Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BTURN - Bajtlandzki turniej

W Bajtlandii rozegrano turniej pomiędzy n graczami. Każdy uczestnik grał dokładnie raz z każdym innym uczestnikiem, a każda gra zakończyła się zwycięstwem dokładnie jednego z graczy. Każdy z uczestników ma swój unikalny numer startowy (będący liczbą całkowitą pomiędzy 1 a n) oraz unikalny numer rankingowy (będący liczbą całkowitą z tego samego zakresu).

Następnego dnia po turnieju Dziennik Bajtlandzki opublikował wyniki wszystkich gier według numerów startowych uczestników, jako listę n*(n-1)/2 linii postaci uczestnik nr i wygrał z uczestnikiem nr j. Głos Bajtlandii opublikował analogiczną listę, ale używając przy tym nie numerów startowych uczestników, lecz ich numerów rankingowych. Co ciekawe, listy w obu gazetach wyglądały identycznie.

Znając numery startowe i rankingowe poszczególnych uczestników, Twoim zadaniem jest określić liczbę możliwych wyników turnieju. Dwa wyniki uważamy za różne, jeżeli w jednym przypadku pewien uczestnik A wygrał z uczestnikiem B, a w drugim przypadku przegrał z tym samym uczestnikiem turnieju.

Wejście

 

W pierwszej linii wejścia podana jest liczba przypadków testowych t (t<=20). Każdy przypadek testowy rozpoczyna się od linii zawierającej liczbę graczy n (1<=n<=10000). W następnych n liniach podane są numery rankingowe graczy o kolejnych numerach startowych.

Wyjście

Dla każdego przypadku testowego, wypisz linię zawierającą resztę z dzielenia przez 1000 liczby możliwych wyników turnieju.

Przykład

Wejście:
1 
4 
2 
4 
3 
1

Wyjście:
4

Dodane przez:adrian
Data dodania:2006-05-28
Limit czasu wykonania programu:1.759s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Kashyap / FIPC
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.