Trên quảng trường trung tâm thành phố, người ta đặt một bảng quảng cáo điện tử hình vuông kích thước \(10^9 \times 10^9\) được chia làm lưới ô vuông đơn vị. Các hàng của bảng đánh số từ \(1\) tới \(10^9\) từ trên xuống dưới và các cột của bảng đánh số từ \(1\) tới \(10^9\) từ trái qua phải. Ô nằm trên giao của hàng \(i\) và cột \(j\) gọi là ô (\(i,j\)).

Có \(n\) hãng đăng kí quảng cáo đánh số từ \(1\) tới \(n\), hãng thứ \(i\) đăng kí quảng cáo trong một cửa sổ hình chữ nhật có cạnh song song với cạnh bảng, hình chữ nhật này có ô ở góc trên bên trái là ô \((a_i,b_i)\) và ô ở góc dưới bên phải là ô \((c_i,d_i)\). Trên cửa sổ, hãng có thể chiếu lên bảng những đoạn video giới thiệu sản phẩm của mình.

Khi hiện lên bảng, cửa sổ quảng cáo của một số hãng có thể giao nhau làm ảnh hưởng tới sự chú ý của người xem, người ta muốn thống kê số cặp (\(i,j\)) với \(1 \le i < j \le n\) mà cửa sổ quảng cáo của hai hãng \(i\) và \(j\) có chung ít nhất một ô, để từ đó thông báo cho các hãng có kế hoạch thay đổi vị trí và kích thước cửa sổ của mình cho phù hợp.

Yêu cầu: Hãy xác định số lượng những cặp (\(i,j\)) với \(1 \le i < j \le n\) mà cửa sổ quảng cáo của hai hãng \(i\) và \(j\) có chung ít nhất một ô.

Input

• Dòng đầu chứa số nguyên dương \(T \le 1000\) là số bộ dữ liệu.
• \(T\) nhóm dòng tiếp theo, mỗi nhóm dòng miêu tả một test:
  • Dòng đầu của nhóm chứa số nguyên dương \(n \le 2 \times 10^5\).
  • \(n\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên dương \(a_i,b_i,c_i,d_i\) cách nhau bởi dấu cách (\(1 \le a_i \le c_i \le 10^9, 1 \le b_i \le d_i \le 10^9\)).
• Tổng các giá trị \(n\) trong tất cả các test không vượt quá \(2 \times 10^5\).

Output

• Gồm \(T\) dòng, ứng với mỗi bộ dữ liệu, đưa ra một số nguyên duy nhất trên một dòng là số lượng những cặp (\(i,j\)) với \(1 \le i < j \le n\) mà cửa sổ quảng cáo của hai hãng \(i\) và \(j\) có chung ít nhất một ô.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n = 2\).
• Subtask \(2\) (\(15\%\) số điểm): \(n \le 10^3, T \le 50\).
• Subtask \(3\) (\(30\%\) số điểm): \(1 \le a_i \le c_i \le 100, 1 \le b_i \le d_i \le 100\).
• Subtask \(4\) (\(35\%\) số điểm): không có ràng buộc gì thêm.

Example

2
2
1 1 2 2
2 2 3 3
5
1 3 2 5
2 2 6 3
2 6 7 9
3 5 6 10
6 3 7 7

1
5