题目描述

小红帽喜欢回文数，但生活中的数常常不是回文数。现在她手上有 $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$。

4
1
4
21
345332

2
3
2
114

提示

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

$21$ 在 $2$ 进制下为 $10101$，$345332$ 在 $114$ 进制下为 $266526$。