Description

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

Input Format

第一行为一个 $t$（$1 \le t \le 1000$）。

接下来的 $t$ 行，每行为一个数 $a_i$（$0 \le a_i \le 10 ^ {10}$）。

Output Format

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

4
1
4
21
345332

2
3
2
114

Hint

$1$ 在二进制下为 $1$，$4$ 在三进制下为 $11$。

$21$ 在 $2$ 进制下为 $1\ 0\ 1\ 0\ 1$，$345332$ 在 $114$ 进制下为 $26\ 65\ 26$。