Trên hệ tọa độ 2 chiều, ta kẻ ~n~ đường zigzag, với đường zigzag thứ ~i~ bắt đầu từ điểm ~(x_i, y_i)~, có độ dài là ~l_i~, và thuộc một trong hai loại:

• Loại ~0~: Xuất phát từ ~(x_i, y_i)~, ta nối các điểm ~(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)~.

• Loại ~1~: Xuất phát từ ~(x_i, y_i)~, ta nối các điểm ~(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)~.

Định nghĩa ~f(i, j)~ là số điểm nguyên chung của đường zigzag thứ ~i~ và đường zigzag thứ ~j~. Hãy tính ~\sum_{i = 1}^n \sum_{j=i+1}^n f(i, j)~.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 10\,000~). Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 2 \cdot 10^5~) — số lượng đường zigzag.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa bốn số nguyên ~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~) — đường zigzag thứ ~i~ bắt đầu từ điểm ~(x_i, y_i)~, có độ dài là ~l_i~, và thuộc loại ~c_i~.

Dữ liệu đảm bảo rằng tổng ~n~ trong tất cả các test case không vượt quá ~2 \cdot 10^5~.

Output

Với mỗi test case, in ra một số nguyên là đáp án của bài toán.

Scoring

Với mỗi test case, định nghĩa ~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

Dưới đây là minh họa cho test case đầu tiên của ví dụ đầu tiên.

Đường màu đỏ và đường màu xanh lần lượt là đường zigzag thứ nhất và thứ hai trong đầu vào. Chúng giao nhau tại điểm chấm, được hiển thị trong minh họa.

Dưới đây là minh họa cho test case thứ hai của ví dụ đầu tiên.

Đường màu đỏ, xanh nước biển và xanh lá cây lần lượt là đường zigzag thứ nhất, thứ hai và thứ ba trong đầu vào. Đường màu xanh nước biển và đường màu đỏ có ~3~ điểm nguyên chung, trong khi đường màu đỏ và đường màu xanh lá cây có ~2~ điểm nguyên chung.