用心感受（三）

Problem Description

在去年杭电多校，Stump用心感受出了$\sum_{d|n}\mu(\frac{n}{d})\ln(d)$ 的结果，又震惊了Yoshinow一整年。 今年Legend_dy在复习期末考时，Cuking掏出了下面的式子：

$$\sum_{k=1}^n \mu(k)\cdot (a^{\varphi(k)+1}\bmod k) $$

其中 $\mu$ 和 $\varphi$ 分别表示莫比乌斯函数和欧拉函数。 可怜的Legend_dy快复习不完了，你能帮他用心感受一下吗？

Input

第一行一个正整数 $T(1\leq T\leq 30)$，表示测试用例组数。 接下来 $T$ 行，每行输入两个正整数 $n,a(1\leq n,a\leq 10^9)$ ，用一个空格隔开。

Output

对每组测试用例，输出一行一个整数表示答案。

Sample Input

3
3 3
10 10
100 100

Sample Output

-1
0
97

Hint

莫比乌斯函数 $\mu$：若 $n$ 中含有非平凡平方因子（即存在某个正整数 $a>1$，$a^2|n$）则 $\mu(n)=0$，否则不妨设 $n$ 的唯一分解为 $n=\prod_{i=1}^k p_i$，则 $\mu(n)=(-1)^k$. 欧拉函数 $\varphi$：$\varphi(n)$ 表示 \set{1,2,\dots,n\} 中和 $n$ 互质的数的个数。 对于第一组测试用例，$n=3,a=3$，答案为 $ 1\times(3^1\bmod 1)+(-1)\times (3^1\bmod 2)+(-1)\times(3^2\bmod 3)=-1 $.

Source

2024“钉耙编程”中国大学生算法设计超级联赛（5）