Given three integers x, m and n. Evaluate (1 + x + x^ 2 + .. + x^ m) (mod n)

Input

First line of the input contains a single integer T representing number of test cases that follow.

For next T lines, each line contains three space separated integers x, m and n.

Output

Output exactly T lines each containing the answer to the corresponding test case.

Constraints

1 ≤ T ≤ 1000
1 ≤ x, n, m ≤ 10^16

Example
Input:
1
3 2 5

Output:
3

见题面

见题面