Two vs Ten

Chef Two and Chef Ten are playing a game with a number X$X$. In one turn, they can multiply X$X$ by 2$2$. The goal of the game is to make X$X$ divisible by 10$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$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first and only line of each test case contains a single integer denoting the initial value of X$X$.

Output

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

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 0≤X≤109$0\le X\le {10}^9$

Subtasks

Subtask #1 (100 points): original constraints

Example Input

3
10
25
1

Example Output

0
1
-1

SOLUTION USING C LANGUAGE:-
#include<stdio.h>
int main(void)
{
    int T,X,i;
    scanf("%d\n",&T);
    for(i=0;i<T;i++)
    {
        scanf("%d\n",&X);
        if(X%10==0)
        {
            printf("0\n");
        }
        else if (X%10==5)
        {
            X=X*2;
            if(X%10==0)
            {
            printf("1\n");
            }
        }
        else
        {
            printf("-1\n");
        }
    }
    return 0;
}

Share: