Description

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$.

Input Format

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.

Output Format

For each query, output one integer as the answer.

2
1 2310
2 6

4
128

Hint

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.

For $100\%$ data: $1 \le T \le 10^5$, $1 \le x \le 10^6$, $1 \le q \le 62$.

Translated by DeepSeek R1