In the 2D coordinate system, we draw ~n~ zigzag lines, with the ~i~-th zigzag line starting from the point ~(x_i, y_i)~, having a length of ~l_i~, and belonging to one of two types:

• Type ~0~: Starting from ~(x_i, y_i)~, we connect the points ~(x_i, y_i) \to (x_i + 1, y_i) \to (x_i + 1, y_i + 1) \to (x_i + 2, y_i + 1) \to (x_i + 2, y_i + 2) \to \dots \to (x_i+\left\lceil\frac{l_i}{2}\right\rceil, y_i+\left\lfloor\frac{l_i}{2}\right\rfloor)~.

• Type ~1~: Starting from ~(x_i, y_i)~, we connect the points ~(x_i, y_i) \to (x_i, y_i + 1) \to (x_i + 1, y_i + 1) \to (x_i + 1, y_i + 2) \to (x_i + 2, y_i + 2) \to \dots \to \left(x_i+\left\lfloor\frac{l_i}{2}\right\rfloor, y_i+\left\lceil\frac{l_i}{2}\right\rceil\right)~.

The function ~f(i, j)~ is the number of common integer points between the ~i~-th and ~j~-th zigzag lines. Calculate ~\sum_{i = 1}^n \sum_{j=i+1}^n f(i, j)~.

Input

The input consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10\,000~) representing the number of test cases. The description of each test case is as follows.

The first line contains an integer ~n~ (~1 \le n \le 2 \cdot 10^5~) — the number of zigzag lines.

The ~i~-th line among the next ~n~ lines contains four integers ~x_{i}, y_{i}, l_i, c_i~ (~0 \le x_i, y_i \le 10^6~, ~2 \le l_i \le 10^6~, ~0 \le c_i \le 1~) — the ~i~-th zigzag line starts from point ~(x_i, y_i)~, with length ~l_i~, and belongs to type ~c_i~.

The sum of ~n~ in all test cases is guaranteed not to exceed ~2 \cdot 10^5~.

Output

For each test case, output the answer to the problem.

Scoring

For each test case, define ~X = \max(\max x, \max y, \max l)~.

Sample Input 1

2
2
0 0 3 0
0 1 3 0
3
2 3 5 0
2 3 8 1
3 3 3 0

Sample Output 1

1
5

Sample Input 2

2
5
10 10 2 0
9 9 10 1
0 0 20 0
0 0 30 0
1 1 40 0
3
15 20 12 0
20 15 34 0
10 10 56 1

Sample Output 2

92
0

Notes

Below is an illustration for the first test case of the first example.

The red line and the blue line are the first and second zigzag lines in the input, respectively. They intersect at the dotted point shown in the illustration.

Below is an illustration for the second test case of the first example.

The red, navy blue, and green lines are the first, second, and third zigzag lines in the input, respectively. The navy blue line and the red line have ~3~ common integer points, while the red line and the green line have ~2~ common integer points.