Có ~N~ điểm tọa độ nguyên trên mặt phẳng, một tứ giác ~ABCD~ với ~4~ đỉnh trong ~N~ điểm trên gọi là đẹp nếu ~x_A > 0~ và ~y_A > 0~; ~x_B > 0~ và ~y_B < 0~; ~x_C < 0~ và ~y_C< 0~; ~x_D < 0~ và ~y_D > 0~; ~ABCD~ có diện tích nguyên. Nhiệm vụ của bạn là đếm tất cả các cách chọn ~4~ đỉnh tạo nên tứ giác đẹp.

Input

• Dòng đầu tiên là số bộ test ~T~ ~(T < 11)~.
• ~T~ nhóm dòng tiếp theo, mỗi nhóm dòng gồm số điểm ~N~ ~(N < 30001)~, sau đó là ~N~ dòng, mối dòng gồm tọa độ ~1~ điểm ~(x~, ~y)~ ~(-3000 < x~, ~y < 30000)~.

Output

Ghi trên T dòng, mỗi dòng là kết quả tương ứng của từng test.

Sample Input

1
6
1 1
2 2
-1 -1
-2 2
2 -1
-3 -4

Sample Output

2