#include using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } bool isPrime(ll num){ if(num<2) return false; else if(num==2) return true; else if(num%2==0) return false; for(ll i=3;i*i<=num;i+=2) if(num%i==0) return false; return true; } ll pow_mod(ll a,ll n,ll m){ ll ret=1; while(n){ if(n&1) ret=ret*a%m; a=a*a%m; n>>=1; } return ret; } template T mod_log(T a,T b,T MOD){ using ll = long long; ll g=1; { ll m=MOD; while(m){ g=(ll)g*a%MOD; m>>=1; } } g=__gcd(g,(ll)MOD); ll c=0,t=1; while(t%g){ if(t==b) return c; t=t*a%MOD; c++; } // not found if(b%g) return MOD; t/=g;b/=g; const ll n=MOD/g; ll h=0,gs=1; while(h*h bs; { ll s=0,e=b; while(s0) chmin(ret,c+s-bs[e]); } } } return ret; } void solve(){ ll n;cin>>n; while(n%2==0) n/=2; while(n%5==0) n/=5; if(n==1){ cout<<1<>q; while(q--) solve(); return 0; }