t = int(input())
l=[]
for _ in range(t):
    l.append(int(input()))
for i in l:
    cnt=0
    for j in range(1,i+1):
        if i%j==0 and i!=0:
            i-=j
            cnt+=1
    if (i==0):
        print(cnt)
    else:
        print(-1)
            
        
        
