艾莉欧在她的被子上发现了一个数字 N N N，她觉得只要找出最小的 x x x 使得， φ x ( N ) = 1 \varphi^x(N) = 1 φx(N)=1。根据这个 x x x 她就能找到曾经绑架她的外星人的线索了。当然，她是不会去算，请你帮助她算出最小的 x x x。
第一行一个正整数 t e s t \mathrm{test} test，接下来 t e s t \mathrm{test} test 组数据每组数据第一行一个正整数 m m m，接下来 m m m 行每行两个正整数 p i , q i p_i, q_i pi,qi
其中 ∏ i = 1 m p i q i \displaystyle \prod_{i = 1}^{m} p_i^{q_i} i=1∏mpiqi