Hẳn bạn đã từng nghe đến trò chơi "Oẳn tù tì" (Rock, Paper, Scissors). Những chú bò thích chơi một trò tương tự mà chúng gọi là "Móng guốc, Giấy, Kéo" (Hoof, Paper, Scissors).

Luật chơi "Móng guốc, Giấy, Kéo" rất đơn giản. Hai chú bò đấu với nhau. Cả hai cùng đếm đến ba rồi đồng thời ra một ký hiệu tượng trưng cho móng guốc, một tờ giấy hoặc một chiếc kéo. Móng guốc thắng kéo (vì móng guốc có thể đập nát kéo), kéo thắng giấy (vì kéo có thể cắt giấy), và giấy thắng móng guốc (vì móng guốc có thể bị giấy cứa). Ví dụ, nếu chú bò thứ nhất ra "móng guốc" và chú bò thứ hai ra "giấy", thì chú bò thứ hai thắng. Dĩ nhiên, hai chú bò cũng có thể hòa nếu cùng ra một ký hiệu.

Giờ đây có \(N\) (\(3\le N\le 2\cdot 10^5\)) chú bò muốn chơi Móng guốc, Giấy, Kéo, và mỗi chú độc lập sử dụng một chiến thuật lấy ngẫu nhiên theo một phân phối cố định nào đó. Cụ thể, chiến thuật của chú bò thứ \(i\) là ra móng guốc, giấy hoặc kéo với xác suất lần lượt là \(\left(\frac{h_i}{h_i+p_i+s_i}, \frac{p_i}{h_i+p_i+s_i}, \frac{s_i}{h_i+p_i+s_i} \right)\).

Có bao nhiêu bộ ba bò phân biệt \((A,B,C)\) sao cho xét trung bình thì \(A\) thắng \(B\), \(B\) thắng \(C\), và \(C\) thắng \(A\)? Hai bộ ba được coi là giống nhau nếu một bộ có thể thu được từ bộ kia bằng một phép dịch vòng.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 5\cdot 10^4\)), là số bộ test độc lập. Mỗi bộ test có định dạng sau:

Dòng đầu tiên chứa \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm \(h_i\), \(p_i\), \(s_i\) (\(0\le h_i,p_i,s_i\le 10^9\), \(h_i+p_i+s_i>0\)).

Đảm bảo rằng tổng \(N\) trên tất cả các bộ test không vượt quá \(3\cdot 10^5\).

Dữ liệu ra

In ra số bộ ba.

Lưu ý: Do các số nguyên xuất hiện trong bài có thể rất lớn, bạn có thể cần sử dụng kiểu số nguyên 64 bit (chẳng hạn long long trong C/C++).

Ví dụ

2
4
1 0 0
1 0 0
0 1 0
0 0 1
10
20410069 21445597 257862632
114108992 287498302 113278897
607994331 143503714 631122722
337497016 270153603 320256324
633717786 631078144 493265815
202783212 612643590 560838949
713379081 42803063 58996167
293262767 470686180 220651551
656404313 408797935 345461691
959196297 827681918 591519393

2
32

Phân nhóm

• Các test 2–3: \(N\le 10\).
• Các test 4–9: \(N\le 7500\), tổng \(N\) trên tất cả các bộ test không vượt quá \(10^4\).
• Các test 10–21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 First Contest, Platinum Division — "Hoof, Paper, Scissors Triples". Tác giả: Richard Qi. https://usaco.org/index.php?page=viewproblem2&cpid=1548