Gene Splicing

Gene Splicing

The CSC has a new head biochemist working on virus vaccines, and she is revolutionizing gene splicing via a novel method. Specifically, if she wants to mix the DNA of two viruses, she proceeds as follows:

1. Prepare a petri dish of A milliliters of liquid DNA from Virus #1.
2. Prepare a petri dish of B milliliters of liquid DNA from Virus #2.
3. Mix'em up!
   • Take C milliliters of liquid DNA from dish #1 and place it into dish #2.
   • Take C milliliters of (the now perfectly mixed) liquid DNA from dish #2 and place it back into dish #1.
4. Keep mixing...

She repeats this mixing process iteratively for a very long time. If she repeated this process forever, then the ratio of liquid DNA from Virus #1 to liquid DNA from Virus #2 in each dish would converge to A/B. However, she desperately wishes to work a 9am - 5pm job, and so is interested in how many iterations of mixing it takes before the mixture is within some tolerance of A/B. (Once the mixture is close enough to A/B, she can immediately 3D print a new virus for study!)

Input

The first line in the test data file contains the number x of test cases. After this, the x test cases are given one by one. Each test case starts with the number ​ A of milliliters in dish #1, the number B of milliliters in dish #2, the mixture amount C, and a tolerance T . You can assume A, B, and C are positive integers with C < min(A, B), both petri dishes have capacity at least A + B and T is a positive real number.

Output

The output is a list of I, the number of iterations before the mixture of liquid DNA in both petri dishes is within tolerance T of the value A/B.

Example input and corresponding output data:

Test Data

The file gene_splicing_test.dat should produce the following output:

9
11
13
99
93
167
2652
4952
1
1
1197
2838