Babuji likes Sanskari functions and has written one of his own.

DoSomething(x,y,prime){

a = 1;

for(i=0 ; i < y ; i++)

{

a = (a-prime)*(x+prime);

}

a = a%prime;

a = (a+prime)%prime;

return a;

}

Now he wants to write a function that does the reverse of above function .

i.e for a given value of x,prime,a you have to output the least possible non-negative value of y

such that a = DoSomething(x,y,prime). If there is no such value print -1

Can you do this task for babuji ?

Input:

First line contains t - no of test cases

t lines follow each containing 3 integers x,prime,a

Output:

t lines. ith line containing answer for the ith case.

Constraints:

0 < t < 10

0 < x < 10^9

0 <= a < 10^8

0 < p < 10^7

note: prime will always be a prime number <10^7

Sample Input:

3

2 7 8

2 7 1

3 5 3

Sample Output:

-1

0

1