题目描述

给定一个数 $x$，你可以对其进行以下操作若干次，直到无法再操作：

• 选择一个数 $y$ 满足 $1 \le y < x$ 且 $\gcd(x,y) \not = 1$，并将 $x$ 变为 $\gcd(x,y)$。

现在有以下两种询问共 $T$ 个：

• 1 x：给定 $x$，求 $x$ 最多能进行几次操作；

• 2 q：给定 $q$，求出一个最小的 $x$，使得 $x$ 最多能进行恰好 $q$ 次操作。

输入格式

第一行，一个整数 $T$，表示询问个数。

接下来 $T$ 行，每行一次询问，保证格式一定为 1 x 或 2 q。

输出格式

共 $T$ 行，每行一个整数，表示询问的答案。

2
1 2310
2 6

4
128

提示

【样例 #1 解释】

对于 1 2310，以下是其中一种操作方式：

• 选择 $y=1890$，则此时 $x=\gcd(2310,1890)=210$；
• 选择 $y=84$，则此时 $x=\gcd(210,84)=42$；
• 选择 $y=18$，则此时 $x=\gcd(42,18)=6$；
• 选择 $y=2$，则此时 $x=\gcd(6,2)=2$。

此时无法再操作，所以结果为 $4$。

可以证明不存在一种方法可以操作超过 $4$ 次。

对于 2 6，可以证明，无法找出一个比 $128$ 小的数，使得其可以进行 $6$ 次操作。

【数据范围】

本题采用捆绑测试。你只有通过一个子任务内的所有测试点，该子任务才会得分。

对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le x \le 10^6$，$1 \le q \le 62$。