如果知道阶的相关知识，那么就是道板题。
一个显然的结论是k最多只能有一个2的因子，同时不能有5的因子，直接特判即可
\[k| \frac{10^x -1}{9}
\]
那么剩余的情况我们可以保证(9p,10)=1,根据欧拉定理，在这种情况下一定有解。
那么问题转化为求最小的正整数x使得
\[9k| {10^x -1}
\]
就是求阶。
而原本的bsgs求出来的x的范围是在[0,9k-1]，我们不希望得到0的解，网上找了一下居然没找到求最小的正整数解。
那么自己动手。
原来我们的hash保存的是最大值，那么最大值有可能减了之后等于0，那么我们在存一个次小值即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<unordered_map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N = 2e5 + 5;
const ll inf = 1ll << 60;
const ll mo = 998244353;
ll n;
ll bsgs(ll a, ll b, ll mod){
unordered_map<ll, ll> mp;
unordered_map<ll, ll> se;
mp.clear();
se.clear();
ll cur = 1, t = sqrt(mod) + 1;
for(int B = 1; B <= t; B++){
cur = cur * a % mod;
if (mp.find(b*cur%mod)!=mp.end()) se[b*cur%mod]=mp[b * cur % mod];
mp[b* cur % mod] = B;
}
ll now = cur;
for(int A = 1; A <= t; A++){
if(mp.find(now)!=mp.end() && A*t-mp[now]) return A*t-mp[now];
if(se.find(now)!=se.end() && A*t-se[now]) return A*t-se[now];
now = now * cur % mod;
}
return -1;
}
void solve(){
scanf("%lld",&n);
if (n%4==0 || n%5==0) {
puts("-1"); return;
}
if (n%2==0) n/=2;
printf("%lld\n",bsgs(10,1,9ll*n));
}
int main()
{
// freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while (T--){
solve();
}
return 0;
}