Nguồn: https://www.codechef.com
Trong một bữa tiệc có N chàng trai và M cô gái. Bạn được cho một ma trận A gồm N hàng và M cột với Aij bằng 1
nếu chàng trai thứ i thích cô gái
thứ j, ngược lại sẽ bằng 0. Chú ý rằng nếu chàng trai x thích cô gái y, thì cô gái y không
nhất thiết phải thích chàng trai x.
Bạn biết rằng nếu 2 chàng trai x và y khác nhau cùng thích một cô gái z, thì họ sẽ có xung đột. Bạn có thể tính số lượng xung đột khác
nhau trong bữa tiệc? Chú ý rằng, thứ tự của các chàng trai trong một xung đột
không quan trọng.
Dữ liệu vào:
Ø Dòng đầu tiên của input chứa một số tự nhiên T – số lượng test.
Ø Dòng đầu tiên của mỗi test chứa hai số nguyên N và M lần lượt là số chàng trai và số cô gái.
Ø N dòng tiếp theo, mỗi dòng gồm M ký tự hoặc ‘0’ hoặc ‘1’.
Dữ liệu ra:
Ø Với mỗi test, in ra một dòng chứa một số nguyên tương ứng
với số lượng xung đột trong bữa tiệc.
Ràng buộc:
Ø 1 ≤ T ≤ 100
Ø 1 ≤ N, M ≤ 10
Ví dụ:
Input
2
4 3
111
100
110
000
2 2
10
01
Output:
4
0
Giải thích:
Ví
dụ 1. Cả ba chàng trai đều thích cô gái
đầu tiên nên sẽ có những xung đột là (1,
2, 1), (1, 3, 1), (2, 3, 1). Chàng
trai 1 và 3 đều thích cô gái thứ hai nên sẽ có thêm một xung đột nữa. Chỉ có một chàng trai thích cô gái thứ ba nên
không có xung đột nào. Do đó có tất cả 4
xung đột.
Ví dụ 2. Với mỗi cô gái chỉ có một chàng trai thích, nên không có
xung đột nào.
