Recently, Karan gifted Ayush the latest Copytam Da's keyboard. He also gifted him an array of N distinct numbers.

The keyboard allows to you to copy any contiguous subsequence of the array and paste it in any position of the array.

After going back to his room, Ayush used this keyboard on the array. After using it for some time, he realized that he has messed up the original given array. Can you help him find the number of elements in the original array?

Input

The first line contains T, the number of test cases. The description of T test cases follows. Each test case contains 2 lines. The first line contains N, the number of elements in the messed-up array. The second line contains N space separated integers denoting the elements of the messed up array.

Output

For each test case, output a single line containing the answer.

Constraints

1 <= T <= 10

1 <= N <= 10^6

1 <= A[i] <= 10000