Autostrady

Zadanie znalazło się na naszym serwisie dzięki uprzejmości organizatorów Akademickich Mistrzostw Polski w Programowaniu Zespołowym 2007 (http://amppz.cs.put.poznan.pl).

Rząd Krainy Po Drugiej Strony Lustra zapowiedział, że zbuduje rozległą sieć dróg szybkiego ruchu. Stworzono więc jej projekt. Zgodnie z projektem, drogi będą dwukierunkowe i każda będzie iden- tyfikowana unikalnym numerem. Każda droga będzie łączyła dwa różne ronda, a dwa ronda będzie łączyła maksymalnie jedna droga. Drogi nie będą się przecinać – zaprojektowano tunele i mosty. Zapowiedzi budowy dróg ucieszyły Gang Wyścigów Nielegalnych (GWN). Członkowie GWN orga- nizują raz na jakiś czas nielegalne wyścigi. Aby przeprowadzić wyścig potrzeba dokładnie czterech połączonych dróg. Drogi te tworzą tor wyścigowy. Tor wyścigowy musi zawierać dokładnie pięć różnych rond (w szczególności, rondo początkowe musi być różne od końcowego). Niestety, członkom gangu brody już urosły, a dróg jak nie ma tak nie ma. Czekając na wy- budowanie dróg, członkowie GWN postanowili więc policzyć, ile różnych wyścigów będą mogli w przyszłości przeprowadzić. Dwa wyścigi uznają za różne, jeśli tory wyścigowe się różnią. Tory wy- ścigowe uznaje się za różne, jeśli różnią się numerem przynajmniej jednej z dróg, które wchodzą w ich skład. Tobie, jako jedynemu zinformatyzowanemu członkowi GWN przypadło zaszczytne zadanie na- pisania programu, który szybko znajdzie liczbę różnych wyścigów, które gang będzie mógł w (raczej dalekiej) przyszłości przeprowadzić.

Specyfikacja wejścia

W pierwszej linii znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę testów. Pierwsza linia testu zawiera liczby n i m (1 ≤ n ≤ 200; 0 ≤ m ≤ n(n − 1)/2), gdzie n oznacza liczbę rond, a m liczbę dróg. W każdej z kolejnych m linii znajdują się liczby u, v (1 ≤ u, v ≤ n), oznaczające, że rondo o numerze u jest połączone drogą z rondem o numerze v.

Specyfikacja wyjścia

Dla każdego testu, wypisz w osobnej linii liczbę różnych wyścigów, które da się przeprowadzić dla danego projektu sieci dróg.

Przykład

Wejście
2
5 4
1 2
2 3
3 4
4 5
3 3
1 2
2 3
3 1
Wyjście
1
0