Read problems statements in Mandarin Chinese and Russian as well. 

You had an array of integer numbers. You also had a beautiful operations called "Copy-Paste" which allowed you to copy any contiguous subsequence of your array and paste it in any position of your array. For example, if you have array [1, 2, 3, 4, 5] and copy it's subsequence from the second to the fourth element and paste it after the third one, then you will get [1, 2, 3, 2, 3, 4, 4, 5] array. You remember that you have done a finite(probably zero) number of such operations over your initial array and got an array A as a result. Unfortunately you don't remember the initial array itself, so you would like to know what could it be. You are interested by the smallest such array. So the task is to find the minimal size(length) of the array that A can be obtained from by using "Copy-Paste" operations. 
 
------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of elements in obtained array A. The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the array.
 
------ Output ------ 

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

$1 ≤ T ≤ 20$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{5}$
 
----- Sample Input 1 ------ 
2
5
1 1 1 1 1
5
1 2 3 1 2
----- Sample Output 1 ------ 
1
3
----- explanation 1 ------ 
In the first case we could have only array [1] in the beginning and then obtain [1, 1], then [1, 1, 1, 1] and finally [1, 1, 1, 1, 1]. In the second one we could obtain A from [1, 2, 3] by copying it's first two elements to the end.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures


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


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


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


t = int(input())
for i in range(t):
	n = int(input())
	a = set(input().split())
	l = len(a)
	print(l)


for i in range(int(input())):
	num = int(input())
	arr = list(map(int, input().split()))
	print(len(set(arr)))


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


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	hashm = {}
	for i in range(n):
		if nums[i] not in hashm:
			hashm[nums[i]] = 1
		else:
			hashm[nums[i]] += 1
	print(len(hashm))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mp = {}
	c = 0
	for i in arr:
		if i in mp:
			mp[i] += 1
		else:
			mp[i] = 1
			c += 1
	print(c)


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


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = dict(Counter(l))
	print(len(m))


q = int(input())
while q > 0:
	n = int(input())
	l = list(map(int, input().split()))
	l = set(l)
	l = list(l)
	print(len(l))
	q = q - 1


a = int(input())
for i in range(a):
	a1 = int(input())
	b = list(map(int, input().split()))
	c = set(b)
	print(len(c))


t = int(input())
for i in range(t):
	n = int(input())
	a = map(int, input().split())
	c = {}
	t = 0
	for j in a:
		if j in c:
			c[j] += 1
		else:
			c[j] = 1
			t += 1
	print(t)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = Counter(l)
	print(len(d))


b = int(input())
for i in range(b):
	N = int(input())
	a = list(map(int, input().split()))
	k = set()
	for i in a:
		k.add(i)
	print(len(k))


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


t = int(input())
for p in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	l1 = list(set(ar))
	mp = {}
	for i in ar:
		if i in mp:
			mp[i] += i
		else:
			mp[i] = 1
	c = 0
	for i in l1:
		if i in mp:
			c += 1
	print(c)


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


t = int(input())
for i in range(t):
	n = int(input())
	l = map(int, input().split())
	s = set(l)
	print(len(s))


from collections import Counter
T = int(input())
for i in range(T):
	n = int(input())
	lst = list(map(int, input().split()))
	lst1 = Counter(lst)
	c = 0
	for i in lst1.values():
		if i >= 1:
			c += 1
	print(c)


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


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


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	h = {}
	c = 0
	for i in range(n):
		if a[i] not in h:
			h[a[i]] = 1
			c = c + 1
	print(c)


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


t = int(input())
while t != 0:
	n = int(input())
	arr = list(map(int, input().split()))
	print(len(set(arr)))
	t -= 1


def hash(l):
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	return d
for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	d = hash(l)
	ans = list(d.keys())
	print(len(ans))


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	print(len(set(A)))


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


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


for _ in range(int(input())):
	n = int(input())
	c = 0
	l = list(map(int, input().split()))
	mp = {}
	for i in l:
		if i in mp:
			mp[i] += 1
		else:
			mp[i] = 1
			c += 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = set()
	l = 0
	for i in a:
		if i not in d:
			l += 1
			d.add(i)
	print(l)


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


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


def BanyakPasangNomorSama(N):
	A = sorted(N)
	banyak_sama = 0
	for x in range(1, len(N)):
		if A[x] == A[x - 1]:
			banyak_sama += 1
	return banyak_sama
banyak_kasus = int(input())
while banyak_kasus > 0:
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	print(N - BanyakPasangNomorSama(A))
	banyak_kasus -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = {}
	for i in l:
		if i in m:
			m[i] += 1
		else:
			m[i] = 1
	s = set(l)
	l1 = list(s)
	c = 0
	for j in l1:
		if j in m:
			c += 1
	print(c)