15
MIRZOYANOVECLOX
 23
AABBBAAACCCCCAAADDDDDDD
 2
QA
 11
GGRRAATTZZZ
 6
AZAZAZ
 10
SQSQSQSQTG
 3
KEK
 100
URXCAIZFIBNJTPCZHBQIBCILLPXZCFGMKKZMNPLCYGAVJVIBMCZEBSJWPSCPQDYCTTKPOKIJRSKIZPDGCHVOUTMPNECYORSFZFNC
 3
LOL
 2
WW
 8
PUTINVOR
 26
QWERTYUIOPASDFGHJKLZXCVBNM
 5
AZAZA
 9
EGORLETOV
 7
KADUROV
 9
MIKEPIDOR
 9
AAAAAAAAA
 100
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
 5
FUFEL
 50
NYQAHBYYOXLTRYQDMVENEMAQNBAKGLGQOLXNAIFNQTOCLNNQIA

MI
 DD
 QA
 ZZ
 AZ
 SQ
 KE
 IB
 LO
 WW
 PU
 QW
 AZ
 EG
 KA
 MI
 AA
 AA
 FU
 YQ

'''
1374b codeforces
def ans(n,count):
    c=count
    a=0
    if n==1 and c==0:
        return 0
    elif n==1 and c!=0:
        print(c)
        return c
    elif c==100:
        print("hi")
        return -1
    elif n%6==0:
        c+=1
        n=n/6
        a=ans(n,c)
    else:
        n=n*2
        c+=1
        a=ans(n,c)

for x in range(int(input())):
    n=int(input())
    s=0
    s=ans(n,0)
'''
from statistics import  mode
n=int(input())
a=input()
b=[]
i=len(a)
j=0
while j<i:
    if j<=i-2:
        b.append(str(a[j]) + str(a[j + 1]))
    j+=1
s=mode(b)
print(s)