Background

谁敢向基础数论挑衅？我将终结他的生命！$\mathcal{SWPUACM}$一键烧脑费马小定理$\mathcal{CRT}$符文已配置。

Description

求解下面式子，其中$\mu$和$\varphi$分别表示莫比乌斯函数和欧拉函数

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

Format

Input

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

Output

对每组 $\mathcal{testcase}$ 每一行输出一个整数即计算结果。

Samples

3
33
1010
100100

-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)$ 表示 $\{1, 2, 3...,n\}$中和 $n$ 互质的数的个数。