Here is a mixed edition of Divisor Summation Powered and Amazing Factor Sequence (medium).

The powered factor sequence

For k an integer number, we define our powered factor sequence with:

a_k[0] = 0; a_k[1] = 1, and

for n > 1, a_k[n] = a_k[n - 1] + sum({x^k | 0 < x ≤ n and n % x = 0}).

Input

First line of input contains an integer T, the number of test cases.

Each of the next T lines contains three integers n, k, m.

Output

For each test case, print a_k[n] on a single line.
As the answer could be a big number, you just have to output it modulo m.

Example

Input:
3
3 1 10
4 2 55
5 3 97

Output:
8
37
43

Constraints

0 < T < 101

0 < n < 10^9

0 < k < 11

1 < m < 10^17

Numbers n, k, m are uniform-randomly chosen.
For your information, there's two input files, the first one is 'easy' with n≤100.
My (1kB)-python code get AC around 0.96s. I have a much slower basic PIKE AC (4.8s).
(Edit 2017-02-11 ; timings and TL updated after compiler changes)