题目描述

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

输入格式

第一行为一个t（1<=t<=1000)

接下来的t行，每行为一个数ai(0<=ai<=10^10)。

输出格式

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

4
1
4
21
345332

2
3
2
114

提示

【样例解释】

1在二进制下为1，4在三进制下为1 1，

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