P11747 「TPOI-1A」鞋子特大号

 You may click here to read English statement. > 我戴着圆顶礼帽 鞋子特大号 > > 我手拿拐杖留着胡子 大家好 > > 别什么你都想要快乐却找不到 > > 幽默是挫折中优雅的礼貌 > > ——周杰伦《[鞋子特大号](https://www.bilibili.com/video/BV1Wt4y1P74C)》

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

无

无

【样例 #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$|无特殊性质|$30$| 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le x \le 10^6$，$1 \le q \le 62$。