Chef Two and Chef Ten are playing a game with a number $X$. In one turn, they can multiply $X$ by $2$. The goal of the game is to make $X$ divisible by $10$.
Help the Chefs find the smallest number of turns necessary to win the game (it may be possible to win in zero turns) or determine that it is impossible.

-----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 and only line of each test case contains a single integer denoting the initial value of $X$. 

-----Output-----
For each test case, print a single line containing one integer — the minimum required number of turns or $-1$ if there is no way to win the game.

-----Constraints-----
- $1 \le T \le 1000$
- $0 \le X \le 10^9$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
3
10
25
1

-----Example Output-----
0
1
-1

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
t=int(input())
for i in range(t):
 x=int(input())
 if x%10==0:
  print(0)
 elif x%5==0:
  print(1)
 else:
  print(-1)

t=int(input())
for i in range(t):
 n=int(input())
 if n%10==0:
  print(0)
 elif n%5==0:
  print(1)
 else: 
  print(-1)
  


# cook your dish here
b=int(input())
for i in range(b):
 a=int(input())
 if(a%10==0):
  print(0)
 elif(a%5==0):
  print(1)
 else:
  print(-1)


# cook your dish here
T = int(input())
for i in range(T):
 X = int(input())
 if(X % 10 == 0):
  print(0)
 elif(X % 5 == 0):
  print(1)
 else:
  print(-1)


t=int(input())
for ss in range(t):
 n=int(input())
 c=0
 if(n%10==0):
  c=1
  print(0)
 elif(n%10!=0):
  for i in range(1,11):
   if((n*(2**i))%10==0):
    c=1
    print(i)
    break
 if(c==0):
  print(-1)
 
   


# cook your dish here
test_case = int(input())
for i in range(test_case):
 num = int(input())
 if (num % 10 == 0):
  print('0')
 elif (num * 2 % 10 == 0):
  print('1')
 else:
  print('-1')

t = int(input())
for _ in range(t):
 num = int(input())
 if num%5 != 0:
  print(-1)
  continue
 count = 0
 while True:
  if num%10 == 0:
   break
  num*=2
  count+=1
 print(count)

for _ in range(int(input())):
 n= int(input())
 print(0) if n%10==0 else print(1) if n%5==0 else print(-1)


# cook your dish here
try:
 for t in range(int(input())):
  x = int(input())
  count = -1
  if x % 10 == 0:
   count += 1
  elif x % 5 == 0:
   count = 1
  else:
   count = -1
  print(count)
except: pass

t = int(input())

for _ in range(t):
 n = int(input())
 steps=-1
 if (n%10==0):
  steps+=1
 elif ((n%5)==0):
  steps=1
 else:
  steps = -1
 print(steps)

for _ in range(int(input())):
 n=int(input())
 if n%10==0:
  print("0")
 elif n%5==0:
  print("1")
 else:
  print("-1")


for _ in range(int(input())):
 n= int(input())
 print(0) if n%10==0 else print(1) if n%5==0 else print(-1)


# cook your dish here
# cook your dish here
t=int(input())
for i in range(t):
 n=int(input())
 if n%10==0:
  print(0)
 elif n%5==0:
  print(1)
 else:
  print(-1)


# cook your dish here
t=int(input())
for i in range(t):
 n=int(input())
 if n%10==0:
  print(0)
 elif n%5==0:
  print(1)
 else:
  print(-1)


for _ in range(int(input())):
 n=int(input())
 print(0) if n%10==0 else print(1) if n%5==0 else print(-1)

for _ in range(int(input())):
 num=int(input())
 if (num%10==0):
  ans=0
 elif num%5==0:
  ans=1
 else:
  ans=-1
 print(ans)

for i in range (int(input())):
 n=int(input())
 if n%5==0:
  if n%10==0:
   print(0)
  else:
   print(1)
 else:
  print((-1))# cook your dish here


# cook your dish here
n=int(input())
for i in range(n):
 a=int(input())
 if(a%5==0 and a%2==0):
  print(0)
 elif(a%5==0 and a%2!=0 and a!=1):
  print(1)
 else:
  print(-1)

# cook your dish here
n=int(input())
for i in range(n):
 z=int(input())
 if z%10==0:
  print("0")
 elif z%5==0:
  print("1")
 else:
  print("-1")

n = int(input())
for i in range(n):
 ele = int(input())
 if(ele%10 == 0):
  print(0)
 else:
  ele *=2
  if(ele%10 == 0):
   print(1)
  else:
   print(-1)




# cook your dish here
n=int(input())
for i in range(n):
 a=int(input())
 if a%10==0:
  print("0")
 else:
  c=0
  a=a*2
  if a%10==0:
   c+=1
   print(c)
  else:
   print("-1")

# cook your dish here
n=int(input())
for i in range(n):
 a=int(input())
 if a%10==0:
  print("0")
 else:
  c=0
  a=a*2
  if a%10==0:
   c+=1
   print(c)
  else:
   print("-1")

# cook your dish here
t=int(input())
for i in range(t):
 x=int(input())
 r=x%10
 if(r==0):
  print(0)
 elif(r==5):
  print(1)
 else:
  print(-1)


# cook your dish here
t=int(input())
for i in range(t):
 n=int(input())
 d=n%10
 if(d==0):
  print(0)
 elif(d==5):
  print(1)
 else:
  print(-1)