Chef is fan of pairs and he likes all things that come in pairs. He even has a doll collection in which the dolls come in pairs. One day while going through his collection he found that there are odd number of dolls. Someone had stolen a doll!!!  
Help chef find which type of doll is missing..

------ Input ------ 

The first line contains an integer T, the number of test cases. 

The first line of each test case contains an integer N, the number of dolls. 

The next N lines are the types of dolls that are left.

------ Output ------ 

For each test case, display the type of doll that doesn't have a pair, in a new line.

------ Constraints ------ 

1≤T≤10 

1≤N≤100000 (10^{5}) 

0≤type≤100000 

----- Sample Input 1 ------ 
1
3
1 
2
1
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 

----- Sample Input 2 ------ 
1
5
1
1
2
2
3
----- Sample Output 2 ------ 
3
----- explanation 2 ------

Difficulty: EASY
Tags: Number theory

Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
T = int(input())
for i in range(T):
	N = int(input())
	a = []
	for j in range(N):
		a.append(int(input()))
	for j in a:
		if a.count(j) % 2 == 1:
			print(j)
			break


for i in range(int(input())):
	n = int(input())
	z = []
	for j in range(n):
		z.append(int(input()))
	for j in z:
		if z.count(j) % 2 == 1:
			print(j)
			break


for t in range(int(input())):
	n = int(input())
	li = []
	for i in range(n):
		a = int(input())
		if a in li:
			li.remove(a)
		else:
			li.append(a)
	print(li[0])


a = int(input(''))
for t in range(0, a):
	n = int(input())
	b = []
	for i in range(n):
		m = int(input())
		if m in b:
			b.remove(m)
		else:
			b.append(m)
	for a in b:
		print(a)


n = int(input())
for i in range(0, n):
	a = int(input())
	l = []
	for w in range(a):
		m = int(input())
		if m not in l:
			l.append(m)
		else:
			l.remove(m)
	for ans in l:
		print(ans)


vp = int(input())
for i in range(vp):
	k = int(input())
	list = []
	for j in range(k):
		tc = int(input())
		if tc in list:
			list.remove(tc)
		else:
			list.append(tc)
	print(list[0])


from collections import Counter
T = int(input())
for _ in range(T):
	N = int(input())
	dolls = [int(input()) for j in range(N)]
	freq = Counter(dolls)
	for doll in set(dolls):
		if freq[doll] % 2 == 1:
			print(doll)
			break


t = int(input())
while t > 0:
	d = int(input())
	l = []
	for i in range(d):
		l.append(int(input()))
	for j in l:
		if l.count(j) % 2 == 1:
			print(j)
			break
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	count = 0
	nums = []
	for c in range(n):
		k = int(input())
		nums.append(k)
	for j in nums:
		if nums.count(j) % 2 != 0:
			print(j)
			break


for _ in range(int(input())):
	n = int(input())
	l = []
	for j in range(n):
		l.append(int(input()))
	for j in l:
		if l.count(j) % 2 == 1:
			print(j)
			break


t = int(input())
for _ in range(t):
	n = int(input())
	doll_count = {}
	for i in range(n):
		doll_type = input().strip()
		if doll_type in doll_count:
			doll_count[doll_type] += 1
		else:
			doll_count[doll_type] = 1
	for (doll_type, count) in doll_count.items():
		if count % 2 != 0:
			print(doll_type)
			break


for _ in range(int(input())):
	N = int(input())
	doll = list()
	for i in range(0, N):
		doll.append(int(input()))
	for j in doll:
		if doll.count(j) % 2 == 1:
			print(j)
			break


from collections import Counter
for _ in range(int(input())):
	l = []
	for j in range(int(input())):
		l.append(int(input()))
	z = Counter(l).items()
	ans = []
	for i in z:
		if i[1] % 2 == 0:
			pass
		else:
			ans.append(i[0])
	print(*ans)


for i in range(int(input())):
	a = int(input())
	l1 = []
	for i in range(a):
		l1.append(int(input()))
	for i in l1:
		if l1.count(i) % 2 == 1:
			print(i)
			break


t = int(input())
if 1 <= t and t <= 10:
	for i in range(t):
		n = int(input())
		p = 0
		for j in range(n):
			k = int(input())
			p ^= k
		print(p)


for i in range(int(input())):
	n = int(input())
	l1 = []
	for i in range(n):
		a = int(input())
		if a in l1:
			l1.remove(a)
		else:
			l1.append(a)
	print(l1[0])


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(int(input()))
	for j in arr:
		if arr.count(j) % 2 == 1:
			print(j)
			break


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for i in range(n):
		a = int(input())
		l.append(a)
	for j in l:
		if l.count(j) % 2 == 1:
			print(j)
			break


t = int(input())
while t:
	s = []
	for i in range(int(input())):
		s.append(int(input()))
	x = 0
	for j in s:
		x = x ^ j
	print(x)
	t = t - 1


T = int(input())
for i in range(T):
	N = int(input())
	list = []
	for i in range(N):
		list.append(int(input()))
	for i in list:
		if list.count(i) % 2 == 1:
			print(i)
			break


t = int(input())
for i in range(t):
	n = int(input())
	dolls = {}
	for j in range(n):
		doll_type = int(input())
		if doll_type not in dolls:
			dolls[doll_type] = 1
		else:
			dolls[doll_type] += 1
	for (doll_type, count) in dolls.items():
		if count % 2 == 1:
			print(doll_type)
			break


import collections
c = 0
t = int(input())
for i in range(t):
	n = int(input())
	list1 = []
	for i in range(n):
		list1.append(int(input()))
	a = collections.Counter(list1)
	for i in a.keys():
		if a[i] % 2 != 0:
			print(i)


for _ in range(int(input())):
	n = int(input())
	c = []
	for i in range(n):
		c.append(int(input()))
	for j in set(c):
		if c.count(j) % 2 == 1:
			print(j)
			break


for i in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(int(input()))
	for i in l:
		if l.count(i) % 2 == 1:
			print(i)
			break


T = int(input())
for t in range(T):
	n = int(input())
	l = []
	for j in range(n):
		l.append(int(input()))
	for j in l:
		if l.count(j) % 2 == 1:
			print(j)
			break


for _ in range(int(input())):
	A = []
	for i in range(int(input())):
		elem = int(input())
		if A.count(elem):
			A.remove(elem)
		else:
			A.append(elem)
	print(*A)


t = int(input())
while t:
	n = int(input())
	dict1 = {}
	for i in range(n):
		k = int(input())
		if not dict1.get(k):
			dict1[k] = 1
		else:
			dict1[k] += 1
	for (key, value) in dict1.items():
		if value % 2 != 0:
			print(key)
			break
	t -= 1


for i in range(int(input())):
	c = 0
	l = []
	for j in range(int(input())):
		d = int(input())
		if d not in l:
			l.append(d)
		else:
			l.remove(d)
	print(l[0])


n = int(input())
for i in range(1, n + 1):
	a = int(input())
	l = []
	for i in range(1, a + 1):
		b = int(input())
		l.append(b)
	s = set(l)
	for i in s:
		if l.count(i) % 2 != 0:
			print(i)


for i in range(int(input())):
	li = []
	for j in range(int(input())):
		a = int(input())
		li.append(a)
	for k in li:
		if li.count(k) % 2 == 1:
			print(k)
			break


for _ in range(int(input())):
	n = int(input())
	l = []
	for _ in range(n):
		i = int(input())
		l.append(i)
	for i in range(n):
		if l.count(l[i]) % 2 != 0:
			print(l[i])
			break


for _ in range(int(input())):
	n = int(input())
	listOfDolls = []
	for i in range(n):
		listOfDolls.append(int(input()))
	for i in listOfDolls:
		if listOfDolls.count(i) % 2 == 1:
			print(i)
			break


for i in range(int(input())):
	n = int(input())
	l = []
	for j in range(n):
		a = int(input())
		l.append(a)
	for k in l:
		if l.count(k) % 2 != 0:
			print(int(k))
			break


n = int(input())
for i in range(1, n + 1):
	a = int(input())
	l = []
	for k in range(a):
		m = int(input())
		if m not in l:
			l.append(m)
		else:
			l.remove(m)
	for z in l:
		print(z)


T = int(input())
while T > 0:
	N = int(input())
	l = list()
	for i in range(0, N):
		a = int(input())
		l.append(a)
	s = set(l)
	for i in s:
		if l.count(i) % 2 != 0:
			print(i)
	T -= 1


for _ in range(int(input())):
	l = []
	for i in range(int(input())):
		x = int(input())
		l.append(x)
	m = set(l)
	for i in m:
		if l.count(i) % 2 == 1:
			print(i)
			break


for i in range(int(input())):
	l = []
	for i in range(int(input())):
		d = int(input())
		if d not in l:
			l.append(d)
		else:
			l.remove(d)
	for i in l:
		print(i)


t = int(input())
for i in range(t):
	n = int(input())
	list = []
	for j in range(n):
		list.append(int(input()))
	for j in list:
		if list.count(j) % 2 == 1:
			print(j)
			break


t = int(input())
for i in range(t):
	a = int(input())
	b = []
	for i in range(a):
		c = int(input())
		if c not in b:
			b.append(c)
		elif c in b:
			b.remove(c)
	for i in b:
		print(i)


from collections import Counter
t = int(input())
for __ in range(t):
	d = int(input())
	dolls = []
	for _ in range(d):
		dolls.append(int(input()))
	c = Counter(dolls)
	for j in c:
		if c[j] % 2 != 0:
			print(j)


t = int(input())
for i in range(t):
	n = int(input())
	res = 0
	for j in range(n):
		res ^= int(input())
	print(res)


N = int(input())
for k in range(N):
	s = int(input())
	l = []
	for j in range(s):
		l.append(int(input()))
	for j in l:
		if l.count(j) % 2 == 1:
			print(j)
			break


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append(int(input()))
	s = set(a)
	for i in s:
		if a.count(i) % 2 != 0:
			print(i)
			break


t = int(input())
for i in range(t):
	leng = int(input())
	lst1 = []
	for j in range(leng):
		a = int(input())
		lst1.append(a)
	s = set(lst1)
	for k in s:
		if lst1.count(k) % 2 != 0:
			print(k)
			break


t = int(input())
for i in range(t):
	n = int(input())
	A = []
	for i in range(n):
		A.append(int(input()))
	for i in A:
		if A.count(i) % 2 == 1:
			print(i)
			break


def find_missing_doll(n, dolls):
	xor = 0
	for i in range(n):
		xor ^= dolls[i]
	return xor
t = int(input())
for _ in range(t):
	n = int(input())
	dolls = []
	for i in range(n):
		dolls.append(int(input()))
	print(find_missing_doll(n, dolls))


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l1 = []
	for i in range(0, n):
		t = int(input())
		l1.append(t)
	c = Counter(l1)
	for i in c:
		if l1.count(i) % 2 == 1:
			print(i)
			break


s = int(input())
for i in range(s):
	a = int(input())
	l = []
	for j in range(a):
		b = int(input())
		l.append(b)
	cache = {}
	for k in l:
		if k in cache:
			cache[k] += 1
		else:
			cache[k] = 1
	for p in cache.keys():
		if cache[p] % 2 != 0:
			print(p)


for _ in range(int(input())):
	n = int(input())
	c = []
	count = 0
	for _ in range(n):
		d = int(input())
		c.append(d)
	for i in c:
		if c.count(i) % 2 == 1:
			print(i)
			break


t = int(input())
for i in range(t):
	n = int(input())
	Input = []
	for j in range(n):
		d = int(input())
		Input.append(d)
		Input.sort()
	s = set(Input)
	for a in s:
		if Input.count(a) % 2 == 1:
			print(a)
			break


for _ in range(int(input())):
	n = int(input())
	dic = {}
	for i in range(n):
		j = int(input())
		if j not in dic:
			dic[j] = 1
		else:
			dic[j] += 1
	for i in dic:
		if dic[i] % 2 == 1:
			print(i)
			break