A. Luxury
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Westin the sheep is located at the lattice point $$$(x,y)$$$. His private jet can travel to any point inside or on the circle centered at $$$(x,y)$$$ with radius $$$r$$$.

There are two countries. Each country is a parallelogram, and a city is located at every lattice point (integer coordinate) that lies inside the parallelogram. The border of the parallelogram counts as inside.

For each country, Westin can visit the cities whose lattice points lie inside or on his circle. Your task is to compare the number of reachable cities in the two countries.

The vertices of each parallelogram are given in the following order:

  • $$$(x_1,y_1)$$$: top-left
  • $$$(x_2,y_2)$$$: top-right
  • $$$(x_3,y_3)$$$: bottom-left
  • $$$(x_4,y_4)$$$: bottom-right

It is guaranteed that for every parallelogram, one pair of opposite sides is parallel to the $$$x$$$-axis (equivalently, the top and bottom edges are horizontal, so $$$y_1=y_2$$$ and $$$y_3=y_4$$$).

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

Each test case consists of three lines:

  • The first line contains three integers $$$x$$$, $$$y$$$, $$$r$$$ ($$$-10^5 \lt x,y \lt 10^5$$$, $$$1 \le r \lt 10^5$$$).
  • The second line contains eight integers $$$x_1\ y_1\ x_2\ y_2\ x_3\ y_3\ x_4\ y_4$$$ describing Country $$$1$$$ ($$$-10^5 \lt x_i,y_i \lt 10^5$$$).
  • The third line contains eight integers $$$x_1\ y_1\ x_2\ y_2\ x_3\ y_3\ x_4\ y_4$$$ describing Country $$$2$$$ ($$$-10^5 \lt x_i,y_i \lt 10^5$$$).

Borders count as inside. It is guaranteed that for every parallelogram, one pair of opposite sides is parallel to the $$$x$$$-axis.

Let $$$n$$$ be the vertical span (in lattice rows) of a country: $$$n = y_1 - y_3 + 1$$$ (since $$$(x_1,y_1)$$$ is top-left and $$$(x_3,y_3)$$$ is bottom-left). It is guaranteed that the sum of $$$n$$$ over all countries across all test cases does not exceed $$$10^5$$$.

Output

For each test case, output one integer:

  • output $$$1$$$ if Country $$$1$$$ has strictly more reachable cities,
  • output $$$2$$$ if Country $$$2$$$ has strictly more reachable cities,
  • output $$$3$$$ if both countries have the same number of reachable cities.
Example
Input
1
0 0 1
-1 1 0 1 0 0 1 0
-1 0 0 0 0 -1 1 -1
Output
3
Note

For the first sample, the following figure illustrates the two parallelograms; both have the same amount of cities inside the radius of the circle, thus the output is $$$3$$$: