在去年杭电多校，Stump用心感受出了$\sum_{d|n}μ(\frac{n}{d})ln(d)$ 的结果，又震惊了Yoshinow一整年。

今年Legend_dy在复习期末考时，Cuking掏出了下面的式子：

$\sum_{k=1}^nμ(k)⋅(a^{φ(k)+1}\ mod\ k)$

其中 $μ$ 和 $φ$ 分别表示莫比乌斯函数和欧拉函数。

可怜的Legend_dy快复习不完了，你能帮他用心感受一下吗？

第一行一个正整数 $T(1≤T≤30)$，表示测试用例组数。

接下来 $T$ 行，每行输入两个正整数 $n,a(1≤n,a≤10^9)$ ，用一个空格隔开。

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

莫比乌斯函数 $μ$：若 $n$ 中含有非平凡平方因子（即存在某个正整数 $a\gt 1，a^2|n$）则 $μ(n)=0$，否则不妨设 $n$ 的唯一分解为 $n=∏_{i=1}^kp_i$，则 $μ(n)=(−1)^k$.

欧拉函数 $φ：φ(n)$ 表示 $ \{1,2,\dots,n\}$ 中和 $n$ 互质的数的个数。

对于第一组测试用例，$n=3,a=3$，答案为 $1×(3^1\ mod\ 1)+(−1)×(3^1\ mod\ 2)+(−1)×(3^2\ mod\ 3)=−1$.