Sparing w Programowaniu Zespołowym Politechnika Poznańska, 16.04.2004

Opis

W pewnym państwie jest n miast. Niektóre miasta połączone są z innymi drogami. Powiemy, że 4 różne miasta a, b, c i d (oraz drogi je łączące) tworzą B-Czwórkę, jeśli istnieją drogi: od miasta a do b, od b do c, od c do d oraz od d do a. Mając dane miasta oraz łączące je drogi, oblicz ile jest różnych B-Czwórek w tym państwie. (Uwaga: Dwie B-Czwórki są różne jeśli składają się z różnych miast lub różnych dróg je łączących).

Specyfikacja wejścia

W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita oznaczająca liczbę następujących zestawów danych. W pierwszej każdego zestawu danych znajduje się 1 liczba całkowita: n (1 <= n <= 150) oznaczająca liczbę miast. W każdej z kolejnych n linii jest n cyfr oddzielonych spacjami. Jeśli i-ta cyfra w j-tej linii (a[i, j]) wynosi 1 oznacza to, że istnieje droga pomiędzy i-tym a j-tym miastem, natomiast 0 oznacza, że droga taka nie istnieje. (Uwaga: Nie istnieją drogi pomiędzy miastem a nim samym oraz zawsze a[i, j] = a[j, i]).

Specyfikacja wyjścia

Dla każdego zestawu danych Twój program powinien wypisać dokładnie jedną liczbę całkowitą oznaczającą liczbę B-Czwórek w tym państwie.

Przykład

2
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
4
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

3
1