Today, Dexter Morgan has Code Monk on his death table. He will ask T questions from Code Monk. If the monk can answer all these questions, he will let him go, otherwise Dexter will kill the monk. Each question is of the following form:

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 \equiv (a_{i-1}*r) \) (mod p), for \(i \gt 1\) and \(a_1 = 1\). Now, the sum of the first N terms of the GP modulo p, is S. Now, Dexter only tells the values of \(r, p\) and S to the monk, and asks if he can find the value of N such that \(a_1 + a_2 + ... + a_N \equiv S\) (mod p) and \(1 \le N \lt p\).

Note : Dexter also tells a special property about r to the monk that if we form a set of the numbers \(r, 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, denoting the common ratio, the prime number and the sum of the first N terms of the GP (mod p), 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 \le T \le 100\).
\(2 \le p \lt 10^9\) and p is prime.
\(1 \le r \lt p\)
\(1 \le S \lt p\)