Lets define a funny modular sequence as a sequence such that:

• a₁ x a₂=1 (mod p)
• a₂ x a₃=1 (mod p)
• ...
• a_n-1 x a_n = 1 (mod p)

Also, a₁, a₂, a₃, ... a_n must be less than p and greater than or equal to 0. Given one element, a₁, find the sum of the entire funny modular sequence of length n. If, for any a_i, where i>=1, there exists no a_i+1 such that a_ix a_i+1 = 1 (mod p), output -1.

Note: p is not necessarily prime.

Input

The first line contains T, the number of test cases. T lines follow, each containing a₁, p, and n.

Output

For each test case, output one line, the required sum.

Constraints

1<=T<=10⁵
1<=a₁<=10⁵
1<=n<=10⁹
a₁ < p <=10⁹

Sample

Input:
2
2 3 2
3 7 2
Output:
4
8

Explanation

In the first test case, the funny modular sequence will be 2, 2, which has a sum of 4.

In the second test case, it will be 3, 5, which has a sum of 8.