Problem Description

在[去年](https://acm.hdu.edu.cn/showproblem.php?pid=7318)杭电多校，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

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

3
3 3
10 10
100 100

-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 $.