B. Make it Divisible by 25 | Codeforces Round #748 (Div. 3)

                                    B. Make it Divisible by 25

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

It is given a positive integer n$n$. In 1$1$ 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 32925$32925$ the 3$3$-rd digit, the resulting number will be 3225$3225$. If one removes from the number 20099050$20099050$ the first digit, the resulting number will be 99050$99050$ (the 2$2$ zeroes going next to the first digit are automatically removed).

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

Input

The first line contains one integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases. Then t$t$ test cases follow.

Each test case consists of one line containing one integer n$n$ (25≤n≤1018$25\le n\le {10}^{18}$). It is guaranteed that, for each n$n$ occurring in the input, the answer exists. It is guaranteed that the number n$n$ has no leading zeros.

Output

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

Example

input

Copy

5
100
71345
3259
50555
2050047

output

Copy

0
3
1
3
2

Note

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

In the second test case, we can remove the digits 1$1$, 3$3$, and 4$4$ to get the number 75$75$.

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

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

In the fifth test case, it's enough to remove the digits 4$4$ and 7$7$.

The solution to the above problem is

#include <bits/stdc++.h>

using namespace std;

#define int            long long int

#define F              first

#define S              second

#define pb             push_back

#define si             set <int>

#define vi             vector <int>

#define pii            pair <int, int>

#define vpi            vector <pii>

#define vpp            vector <pair<int, pii>>

#define mii            map <int, int>

#define mpi            map <pii, int>

#define spi            set <pii>

#define endl           "\n"

#define sz(x)          ((int) x.size())

#define all(p)         p.begin(), p.end()

#define double         long double

#define que_max        priority_queue <int>

#define que_min        priority_queue <int, vi, greater<int>>

#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

#define print(a)       for(auto x : a) cout << x << " "; cout << endl

#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl

#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)

{

    int x = 1;

    while (b)

    {

        if (b & 1) x *= a;

        a *= a;

        b >>= 1;

    }

    return x;

}

template <typename Arg1>

void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }

template <typename Arg1, typename... Args>

void __f (const char* names, Arg1&& arg1, Args&&... args)

{

    const char* comma = strchr (names + 1, ',');

    cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);

}

const int N = 200005;

//Main solution starts here

void solve() {

    

string s;

cin>>s;

int n=s.length();

int ans=n;

for(int i=0; i<n; i++){

    for(int j=i+1; j<n; j++){

        int val=(s[i]-'0')*10 +(s[j]-'0');

        if(val%25==0){

            ans=min(ans,j-i-1+n-j-1);

        }

    }

}

cout<<ans<<endl;

    

}

int32_t main()

{

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifndef ONLINE_JUDGE

    freopen("input.txt",  "r",  stdin);

    freopen("output.txt", "w", stdout);

#endif

    clock_t z = clock();

    int t = 1;

    cin >> t;

    while (t--) solve();

    cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);

    return 0;

}