GCD Operation Queries

You are given a number \( x \). You can perform the following operation any number of times until no further operations are possible:

• Select a number \( y \) satisfying \(1 \le y < x\) such that \(\gcd(x,y) \neq 1\), and then update \(x\) to \(\gcd(x,y)\).

There are two types of queries. In total, there are \( T \) queries:

• Query 1: 1 x — Given \( x \), compute the maximum number of operations you can perform.
• Query 2: 2 q — Given an integer \( q \), find the smallest \( x \) such that the maximum number of operations is exactly \( q \).

Observation:

Let the prime factorization of \( x \) be \( x=\prod_{i} p_i^{a_i} \). It can be shown that the maximum number of operations is given by:

[ f(x)=\left(\sum_i a_i\right)-1. ]

For Query 1, given \( x \) compute \( f(x)=\Big(\sum_{p^a\parallel x} a\Big)-1 \). Note that if \( x \) is prime, then \( f(x)=0 \).

For Query 2, we need to find the smallest \( x \) such that \( f(x)=q \). In other words, we need \( \sum_i a_i=q+1 \). It is optimal to choose the prime factorization with only one prime. Since \( 2 \) is the smallest prime, the answer for Query 2 is \( x=2^{q+1} \).

You are required to answer each query and print the answer on a separate line.

inputFormat

The input begins with a single integer \( T \) (the number of queries). Each of the next \( T \) lines contains a query in one of the following two formats:

• 1 x — for Query 1
• 2 q — for Query 2

It is guaranteed that \( x \) and \( q \) are such that the answers fit within the range of 64-bit integers.

outputFormat

For each query, output a single line containing the answer. For Query 1, output \( f(x) \). For Query 2, output the smallest \( x \) such that \( f(x)=q \).

sample

3
1 8
2 1
1 12

2
4
2

</p>