There are two mirrors inside a box of size $[-L, L] \times [-L, L]$.

Each mirror is a line segment, and both sides of the mirror can reflect light. The two mirrors share a common endpoint.

A laser beam is emitted from point $(x, y)$ in the direction of $(x+a, y+b)$. This means that if there were no mirrors or box boundaries, the laser would pass through $(x+a, y+b)$. How many times does the laser reflect off the mirrors in total?

If a light ray parallel to a mirror hits an endpoint of that mirror, it is considered not to reflect. If it is not parallel, hitting an endpoint is considered a reflection.

Input

The first line contains two integers $T$ and $L$, representing the number of test cases and the size of the box.

Following this are $T$ lines, each containing 10 integers:

• The first 6 integers are $x_1, y_1, x_2, y_2, x_3, y_3$, representing two mirrors: the segment from $(x_1, y_1)$ to $(x_2, y_2)$ and the segment from $(x_2, y_2)$ to $(x_3, y_3)$.
• The last 4 integers are $x, y, a, b$, representing that the laser is emitted from $(x, y)$ in the direction of $(x+a, y+b)$, meaning that if there were no mirrors or box, the laser would pass through $(x+a, y+b)$.

Output

Output $T$ lines, each containing the total number of reflections for that test case.

Constraints

$1 \le T \le 50\,000$, $1 \le L \le 1000$.

Examples

Input 1

2 10
9 -6 -8 -10 -6 -2 -3 3 -5 1
8 -10 -2 8 -9 1 -2 -3 10 4

Output 1

0
1