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