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$