题目描述

银河联邦议会担心人口数量下降，决定向银河系中的每一位公民发放补贴。具体来说，议会决定：如果某位公民的年龄是一个“圆整数”，就给他发放奖金。

然而，不同种族使用不同进制表示数字，因此“圆整数”不能只在十进制下定义。

经过许多讨论，议会决定：一个年龄 $A$ 被称为圆整数，当且仅当存在某个整数进制 $B\ge 2$，使得 $A$ 在 $B$ 进制下的表示中恰好有两个数字为 $1$，其余数字均为 $0$。

也就是说，$A$ 可以写成如下形式：

奖金金额被定义为使 $A$ 成为圆整数的最小进制 $B$。

法律生效后，议会需要快速计算每位公民应得的奖金，以便在下次选举前把钱发出去。请你编写程序完成这一任务。

输入格式

输入文件 bonus.in 的第一行包含整数 $N$，表示银河系中公民数量。

接下来 $N$ 行，每行包含一个整数 $A_i$，表示第 $i$ 位公民的年龄。

输出格式

输出文件 bonus.out 包含 $N$ 行。

第 $i$ 行输出一个整数，表示使 $A_i$ 成为圆整数的最小进制。

约束

• $1 \le N \le 100000$。
• 对于 $20\%$ 的测试，$1 \le N \le 10000$。
• 对任意 $1\le i\le N$，有 $2 \le A_i \le 2^{64}-1$。

样例

输入

5
36
26
80
56
125

输出

2
5
2
7
124

样例解释

36  = 100100_2
26  = 101_5
80  = 1010000_2
56  = 110_7
125 = 11_124

有些数可能在多个进制下都是圆整数。例如：

但答案始终要求最小的进制。