艾利欧在她的被子上发现了一个数字 $N$，他觉得只要找出最小的 $x$ 使得，$\varphi^x(N)=1$。根据这个 $x$ 她就能找到曾经绑架她的外星人的线索了。当然，她是不会去算，请你帮助她算出最小的 $x$。
第一行一个正整数 $test$，接下来 $test$ 组数据每组数据第一行一个正整数 $m$，接下来 $m$ 行每行两个正整数 $p_i,q_i$。
其中 $\sum_{i=1}^m p_i^q$ 为 $N$ 的标准分解形式。
输出 $test$ 行，每行一个整数，表示答案。
1 2 2 2 3 1
3
$test \le 50$
$p_i \le 10^5，1 \le Q_i \le 10^9$
Comet OJ