题目描述

我们定义一种“$k$-合法数”：对于一个正整数 $y$ 和一个正整数 $k \ge 2$，如果 $y$ 在 $k$ 进制下的所有数位上的数字之乘积非零，且该乘积能够整除 $y$ 本身，则称 $y$ 为“$k$-合法数”。 例如：

• 当 $k = 10$ 时，$y = 36$ 是 $10$-合法数，因为 $(3 \times 6) \mid 36$。
• 当 $k = 4$ 时，$y = 6$ 是 $4$-合法数，因为 $6$ 转换为 $4$ 进制后为 $(12)_4$，而 $(1 \times 2) \mid 6$。
• 当 $k = 2$ 时，$y = 13$ 不是 $2$-合法数，因为 $13$ 转换为 $2$ 进制后为 $(1101)_2$，数位乘积为 $0$，而 $0$ 不能作为除数。

Alice 和 Bob 正在玩一个取棋子游戏。初始时有 $x$ 枚棋子。 在游戏开始前，Alice 会选定一个正整数 $k$（$k \ge 2$）。 随后两人交替取走棋子，由 Alice 先手。每次取走的棋子数量必须是一个 $k$-合法数。取走最后一枚棋子的一方获胜。

假设双方均采取最优策略。给定初始棋子数 $x$，请你求出能使 Alice 先手必胜的最小的 $k$ 是多少？

输入格式

第一行包含一个正整数 $T$ —— 表示数据组数。

接下来 $T$ 行，每行包含一个正整数 $x$ —— 表示初始的棋子数。

输出格式

输出共 $T$ 行，每行一个正整数，表示对应询问中能使 Alice 必胜的最小的 $k$。

样例输入 1

3
9
5
10

样例输出 1

2
2
3

说明

样例解释

当 $x=5$ 的时候，Alice 可以选择 $k=2$。

• 初始时有 $5$ 枚棋子。
• Alice 先手拿走 $3$ 枚（因为 $3=(11)_2$，数位乘积为 $1 \times 1 = 1$，$1 \mid 3$，所以 $3$ 是合法的）。
• 此时剩余 $2$ 枚棋子。Bob 只能拿走 $1$ 枚（因为 $1=(1)_2$ 合法，而 $2=(10)_2$ 数位乘积为 $0$ 不合法）。
• 最后剩余 $1$ 枚，Alice 拿走最后的 $1$ 枚从而获胜。

又因为 $k=2$ 已经是题目允许的最小值，所以对于 $x=5$ 最终答案为 $k=2$。

数据范围

• 对于所有测试点，保证 $1 \le T \le 100$。
• 对于所有测试点，保证 $3 \le x \le 10^{18}$。
• 保证所有的输入数值均为整数。