This problem is a programming version of Problem 144 from projecteuler.net
In laser physics, a "white cell" is a mirror system that acts as a delay line for the laser beam. The beam enters the cell, bounces around on the mirrors, and eventually works its way back out.
The white cell we will use as an example is an ellipse with the equation .
The section corresponding to at the top is missing, allowing the light to enter and exit through the hole.
The light beam in this problem starts at the point just outside the white cell, and the beam first impacts the mirror at .
Each time the laser beam hits the surface of the ellipse, it follows the usual law of reflection "angle of incidence equals angle of reflection." That is, both the incident and reflected beams make the same angle with the normal line at the point of incidence.
In the figure on the left, the red line shows the first two points of contact between the laser beam and the wall of the white cell; the blue line shows the line tangent to the ellipse at the point of incidence of the first bounce.
The animation on the below shows the first 10 reflections of the beam.
The original question is: how many times does the beam hit the internal surface of the white cell before exiting?
In this problem we'll deal with the generalization: Given an ellipse with an equation , the starting point of the light beam, and the place where it first impacts the mirror, how many times does the beam hit the internal surface of the white cell before exiting?
Assume that the section corresponding to at the top is missing.
Input Format
The first line of input contains , the number of test cases.
The first line of each test case contains three integers, , and .
The second line of each test case contains four real numbers , , and . denotes the starting point of the laser beam, and denotes the place where it first impacts the mirror.
Constraints
, , , are given with two decimal places.
is outside the ellipse, i.e., .
is exactly on the ellipse, i.e., .
The beam passes through the missing section at the top.
The beam won't pass through any point away from the ends of the missing section.
The answer for each test case is less than .
Output Format
For each test case, output a single line containing a single integer, the answer for that test case.
Sample Input
2
4 1 100
0.00 10.10 0.00 -10.00
75 77 720
0.00 3.06 -2.70 -1.50
Sample Output
1
2
Explanation
The first case corresponds to the example ellipse in the problem statement, but the beam enters it vertically. Thus it only bounces once and immediately exits afterwards.
The second case corresponds to a near circle. The beam enters and bounces in a triangle-like way as follows:
Thus it bounces two times before it exits.