No submission language available for this problem.

AC游戏

【题目背景】

$A$ 和 $C$ 玩起了数字游戏。

【题目描述】

游戏是回合制游戏，游戏规则是这样：$A$ 和 $C$ 轮流进行操作，$A$ 为先手。 裁判会先确定一个数字 $Q$，每次操作玩家必须写出当前数字的一个因数来代替当前数字，但是这个因数不能是 $1$ 和它本身。 例如当前数字为 $6$，那么可以用 $2, 3$ 来代替，但是 $1$ 和 $6$ 就不行。规定第一个没有数字可以写出的玩家为胜者。

$A$ 在已知 $Q$ 的情况，想知道自己作为先手能不能胜利，若能胜利，那么第一次写出的可以制胜的最小数字是多少呢？ 整个游戏过程我们认为 $A$ 和 $C$ 用的都是最优策略。

【输入格式】

第一行一个整数 $T$ 表示将有 $T$ 组测试。

接下来又 $T$ 行，每行一个正整数 $Q$。

【输出格式】

有 $T$ 组输出，分别对应一个 $Q$ 的结果，每组输出如下：

第一行是 $1$ 或 $2$，$1$ 表示 $A$ 能胜利，$2$ 表示 $C$ 能胜利。

若 $A$ 能胜利，则在第二行输出第一次写出的可以制胜的最小数字。

若是第一次就无法写出数字，则认为第一次写出的可以制胜的最小数字为 $0$。

【样例】

输入数据

2
6
30

输出数据

2
1
6

【说明】

对于 $100 \%$ 的数据，$4\le T \le 6$

对于 $30 \%$ 的数据，$Q \le 50$

对于 $100 \%$ 的数据，$2 \le Q \le {10}^{13}$