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

Difficulty: interview

Starter code:

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)
        else:
            if 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)



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 z in finalList:
        if len(test)==0:
            test.append(z[1])
            name.append(z[0])
        else:
            if z[1] in test:
                name.append(z[0])
                name.sort()
                name=[name[0]]
            else:
                break
    # if len(name)>1:
    #     name.sort()
    #     print(name[0])
    # else:
    print(name[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 z in finalList:
        if len(test)==0:
            test.append(z[1])
            name.append(z[0])
        else:
            if z[1] in test:
                name.append(z[0])
            else:
                break
    if len(name)>1:
        name.sort()
        print(name[0])
    else:
        print(name[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:
        name=boysList[0]
        coun=boysList.count(boysList[0])
        finalList.append([boysList[0],coun])
        while name in boysList: boysList.remove(name)

    finalList.sort(key=lambda x:x[1])
    finalList.reverse()
    test=[]
    name=[]
    for z in finalList:
        if len(test)==0:
            test.append(z[1])
            name.append(z[0])
        else:
            if z[1] in test:
                name.append(z[0])
            else:
                break
    if len(name)>1:
        name.sort()
        print(name[0])
    else:
        print(name[0])






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])


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 z in finalList:
        if len(test)==0:
            test.append(z[1])
            name.append(z[0])
        else:
            if z[1] in test:
                name.append(z[0])
            else:
                break
    if len(name)>1:
        name.sort()
        print(name[0])
    else:
        print(name[0]  )






# cook your dish here
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])
   


# cook your dish here
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))
   

    



# cook your dish here
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])

# cook your dish here
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='')

# cook your dish here

t=int(input())
i=0
for i in range(t):
    n=int(input())
    a=list(map(str,input().split()))
    a.sort()
    z=set(a)
    #print(z)
    q=list(z)
    q.sort()
    #print(q)
    b=[]
    k=0
    #print(max(a))
    for j in q:
        var=a.count(j)
        b.append(var)
        #b[k].append(a.count(j))
        
        #k+=1
    
    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)

# cook your dish here
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

# cook your dish here
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
            
        #name = min([i for i in names if dict[i] == max(dict.values())])
        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)

# cook your dish here
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])

# cook your dish here
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


# cook your dish here

tests = int(input())
for te in range(tests):
    n = int(input())
    strings = list(input().split())
    #print(strings)
    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)
    


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:
    if ss.count(i)>cnt :
      cnt=ss.count(i)
      ans=i
    elif ss.count(i)==cnt:
      if i < ans:
        ans=i
  
  print(ans)