#define rep(i,n) for(int i=0;i<(int)(n);i++) #define ALL(v) v.begin(),v.end() typedef long long ll; #include using namespace std; ll modpow(ll x,ll n,ll MOD){ ll ans=1; while(n){ if(n&1) ans=ans*x%MOD; x=x*x%MOD; n/=2; } return ans; } int main(){ int t; cin>>t; while(t--){ ll n; cin>>n; map m; for(ll i=2;i*i<=n;i++){ while(n%i==0){ m[i]++; n/=i; } } if(n!=1) m[n]++; ll ans=1; for(auto x:m){ ll p=x.first; if(p==1 || p==2 || p==5) continue; ll y=p-1; set s; for(ll i=1;i*i<=y;i++){ if(y%i==0){ s.insert(i); s.insert(y/i); } } ll tmp=1; for(auto a:s){ if(modpow(10,a,p)==1){ tmp=a; break; } } ans=lcm(ans,tmp); } cout<