A Simple Sum

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

Input

First line contains the number of test cases. Each next line contains three space separated integers x, m and n (1 ≤ x, m, n ≤ 10^16).

Output

For each test case print the answer on a separate line.

Examples