题目背景

You may click here to read English statement.

我戴着圆顶礼帽 鞋子特大号

我手拿拐杖留着胡子 大家好

别什么你都想要快乐却找不到

幽默是挫折中优雅的礼貌

——周杰伦《鞋子特大号》

题目描述

给定一个数 $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$ 次操作。

【数据范围】

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

$\text{Subtask}$	特殊性质	分值
$0$	样例	$0$
$1$	$T \le 2,2 \le x \le 100,q \le 5$	$40$
$2$	$T \le 10^5,x \le 10^3,q \le 25$	$30$
$3$	无特殊性质

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