Cai, the outstanding billionaire, has a very particular obsession: he only feels comfortable when his feet are planted firmly on an edge or vertex of the tiling — that is, on the boundary of some floor tile. Recently, he acquired a collection of identical, high-end triangular floor tiles. He plans to use these tiles to tile a long, straight corridor in his new mansion.
The corridor is an infinite strip on a two-dimensional plane. To ensure the design meets his supreme standards, Cai has dictated a strict tiling rule: every single triangular tile must be placed such that it spans the entire width of the corridor, touching both parallel boundary lines. This creates a continuous, single-row tessellation of the strip. One of these tiles must exactly match his favorite reference triangle, and all other tiles must be congruent to it.
Cai is currently standing at a fixed location in the hallway. He is exhausted after a long day of terraforming work and, quite frankly, will not move at all. He wants the tiles to grow automatically across the floor starting from his reference triangle, as long as the resulting pattern follows his rules. Of course, it is only a success if an edge or vertex of the tiles coincides with his current position!
Your task is to determine if it is possible to tile the corridor such that Cai's current position, point $D$, lies exactly on an edge or a vertex of the tessellation containing $\triangle ABC$. The corridor's boundaries are defined as the two unique parallel lines $l_1$ and $l_2$ such that $l_1$ passes through $A$ and $B$, and $l_2$ passes through $C$. A tessellation of the strip formed by $(l_1, l_2)$ is a tiling of the entire strip using congruent copies of triangle $\triangle ABC$ (allowing translation, rotation, and reflection), with no overlaps and no gaps.
Illustration of the first two sample test cases.
Input
There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^3$) indicating the number of test cases. For each test case:
The first line contains two integers $x_a$ and $y_a$ ($-100 \le x_a, y_a \le 100$), the coordinates of point $A$.
The second line contains two integers $x_b$ and $y_b$ ($-100 \le x_b, y_b \le 100$), the coordinates of point $B$.
The third line contains two integers $x_c$ and $y_c$ ($-100 \le x_c, y_c \le 100$), the coordinates of point $C$.
The fourth line contains two fractions $x_{d1}/x_{d2}$ and $y_{d1}/y_{d2}$, where $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ are integers satisfying $-10^7 < x_{d1}, y_{d1} < 10^7$ and $0 < x_{d2}, y_{d2} < 10^7$, representing the coordinates of point $D$.
It is guaranteed that $A$, $B$, and $C$ form a non-degenerate triangle.
Output
For each test case, output "Yes" in a line if there exists a valid tessellation such that point $D$ lies on an edge or a vertex of at least one triangle in the pattern. Otherwise, output "No".
Examples
Input 1
4 -2 1 0 0 0 2 2/1 0/1 -2 1 0 0 0 2 1/1 0/1 0 1 -2 1 0 2 1/2 7/4 0 1 -2 1 0 2 -3/2 3/4
Output 1
Yes No Yes No