[Solution] Make it Divisible by 25 solution codeforces | Codeforces Round #748

Make it Divisible by 25 solution codeforces

It is given a positive integer nn. In 11 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 3292532925 the 33-rd digit, the resulting number will be 32253225. If one removes from the number 2009905020099050 the first digit, the resulting number will be 9905099050 (the zeroes going next to the first digit 33 are automatically removed).

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

Make it Divisible by 25 solution codeforces

Input

The first line contains one integer tt (1t1041≤t≤104) — the number of test cases. Then tt test cases follow.

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

Make it Divisible by 25 solution codeforces

Output

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

Example
input

Copy
5
100
71345
3259
50555
2050047


Make it Divisible by 25 solution codeforces

output

Copy
0
3
1
3
2


Make it Divisible by 25 solution codeforces

Note

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

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

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

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

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