abc222G - 222

G - 222

如果知道阶的相关知识，那么就是道板题。
一个显然的结论是k最多只能有一个2的因子，同时不能有5的因子，直接特判即可

那么剩余的情况我们可以保证(9p,10)=1,根据欧拉定理，在这种情况下一定有解。
那么问题转化为求最小的正整数x使得

就是求阶。

而原本的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;
}