find the length of gp of given common ratio

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



5 2 7

5 5 7



-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 for the sum of the GP.
So, we have the answer

It will be more convenient for both of you and us if you provide question link only.

1 Like

Dexter? Is this, by any chance is related to a contest going on heackerearth ?? please provide Q link so that we can be sure its not related to an on going contest.

It is ongoing contest.I think it’s not fair to discuss like this!The contest ends tomorrow.After that editorials will be available!
Happy Coding…