There is an event in DUCS where boys get a chance to show off their skills to impress girls. The boy who impresses the maximum number of girls will be honoured with the title “Charming Boy of the year”.
There are $N$ girls in the department. Each girl gives the name of a boy who impressed her the most. You need to find the name of a boy who will be honoured with the title. 
If there are more than one possible winners, then the one with the lexicographically smallest name is given the title. 
It is guaranteed that each boy participating in the event has a unique name.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. 
- The first line of each test case contains an integer $N$ denoting the number of girls.
- The second line contains $N$ space-separated strings $S_1, S_2, \ldots, S_N$, denoting the respective names given by the girls.

-----Output-----
For each test case, print a single line containing a string — the name of the boy who impressed the maximum number of girls. In case of a tie, print the lexicographically smallest name.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 10^5$
- $1 \leq |S_i| \leq 10$, for each valid $i$
$(|S_i|$ is the length of the string $S_i)$
- For each valid $i$, $S_i$ contains only lowercase English alphabets
- Sum of $N$ over all the test cases is $\leq 10^6$

-----Subtasks-----
- 30 points: $1 \leq N \leq 100$
- 70 points: original constraints

-----Sample Input-----
2

10

john berry berry thomas thomas john john berry thomas john

4

ramesh suresh suresh ramesh   

-----Sample Output-----
john

ramesh

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = [i for i in input().split()]
	ll = []
	c = Counter(l)
	cc = []
	m = 0
	for (l, count) in c.most_common(len(l) - 1):
		if m == 0:
			ll.append(l)
			cc.append(count)
		if m == count:
			ll.append(l)
			cc.append(count)
		if count < m:
			break
		m = count
	k = set(cc)
	leng = len(list(k))
	if leng == 1:
		sor = sorted(ll)
		print(sor[0])
	else:
		print(ll[0])


testCase = int(input())
for _ in range(testCase):
	numBoys = int(input())
	finalList = []
	boysList = [i for i in input().split()]
	boysList.sort()
	while len(boysList) != 0:
		coun = boysList.count(boysList[0])
		finalList.append([boysList[0], coun])
		for _ in range(coun):
			boysList.remove(boysList[0])
	finalList.sort(key=lambda x: x[1])
	finalList.reverse()
	test = []
	name = []
	for (a, b) in finalList:
		if len(test) == 0:
			test.append(b)
			name.append(a)
		elif b in test:
			name.append(a)
			name.sort()
			name = [name[0]]
		else:
			break
	print(name[0])


t = int(input())
result = []
for i in range(t):
	n = int(input())
	names = input()
	names_list = names.split()
	unique_names = list(set(names_list))
	count = []
	for i in unique_names:
		counting = 0
		for j in names_list:
			if i == j:
				counting += 1
		count.append(counting)
	count_1 = 0
	for i in count:
		if i == max(count):
			count_1 += 1
	if count_1 == 1:
		result.append(unique_names[count.index(max(count))])
	else:
		a = []
		b = max(count)
		while max(count) == b:
			a.append(unique_names[count.index(max(count))])
			count[count.index(max(count))] = 0
		a.sort()
		result.append(a[0])
for i in result:
	print(i)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = sorted(list(map(str, input().split())))
	count = Counter(arr).most_common(1)
	print(max(count)[0])


from collections import Counter
T = int(input())
for _ in range(T):
	n = int(input())
	lists = list(map(str, input().split()))
	d = dict(Counter(lists))
	l = list(d.values())
	maxi = max(l)
	greatest = []
	for ele in d:
		if d[ele] == maxi:
			greatest.append(ele)
	greatest.sort()
	print(greatest[0])


T = int(input())
if T < 1 or T > 100:
	print('Exceeded testcases limit')
	return
sum = 0
for i in range(0, T):
	N = int(input())
	if N < 1 or N > 100000:
		print('Exceeded number of girls limit')
		return
	string = input()
	S = string.split()
	L = []
	for i in S:
		if len(i) < 1 or len(i) > 10:
			print('Exceeded string length limit')
			return
		L.append(i.lower())
	sum += N
	if sum > 1000000:
		print('Exceeded Sum of N over all the test cases limit')
		return
	lcount = []
	newlist = []
	for i in L:
		if i not in newlist:
			newlist.append(i)
			freq = L.count(i)
			lcount.append(freq)
	maximum = max(lcount)
	mostliked = []
	for i in range(0, len(lcount)):
		if lcount[i] == maximum:
			mostliked.append(newlist[i])
	mostliked.sort()
	print(mostliked[0])


from collections import Counter

def count(s):
	c = Counter(s)
	return c.most_common(1)[0][0]
t = int(input())
for i in range(t):
	n = int(input())
	s = sorted(list(map(str, input().split())))
	print(count(s))


for _ in range(int(input())):
	noOfGirls = int(input())
	boys = list(input().split())
	freq = dict()
	for j in boys:
		if j not in freq:
			freq[j] = 1
		else:
			freq[j] += 1
	occu = list(freq.values())
	occu.sort()
	answers = list()
	for (key, value) in freq.items():
		if value == occu[-1]:
			answers.append(key)
	if len(answers) != 1:
		answers.sort()
		print(*answers[0], sep='')
	else:
		print(*answers, sep='')


t = int(input())
i = 0
for i in range(t):
	n = int(input())
	a = list(map(str, input().split()))
	a.sort()
	z = set(a)
	q = list(z)
	q.sort()
	b = []
	k = 0
	for j in q:
		var = a.count(j)
		b.append(var)
	print(q[b.index(max(b))])


try:
	from collections import Counter
	for i in range(int(input())):
		n = int(input())
		l = list(map(str, input().split()))
		c = list(Counter(l).items())
		x = max(list(Counter(l).values()))
		y = []
		for (j, k) in c:
			if k == x:
				y.append(j)
		print(min(y))
except:
	pass


import collections

def CountFrequency(arr):
	return collections.Counter(arr)
for t in range(0, int(input())):
	n = int(input())
	arr = list(map(str, input().split()))
	freq = CountFrequency(arr)
	ans = ''
	cnt = 0
	for (key, value) in freq.items():
		if value > cnt:
			cnt = value
			ans = key
		elif value == cnt:
			if key < ans:
				ans = key
	print(ans)


for t in range(0, int(input())):
	n = int(input())
	ss = list(map(str, input().split()))
	my_dict = {}
	for i in ss:
		my_dict[i] = ss.count(i)
	ans = ''
	cnt = 0
	for (key, value) in my_dict.items():
		if value > cnt:
			cnt = value
			ans = key
		elif value == cnt:
			if key < ans:
				ans = key
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	s = input().split()
	s.sort()
	max = 0
	c = 1
	s1 = []
	for i in range(n - 1):
		if i == n - 2:
			if c == max:
				max = c
				s[i] = min(s[i], s1)
			if c > max:
				max = c
				s1 = s[i]
		if s[i] == s[i + 1]:
			c = c + 1
		elif s[i] != s[i + 1]:
			if c == max:
				max = c
				s[i] = min(s[i], s1)
			elif c > max:
				max = c
				s1 = s[i]
			c = 1
	print(s1)
	t = t - 1


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		names = list(input().split())
		f = set(names)
		maxi = 0
		dict = {i: 0 for i in f}
		for i in names:
			dict[i] += 1
			if dict[i] > maxi:
				name = i
				maxi = dict[i]
			elif dict[i] == maxi:
				if i < name:
					name = i
		print(name)
except Exception:
	pass


for t in range(0, int(input())):
	n = int(input())
	ss = list(map(str, input().split()))
	unique_words = set(ss)
	ans = ''
	cnt = 0
	for i in unique_words:
		x = ss.count(i)
		if x > cnt:
			cnt = x
			ans = i
		elif x == cnt:
			if i < ans:
				ans = i
	print(ans)


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		names = list(input().split())
		f = set(names)
		dict = {i: 0 for i in f}
		for i in names:
			dict[i] += 1
		name = min([i for i in names if dict[i] == max(dict.values())])
		print(name)
except Exception:
	pass


tests = int(input())
for te in range(tests):
	n = int(input())
	strings = list(input().split())
	dic = {}
	for i in range(n):
		if strings[i] not in dic:
			dic[strings[i]] = 1
		else:
			dic[strings[i]] += 1
	maxa = -1
	for i in list(dic.keys()):
		if dic[i] > maxa:
			ans = i
			maxa = dic[i]
		if dic[i] == maxa:
			ans = min(ans, i)
	print(ans)