Description

Elio found a number $N$ on her quilt. She wants to find the smallest $x$ such that $\varphi^x(N) = 1$. Based on this $x$, she can find clues about the aliens who once abducted her. Of course, she will not do the computation herself; please help her compute the minimal $x$.

$\varphi^x(N)$ denotes iterating $\varphi$ $x$ times, not an exponent.

Input Format

The first line contains a positive integer $\mathrm{test}$. Then for each of the $\mathrm{test}$ test cases, the first line contains a positive integer $m$, followed by $m$ lines, each containing two positive integers $p_i, q_i$.

Here $\displaystyle \prod_{i = 1}^{m} p_i^{q_i}$ is the standard factorization form of $N$, and $\prod$ denotes a product.

Output Format

Output $\mathrm{test}$ lines, each containing one integer, the answer.

1
2
2 2
3 1

3

Hint

$\varphi$ is Euler's totient function. $\varphi(n)$ is the number of integers not exceeding $n$ that are coprime to $n$. Hint: $\varphi(\prod_{i=1}^mp_i^{q_i})=\prod_{i=1}^m(p_i-1)\times p_i^{q_i-1}$.

Constraints

• For 30% of the testdata, $N \le 10^6$.
• For 60% of the testdata, $x \le 100$.
• For 100% of the testdata, $\mathrm{test} \le 50$, $1 \le p_i \le {10}^5$, $1 \le q_i \le {10}^9$, $m \le 2000$.

Translated by ChatGPT 5