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