백준 2777 숫자 놀이

https://www.acmicpc.net/problem/2777

2777번: 숫자 놀이

T = int(input())
l = [i for i in range(9,1,-1)]
result = []
for i in range(T):
    N = int(input())
    if N == 1:
        result.append(N)
    else:
        cnt=0
        c=0
        while(1):
            if cnt==8:
                result.append(-1)
                break
            if N==1:
                result.append(c)
                break
            cnt=0
            for i in range(8):
                if N%l[i]==0:
                    N = N//l[i]
                    c+=1
                    break
                else:
                    cnt+=1
    
for i in range(T):
    print(result[i])