A Nice-P sequence is defined 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). In addition, 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 Nice-P sequence of length n. If, for any a_i, where i>=1, there exists no a_i+1 such that a_i x a_i+1 = 1 (mod p), output -1.

NOTE: p IS NOT NECESSARILY A 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⁹