C. Equipartition
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Herminia wants to divide her lands among her four children. Herminia's estate consists of $$$n$$$ possessions, the $$$i$$$-th of which is located at the point $$$(x_i, y_i)$$$ in the plane (where $$$x_i$$$, $$$y_i$$$ are integer coordinates) and has a value $$$v_i$$$.

Herminia will divide her lands as follows: she will choose a point $$$(a, b)$$$ and give each child the possessions contained in one of the four quadrants defined by the point. That is:

  • One of the children will receive the possessions with coordinates $$$(x, y)$$$ such that $$$x \leq a$$$ and $$$y \leq b$$$.
  • Another will receive the possessions with coordinates $$$(x, y)$$$ such that $$$x \gt a$$$ and $$$y \leq b$$$.
  • Another will receive the possessions with coordinates $$$(x, y)$$$ such that $$$x \leq a$$$ and $$$y \gt b$$$.
  • The last child will receive the possessions with coordinates $$$(x, y)$$$ such that $$$x \gt a$$$ and $$$y \gt b$$$.

Herminia wants each child to receive the same total value in possessions. Help Herminia find the number of points $$$(a, b)$$$ with integer coordinates such that the sum of the values of the possessions in each of the quadrants is equal.

Input

The input begins with a number $$$T$$$ — the number of test cases.

Each test case starts with a line with an integer $$$n$$$, the number of possessions. Next, there are $$$n$$$ lines, the $$$i$$$-th of which has three integers $$$x_i$$$, $$$y_i$$$, and $$$v_i$$$: the coordinates and the value of the $$$i$$$-th possession.

Output

For each test case, your program should print a line with the number of points with integer coordinates $$$(a, b)$$$ such that the values of the possessions in each of the four quadrants defined by those points add up to the same total.

Scoring
  1. (17 points) $$$n = 4$$$.
  2. (23 points) $$$n \leq 30$$$.
  3. (19 points) $$$n \leq 500$$$.
  4. (21 points) $$$0 \leq x_i, y_i \lt \min(3\cdot 10^4, n)$$$, $$$v_i = 1$$$ for all $$$i = 1, \ldots, n$$$.
  5. (20 points) No additional restrictions.
Example
Input
3
5
-1 -2 1
3 4 2
2 -5 2
-2 -1 1
-4 3 2
1
0 0 1
4
-1000000000 -1000000000 1
1000000000 -1000000000 1
-1000000000 1000000000 1
1000000000 1000000000 1
Output
12
0
4000000000000000000
Note

$$$1 \leq T \leq 1000$$$.

$$$1 \leq n \leq 2 \cdot 10^5$$$.

The sum of $$$n$$$ for all cases will be at most $$$2 \cdot 10^5$$$.

$$$-10^9 \leq x_i, y_i \leq 10^9$$$.

There are no repeated pairs $$$(x_i, y_i)$$$.

$$$1 \leq v_i \leq 10^9$$$.