Little Jhool solves huge mathematical questions, for which people usually use super-computers, and everything - but hey, this is Little Jhool we are talking about. This time it's not Little Jhool who is going to solve a tough problem, instead he has asked you to solve this problem for you.
He gives you four things to deal with this problem.
1. An infinite Arithmetic progression.
2. A prime number. - p.
3. The starting number of an Arithmetic Progression. - a.
4. Common difference in the arithmetic progression given to him. - d.
And he asks you to do a very simple thing. With the three powerful numbers, you have at your disposal, you have to print the first index of a number in that Arithmetic Progression, which is a multiple of the given prime number, p.
Input format:
The first line contains a number, tc, denoting the number of test cases. The second line contains two integers, a and d - a depicts the first term in the AP, d depicts the common difference. The last line contains the prime number.
Output format:
You have to print the FIRST index (0-based) of the multiple of the given prime number in the given AP. If no such element exists in this infinite AP, then print -1.
Constraints:
0 <= a, d, <= 10^18
1 <= p <= 10^9
In the first test case, the AP would be: 4, 4+9=13, 13+9=22, 22+9=31 - and the prime number is 11, so the index is [2].
In the second case, the AP would be: 5, 11, 17, 23, 29, 35 - the prime number is 7, so the index is [5].
