You form a geometric progression with N numbers. The first term of the progression is 1 r is the common ratio of the progression. p is a prime number. All the multiplication operations are defined under the modulo p, i.e., a i ≡ ( a i − 1 ∗ r ) ai≡(ai−1∗r) (mod p), for 1 i>1 and a1=1. Now, the sum of the first N terms of the GP modulo p, is S. Now, Dexter only tells the values of , p r,p and S to the monk, and asks if he can find the value of N such that a1+a2+…+aN≡S (mod p) and 1≤N
Note : Dexter also tells a special property about r to the monk that if we form a set of the numbers r1 , r 2 , r 3 , . . . , r p − 1(mod p), then that set will contain all the numbers from 1 to p−1.
Input The first line of input contains a single integer T, denoting the number of questions Dexter asks from Code Monk. The next T lines contain three space-separated integers r,S and p p, denoting the common ratio, the sum of the first N terms of the GP (mod p), and the prime number respectively.
Output For each question, you have to print only one integer, the value of N which satisfies the condition given in the problem. If it is not possible to get S as the sum of the GP (mod p) for any N, print −1.
Constraints 1≤T≤100. 2≤p<109 and p is prime. 1≤r
SAMPLE INPUT
2
5 2 7
5 5 7
SAMPLE OUTPUT
4
-1 Explanation
Case 1: r=5,S=2,p=7 a1=1,a2=5,a3=4,a4=6. We can see that a1+a2+a3+a4≡2 (mod 7). So, answer for this case is N=4.
2: r=5,S=5,p=7 We can see that there is no
1≤N<p, that gives
S
5
S=5 for the sum of the GP.
So, we have the answer
−1.