# Make it Divisible by 25 solution codeforces

\It is given a positive integer . In  move, one can select any single digit and remove it (i.e. one selects some position in the number and removes the digit located at this position). The operation cannot be performed if only one digit remains. If the resulting number contains leading zeroes, they are automatically removed.

E.g. if one removes from the number  the -rd digit, the resulting number will be . If one removes from the number  the first digit, the resulting number will be  (the zeroes going next to the first digit  are automatically removed).

## Make it Divisible by 25 solution codeforces

What is the minimum number of steps to get a number such that it is divisible by  and positive? It is guaranteed that, for each  occurring in the input, the answer exists. It is guaranteed that the number  has no leading zeros.

Input

The first line contains one integer  () — the number of test cases. Then  test cases follow.

Each test case consists of one line containing one integer  (). It is guaranteed that, for each  occurring in the input, the answer exists. It is guaranteed that the number  has no leading zeros.

## Output Make it Divisible by 25 solution codeforces

For each test case output on a separate line an integer  () — the minimum number of steps to get a number such that it is divisible by  and positive.

Example
input

### Copy Make it Divisible by 25 solution codeforces

5
100
71345
3259
50555
2050047

output

### Copy Make it Divisible by 25 solution codeforces

0
3
1
3
2


### Note Make it Divisible by 25 solution codeforces

In the first test case, it is already given a number divisible by .

In the second test case, we can remove the digits , and  to get the number .

In the third test case, it’s enough to remove the last digit to get the number .

In the fourth test case, we can remove the three last digits to get the number .

In the fifth test case, it’s enough to remove the digits  and .