给定 T 组询问，每组给出两个整数 a 和 p ，其中 p 是素数， 1 \le a < p 。
请你输出 a 在模 p 意义下的乘法逆元 x ，即满足 a \cdot x \equiv 1 \pmod p 、且 0 \le x < p 的那个 x 。
在给定范围内该 x 是唯一存在的。
第一行一个整数 T 。 接下来 T 行，每行两个整数 a, p 。
输出 T 行，每行一个整数，对应该询问的逆元。
4 2 5 3 7 5 11 7 13
3 5 9 2
2 \cdot 3 = 6 \equiv 1 \pmod 5 ； 3 \cdot 5 = 15 \equiv 1 \pmod 7 ； 5 \cdot 9 = 45 \equiv 1 \pmod{11} ； 7 \cdot 2 = 14 \equiv 1 \pmod{13} 。
1 \le T \le 10^5 ， p 为素数， 1 \le a < p \le 10^9 。
由 Fermat 小定理， a^{p - 1} \equiv 1 \pmod p ，故 a^{p - 2} 即为所求。用快速幂计算 a^{p - 2} \bmod p ，单次 O(\log p) ，整体 O(T \log p) 。 T \le 10^5 时输入输出是瓶颈，请使用 scanf/printf。
scanf
printf