P11747 「TPOI-1A」Oversized Shoes

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

Given a number $x$, you can perform the following operations multiple times until no longer possible: - Choose a number $y$ satisfying $1 \le y < x$ and $\gcd(x, y) \neq 1$, then replace $x$ with $\gcd(x, y)$. There are $T$ queries of two types: - `1 x`: Given $x$, find the maximum number of operations that can be performed on $x$; - `2 q`: Given $q$, find the **smallest** $x$ such that the maximum number of operations on $x$ is exactly $q$.

The first line contains an integer $T$, the number of queries. Each of the next $T$ lines contains a query in the format `1 x` or `2 q`.

For each query, output one integer as the answer.

**Explanation for Sample #1** For `1 2310`, one possible operation sequence is: - Choose $y = 1890$, then $x = \gcd(2310, 1890) = 210$; - Choose $y = 84$, then $x = \gcd(210, 84) = 42$; - Choose $y = 18$, then $x = \gcd(42, 18) = 6$; - Choose $y = 2$, then $x = \gcd(6, 2) = 2$. No further operations can be performed, so the result is $4$. It can be proven that no method allows more than $4$ operations. --- For `2 6`, it can be proven that no number smaller than $128$ can perform exactly $6$ operations. **Constraints** **This problem uses bundled tests. You must pass all test cases in a subtask to receive points.** | Subtask | Special Constraints | Points | |:-:|:-:|:-:| | 0 | Sample | 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 | No special constraints | 30 | For $100\%$ data: $1 \le T \le 10^5$, $1 \le x \le 10^6$, $1 \le q \le 62$. Translated by DeepSeek R1