Lets think of an infinite series of numbers such that the difference between any two consecutive numbers is d. Let the first number in the sequence be a.
Now your task is to find the multiple that occurs first in the sequence of a given number n and print its index in the output.
Input
1st line T denoting test cases.
T test cases follow :
1st line consists of two space separated integers a and d. 0 ≤ a,d ≤ pow(10,18);
2nd line contains a single integer n. 1 ≤ n ≤ pow(10,9);
Output
print as said above and if there is no such number then print -1.
Update: the number n is strictly a prime number and index of the sequence starts with 0.

SAMPLE INPUT
2
5 6
7
4 9
11

SAMPLE OUTPUT
5
2

见题面

见题面