题目描述

小 A 在翻阅三年前的《相马经》古卷时，发现了一个评判马匹血统纯度的公式：

定义 \(S \left(n, m\right) = \sum\limits_{i = 1}^{m} \varphi \left(n \times i\right)\)，其中 \(n\) 为马的谱系编号， \(m\) 为繁衍代数， \(S \left(n, m\right)\) 即为该血脉的纯度值。给定 \(n\) 和 \(m\) 的值，求 \(S \left(n, m\right)\) 在模 \(p\) 意义下的值。

伯乐的数学很差，算不出这些马的血统纯度，只好丢给您来解答。

注： \(\varphi\) 是欧拉函数。具体地，若 \(n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}\)，则 \(\varphi \left(n\right) = n \times \prod\limits_{i = 1}^{k} \left(1 - \frac{1}{p_i}\right)\)。

输入格式

本题有多组测试数据。第一行输入 \(T\ (1 \le T \le 5)\)，表示数据组数。

对于每组数据：

输入一行三个正整数 \(n\)、 \(m\) 和 \(p\) （\(1 \le n, m \le 10^9\)， \(10^8 \le p \le 10^9 + 7\)），不保证 \(p\) 是质数。

输出格式

对于每组数据，输出一行一个整数，表示 \(S \left(n, m\right) \bmod p\) 的值。

样例输入

2
1 2 998244353
2 3 1000000007

样例输出

2
5