Keliane is a playful girl.

One day, she nails $n$ nails into a wall, where the $i$-th nail is at coordinates $(x_i, y_i)$. Then, she attaches $m$ strings to the wall. Each string has one end fixed at $s_i(sx_i, sy_i)$, passes through point $t_i(tx_i, ty_i)$, and has a total length of $L_i$. The point $s_i$ is "stuck" to the wall, while the other end is movable. Initially, the string is a taut straight line segment.

Keliane then plays a game with each string. In the $i$-th game, she holds the movable end of the $i$-th string and moves it clockwise, keeping the string taut at all times.

It is easy to see that the string is always performing a clockwise circular motion centered at some position. Initially, the center is the fixed end $s_i$ of the string, but during the motion, the center may change continuously, as shown in the figure below:

In the figure, the red dot on the left is a nail, the red dot on the right is the fixed end of the string, the dots of other colors are virtual points, and the movable end is the purple dot. The string starts moving from the purple dot. When it reaches the blue dot, the string wraps around the nail on the left, causing the movable end to change its center and radius, continuing its clockwise circular motion. Then, the movable end reaches the green dot, and from then on, it will continue to rotate around the left nail indefinitely.

It is clear that the motion of the string will not stop, so Keliane stops when she gets tired. However, as a curious girl, Keliane decides to calculate, for each string, how many times the center of rotation changes (including the initial center) if the string were to run indefinitely. It is easy to see that this number must be finite.

To simplify the problem, we make the following assumptions about the game process:

1. During the motion, the distance from the movable end to every nail is always at least $9 \times 10^{-4}$.
2. The coordinates of the nails are distinct, but multiple points may be collinear.
3. The volume of the nails and the string can be ignored. During the game, different segments of the string do not affect each other.
4. Initially, the minimum Euclidean distance from the string to any nail is at least $9 \times 10^{-4}$.
5. The fixed end where the string is initially attached will not affect the motion of the string, i.e., the string will not wrap back onto the fixed end.

Input

The input is read from standard input.

The first line contains an integer $T$, representing the number of test cases.

For each test case, the first line contains two integers $n$ and $m$, representing the number of nails and the number of strings.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the nails.

The next $m$ lines each contain five integers $sx_i, sy_i, tx_i, ty_i, L_i$, representing a string, with meanings as described above.

Output

Output to standard output.

For each query in each test case, output one integer per line representing the number of times the center of rotation changes during the process.

There is no need to separate different test cases with empty lines.

Examples

Input 1

2
5 3
0 0
2 0
2 2
0 2
1 1
1 3 10 3 10
1 3 10 3 20
1 3 10 3 30
3 1
0 0
100 0
1000 0
1 3 10 3 1000000000

Output 1

6
11
16
1000001

Note 2

See the provided files.

For the sake of the contestants' health, Keliane decided to add a large sample case. However, because this is an IOI-style contest, Keliane did not want the large sample to be too difficult.

The large sample is shown in the figure below:

The "dots" of two colors represent the nails and the queries, respectively. Why does a query look like a point? Because each query is a line segment of length $1$, and given the large coordinate range, it appears as a point.

It is easy to see that the answer for each query is $1$.

Constraints

For the first $10\%$ of the data, $n \leq 2$.

For the first $20\%$ of the data, $n \leq 3$.

For the first $30\%$ of the data, $n \leq 10$.

For the first $60\%$ of the data, $n \leq 100$, $m \leq 100$.

For $100\%$ of the data, $1 \leq n \leq 500$, $1 \leq m \leq 500$, $1 \leq T \leq 10$.

For $100\%$ of the data, $0 \leq |x_i|, |y_i|, |sx_i|, |sy_i|, |tx_i|, |ty_i| \leq 10^4$, $1 \leq L_i \leq 10^9$.