B. Potion(easy version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem C. The only difference between the two versions is that the easy version satisfies a=b=1.

Twilight Sparkle is a Unicorn pony who loves knowledge.

One day, she is learning how to make magic potion with the teaching of Zecora, a zebra living in Everfree Forest.

In the preparatory work, she should mix pure water with the magic water extracted from Everfree Forest in a specific proportion $$$x:y$$$. (These two types of liquid can dissolve in each other, of course.)

However, she has only one measuring cup with blur scale marks. More specifically, the measuring cup has a volume of $$$a+b$$$ ml and only one distinct scale mark at $$$a$$$ ml. That is, she can only measures $$$a$$$ ml or $$$a+b$$$ ml of liquid via this measuring cup precisely.

Now Twilight Sparkle are allowed to perform the following operations any times:

1. Fill the measuring cup with pure water or magic water.

2. Pour the mixture water out from the measuring cup and preserve $$$a$$$ ml of mixture in the measuring cup.

Twilight Sparkle wonders what is the minimum possible number of operation 1 to make a mixture with proportion $$$x:y$$$ in the measuring cup, or tell that is impossible.

Input

The first line contains a single integer $$$T\ (1\le T\le 10^5)$$$ - the number of testcases.

Each testcase contains only one line, four integers $$$x,y,a,b\ (1\le x,y\le 10^{18},a=b=1)$$$.

Output

For each testcase, if Twilight Sparkle couldn't make the specific mixture, print a single integer: $$$-1$$$.

Otherwise, print the minimum number of operation 1 to do that.

Example
Input
3
3 5 1 1
2 6 1 1
5 7 1 1
Output
4
3
-1
Note

For the first test case, Twilight Sparkle does the following operations:

Fill in pure water, then the proportion is $$$1:0$$$.

Pour out the mixture till $$$a$$$ ml remains, and pour in magic water, then the proportion is $$$1:1$$$.

Pour out the mixture till $$$a$$$ ml remains, and pour in pure water, then the proportion is $$$3:1$$$.

Pour out the mixture till $$$a$$$ ml remains, and pour in magic water, then the proportion is $$$3:5$$$.

For the second test case, Twilight pours in pure, magic and then magic water in order.(And also does operation 2 every time she fills in liquid except the last time.)

For the third test case, there is no way for her to make the specific mixture.