On the occasion of 66^th Republic day, a young lad, Lemon Kumar (a.k.a Yaar Kumar), is revising his speech again and again to remember it. He found that some of the letters in his
speech is repeated quite often. Being very fond of programming, like the Chef, he took it as a challenge and decided to find this letter. He decided that:

He will count the frequency of all English alphabets only and will consider upper case letters as lower case for counting.
If two letters have same frequency he will consider letter with high ASCII value.


As he is getting late for his speech so he
decided to appoint you to do this job for him. 

Input
First line contains the number of test cases T.
For each test case you are given a string(speech) containing any character in a single line.

Output
For each test case print a lower case letter on a single line whose frequency is maximum in his speech.

Constraints

1 ≤ T ≤ 100
1 ≤ Length of the speech ≤ 10^5


Example
Input:
1
Happy Republic Day!!!
Output:
p
import string
for _ in range(int(raw_input())):
    string=str(raw_input()).lower()
    punctuation=['!','@','#',' ','$','%','^','&','*','(',')','-','=','+','[',']',"'",';','/''1','2','3','4','5','6','','7','8','9','0']
    string1=[f for f in string if f not in punctuation]
    string=''.join(string1)
    dictionary={}
    for i in string:
        dictionary[i]=dictionary.get(i,0)+1
    maxvals=max(dictionary.values())
    new=[]
    for a,b in dictionary.items():
        if(b==maxvals):
            new.append(ord(a))
    print str(unichr(max(new)))