P2350 [HAOI2012] Alien

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.

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 $\mathrm{test}$ lines, each containing one integer, the answer.

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