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

Sample Output:

4

8

Explanation