小红帽的回文数

题目描述

小红帽喜欢回文数,但生活中的数常常不是回文数。现在她手上有 $t$ 个数,现在她知道这 $t$ 个数分别在 $x$ 进制下是回文数($x \ge 2$),请你对于每个数求出最小的 $x$。

输入输出格式

输入格式


第一行为一个 $t$($1 \le t \le 1000$)。 接下来的 $t$ 行,每行为一个数 $a_i$($0 \le a_i \le 10 ^ {10}$)。

输出格式


输出有 $t$ 行,每行为所求的 $x$。

输入输出样例

输入样例 #1

4
1
4
21
345332

输出样例 #1

2
3
2
114

说明

$1$ 在二进制下为 $1$,$4$ 在三进制下为 $11$。 $21$ 在 $2$ 进制下为 $10101$,$345332$ 在 $114$ 进制下为 $266526$。