Efficient Algotithms 2022

Mamy N pokojów ponumerowanych liczbami 1, 2 ... N. W każdym pokoju znajduje się obraz, na którym jest namalowana pewna liczba ze zbioru {1, 2 ... N}. Ponadto w każdym pokoju znajduje się jeden człowiek. Co minutę rozlega się dzwonek (słyszany jednocześnie w każdym pokoju) i na jego dźwięk każdy człowiek czyta liczbę z obrazu, który wisi w pokoju, w którym się znajduje i teleportuje się do pokoju oznaczonego tym numerem. Chociaż na początku w każdym pokoju jest jedna osoba, to już po pierwszej iteracji tak wcale być nie musi — niektóre pokoje mogą być puste. W ogólności liczba zajętych pokojów może się zmieniać z minuty na minutę. Jednak, jak można udowodnić, w końcu liczba zajętych pokojów ustali się i nigdy więcej się już nie zmieni, mimo faktu, iż ludzie ciągle się będą przemieszczać.

Twoim zadaniem jest, na podstawie liczby pokojów N oraz liczb wymalowanych w poszczególnych pokojach, stwierdzić jaka będzie ta ostateczna liczba zajętych pokojów.

Wejście.

W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 < d < 10), określająca liczbę zestawów danych, których opisy umieszczone są kolejno po sobie w następnych liniach pliku. Opis pojedynczego zestawu jest następujący: W pierwszej linii znajduje się liczba naturalna n (2 < n < 10000) określająca liczbę pokojów. W drugiej linii znajduje się n liczb naturalnych a1, a2 ... an (ze zbioru liczb {1, 2 ... n}) określających liczby wypisane w kolejnych pokojach.

Wyjście.

Każdemu zestawowi w pliku wejściowym powinna odpowiadać jedna linia pliku wyjściowego. Ta linia powinna zawierać jedną liczbę naturalną określającą ostateczną liczbę zajętych pokojów.

Example

Input:
3
5
1 1 1 2 2
5
5 1 2 4 3
5
2 3 2 1 4

Output:
1
5
2

Wyjaśnienie

Pierwsze sześć minut symulacji dla ostatniego zestawu (2 3 2 1 4) zostało przedstawione na rysunku poniżej:

W pierwszej kolumnie przedstawione są liczby wymalowane w kolejnych pokojach. W kolejnych kolumnach przedstawiony jest stan pokojów w kolejnych "turach" - jedna kropka reprezentuje jednego człowieka. W dalszych turach (nie pokazanych na rysunku) liczba zajętych pokojów nie ulega zmianie - ludzie z pokojów nr 2 i 3 zamieniają się miejscami co minutę. Odpowiedzią jest więc 2.

We have N rooms 1, 2 ... N. In each room there is a picture on which some number from the set {1, 2 ... N}. Furthermore, there is one person in each room. Every minute, a bell rings (heard simultaneously in each room) and at the sound of the bell, each person reads a number from the painting in the room he is in and teleports to the room marked with that number. Although initially there is one person in each room, after the first iteration this need not be the case at all - some rooms may be empty. In general, the number of occupied rooms can change from minute to minute. However, as you can prove, eventually the number of occupied rooms will settle down and never change again, despite the fact that people keep moving around.

Your task is to determine, on the basis of the number of rooms N and the numbers painted in each room, what that final number of occupied rooms will be.

Input

In the first line of the input file there is a natural number d (1 < d < 10), specifying the number of sets of data whose descriptions are placed one after another in the following lines. The description of a single set is as follows: The first line contains a natural number n (2 < n < 10000) specifying the number of rooms. In the second line there are n natural numbers a1, a2 ... an (from the set of numbers {1, 2 ... n}) defining the numbers written in the following rooms.

Output

Each set in the input file should correspond to one line of the output file. This line should contain one natural number denoting the final number of occupied rooms.

Example

Input:
3
5
1 1 1 2 2
5
5 1 2 4 3
5
2 3 2 1 4

Output:
1
5
2

Explanation

The first six minutes of the simulation for the last set (2 3 2 1 4) are shown in the figure below:

The first column shows the numbers painted in the subsequent rooms. The following columns present the status of rooms in subsequent "turns" - one dot represents one person. In further turns (not shown in the figure), the number of occupied rooms does not change - people from rooms 2 and 3 exchange places every minute. So the answer is 2.