FUNMODSEQ - Funny Modular Sequence

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

  • a1 x a2 = 1 (mod p)
  • a2 x a3 = 1 (mod p)
  • ...
  • an-1 x an = 1 (mod p)

Also, a1, a2, a3 ... an must be less than p and greater than or equal to 0. Given one element, a1, find the sum of the entire funny modular sequence of length n. If, for any ai, where i>=1, there exists no ai+1 such that aix ai+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 a1, p, and n.

Output

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

Constraints

1<=T<=105
1<=a1<=105
1<=n<=109
a1 < p <=109

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.


Added by:Piyush Kumar
Date:2016-06-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Hackerearth Monthly Contest

hide comments
2016-06-17 07:08:10 [Rampage] Blue.Mary
The sample input doesn't contain the number of test cases in the first line.

Re: My bad! Updated!

Last edit: 2016-06-17 07:29:11
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.