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.
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)$$$.
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.
3 3 5 1 1 2 6 1 1 5 7 1 1
4 3 -1
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.
Name |
---|