W Bajtocji postanowiono zorganizować wyścigi formuły 1. Oczywiście, jak to zwykle bywa z Bajtocji, postanowiono ulepszyć sposób organizacji tych zawodów. Aby nie dochodziło do, jakże częstych podczas takich wyścigów wypadków, postanowiono, że każdy zawodnik będzie startował z innego miasta, ale każdy będzie jeździł i tak tą samą trasą, bo wszyscy będą jeździć w kółko, po prostu mijając punkty startowe przeciwników. Tak się akurat złożyło, że liczba n miast w Bajtocji dokładnie odpowiada liczbie zawodników startujących w wyścigu, a liczba ustalonych okrążeń była tą liczbą podniesioną do kwadratu. Naczelnemu informatykowi w Bajtocji postawiono za zadanie wytyczenia trasy wyścigu. Po tym jak to zrobił w każdym mieście ustawiono odpowiednie znaki, które kierowały kierowcę bolidu na odpowiednią autostradę do jakiegoś miasta. Na szczęście organizatorów, tuż przed startem ktoś zauważył, że znaki ustawione w poszczególnych miastach, wcale nie wyznaczają trasy, takiej, jak to było zaplanowane, tzn. znaki nie wytyczały trasy w sposób, w jaki nakazano ją ustalić informatykowi, tylko było poustawiane zupełnie pseudolosowo. Nie było już czasu, aby ich zmieniać, ale, żeby nie było całkowitej klapy, postanowiono, że publiczność będzie rozstawiona tylko w miastach, przez które będą jeszcze przejeżdżały samochody podczas jednego z ostatnich n okrążeń. Nowe okrążenia zdefiniowano po prostu jako przejechanie dwa razy przez to samo miasto. Poprzedniego informatyka, po takiej wpadce, natychmiast zwolniono z pracy, a zadanie ustalenia miast, w których trzeba rozstawić trybuny powierzono Tobie. Organizatorzy wzięli na siebie ustalenie dla każdego zawodnika mety, aby każdy przejechał, jeśli nie równą, to przynajmniej zbliżoną ilość kilometrów.

Zadanie
Na podstawie znaków rozstawionych w poszczególnych miastach, wskaż liczbę miast, w których przynajmniej jeden samochód pojawi się przynajmniej raz w czasie ostatnich n okrążeń.

Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita, oznaczająca liczbę zestawów danych, które za chwilę pojawią się na wejściu. W pierwszej linii zestawu znajduje się liczba n (2<=n<=10000) oznaczająca ilość zawodników startujących w zawodach, ilość miast w Bajtocji oraz pierwiastek ilości okrążeń wykonanych przez każdego zawodnika. W drugiej linii znajduje się n liczb naturalnych z przedziału od 1 do n, gdzie i-ta liczba oznacza numer miasta, na jaki wskazują znaki w i-tym mieście, jako następny etap wyścigu.

Wyjście
Odpowiedzią jest jedna liczba naturalna określającą liczbę miast, w których trzeba ustawić trybuny dla widzów.

Przykład

wejście:
3
5
1 1 1 2 2
5
5 1 2 4 3
5
2 3 2 1 4

wyjście:
1
5
2