Ehab has an array $a$ of length $n$. He has just enough free time to make a new array consisting of $n$ copies of the old array, written back-to-back. What will be the length of the new array's longest increasing subsequence?

A sequence $a$ is a subsequence of an array $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements. The longest increasing subsequence of an array is the longest subsequence such that its elements are ordered in strictly increasing order.


-----Input-----

The first line contains an integer $t$ — the number of test cases you need to solve. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$) — the number of elements in the array $a$.

The second line contains $n$ space-separated integers $a_1$, $a_2$, $\ldots$, $a_{n}$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.

The sum of $n$ across the test cases doesn't exceed $10^5$.


-----Output-----

For each testcase, output the length of the longest increasing subsequence of $a$ if you concatenate it to itself $n$ times.


-----Example-----
Input
2
3
3 2 1
6
3 1 4 1 5 9

Output
3
5



-----Note-----

In the first sample, the new array is $[3,2,\textbf{1},3,\textbf{2},1,\textbf{3},2,1]$. The longest increasing subsequence is marked in bold.

In the second sample, the longest increasing subsequence will be $[1,3,4,5,9]$.

Difficulty: interview

Starter code:

Solutions:
#list(map(int,input().split()))
t=int(input())
for _ in range(t):
    n=int(input())
    it=list(map(int,input().split()))
    print(len(set(it)))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	print(len(set(a)))

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    input()
    print(len(set(map(int, input().split()))))


a = int(input())
for i in range(a):
    o = int(input())
    u = list(map(int, input().split()))
    print(len(set(u)))

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    set_ = set(a)
    print(len(set_))



for _ in range(int(input())):
	n=int(input())
	a=list(map(int,input().split()))
	print(len(set(a)))

for nt in range(int(input())):
	n=int(input())
	l=list(map(int,input().split()))
	l=set(l)
	l=list(l)
	print (len(l))

#!/usr/bin/env python
#-*- coding:utf-8 -*-

# Code by H~$~C

from sys import stdin
input = stdin.readline
import math

for i in range(int(input())):
  n = int(input())
  arr = sorted(list(map(int, input().split())))
  ans = n
  for j in range(n - 1):
    if (arr[j + 1] == arr[j]):
      ans -= 1
  print(ans)

t = int(input())

for _ in range(t):
    n = int(input())
    a = list(map(int, input().strip().split()))

    print(len(set(a)))

t = int(input())
while(t):
    t -= 1
    n = int(input())
    a = set(map(int, input().split()))
    print(len(a))

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = len(set(a))
    print(ans)

t = int(input())
for i in range(t):
    solve()


t = int(input())
for _ in range(t):
	n = int(input())
	a = set(map(int, input().split()))
	print(len(a))

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
#sys.setrecursionlimit(100000)

for i in range(int(data())):
    n=int(data())
    A=set(mdata())
    print(len(A))

from sys import stdin,stdout                           #
import math                                            #
import heapq                                           #
                                                       #
t = 1                                                  #
def aint():                                            #
	return int(input().strip())                        #
def lint():                                            #
	return list(map(int,input().split()))              #
def fint():                                            #
	return list(map(int,stdin.readline().split()))     #
                                                       #	
########################################################

def main():
	n=aint()
	l=lint()
	print(len(set(l)))
	#solve

t=int(input())

########################################################
for i in range(t):                                     #
	main()                                             #

import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n=int(input())
    A=list(map(int,input().split()))
    print(len(set(A)))