### 问题描述 小辉有 $m$ 对 $a,p$ ,令 $n=\prod _{i=1}^m p_i$ ，小辉想知道是否存在最小的非负整数 $x$ 满足： $$ x^{p_i} \equiv a_i \pmod n $$ 如果存在，则输出 $x$ ，不存在则输出 $-1$ 。 ### 输入格式 第一行一个整数 $T$ 表示测试数据组数。 每组数据中，第一行一个数 $m$ ，接下来 $m$ 行，每行两个整数 $a_i,p_i$ 。 ### 输出格式 每行一个整数，若 $x$ 存在则输出 $x$ ，否则输出 $-1$ 。 ### 样例输入 ```text 3 2 3 5 2 1 1 13 3 2 3 4 2 4 ``` ### 样例输出 ```text 5 3 4 ``` ### 说明 因为范围较大，建议在 `c++` 中使用 `__int128` 。 ### 评测数据规模 对于 $100$% 的评测数据， $1\leq T\leq 10^4,1\leq n \leq 10^{18},0\leq a_i< n$ 。