Type: Default 1000ms 256MiB

ez4OIer

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

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

Description

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

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

Format

Input

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

Output

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

Samples

3
33
1010
100100
-1
0
97

Hint

莫比乌斯函数 μ\mu :若 nn 中含有非平凡平方因子(即存在某个正整数 a>1a2na>1,a^2|n)则 μ(n)=0\mu (n)=0,否则不妨设 nn 的唯一分解为 n=i=1kpin = \prod_{i=1}^{k} p_i ,则 μ(n)=(1)k\mu(n)=(−1) ^ k.

欧拉函数 φ\varphiφ(n)\varphi(n) 表示 {1,2,3...,n}\{1, 2, 3...,n\}中和 nn 互质的数的个数。