#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("inline") #include using namespace std; #define MD (1000000007U) template struct cLtraits_identity{ using type = T; } ; template using cLtraits_try_make_signed = typename conditional< is_integral::value, make_signed, cLtraits_identity >::type; template struct cLtraits_common_type{ using tS = typename cLtraits_try_make_signed::type; using tT = typename cLtraits_try_make_signed::type; using type = typename common_type::type; } ; void*wmem; char memarr[96000000]; template inline auto min_L(S a, T b) -> typename cLtraits_common_type::type{ return (typename cLtraits_common_type::type) a <= (typename cLtraits_common_type::type) b ? a : b; } template inline auto max_L(S a, T b) -> typename cLtraits_common_type::type{ return (typename cLtraits_common_type::type) a >= (typename cLtraits_common_type::type) b ? a : b; } template inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } template inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){ walloc1d(arr, x2-x1, mem); (*arr) -= x1; } #define ISPRIME_PRE_CALC_SIZE 1000000 char isPrime_prime_table[ISPRIME_PRE_CALC_SIZE]; template inline int isPrime(T n); void isPrime32_init(void); int isPrime32_sub(int b, unsigned n); int isPrime32(unsigned n); int isPrime64_sub(long long b, unsigned long long n); int isPrime64(unsigned long long n); #define FACTOR_PRE_CALC_SIZE 1000000 int factor_hasprime_table[FACTOR_PRE_CALC_SIZE]; template int Factor(T N, R1 fac[], R2 fs[], void *mem = wmem); template int Factor(T N, R1 fac[], void *mem = wmem); template int Factor(T N, void *mem = wmem); unsigned Factor32_rho(unsigned n); template int Factor32(unsigned N, R1 fac[], R2 fs[], void *mem = wmem); unsigned long long Factor64_rho(unsigned long long n); template int Factor64(unsigned long long N, R1 fac[], R2 fs[], void *mem = wmem); void Factor32_init(void); template int Divisor(T N, R res[], void *mem = wmem); template void sortA_L(int N, T1 a[], void *mem = wmem){ sort(a, a+N); } struct Rand{ unsigned x; unsigned y; unsigned z; unsigned w; Rand(void){ x=123456789; y=362436069; z=521288629; w=(unsigned)time(NULL); } Rand(unsigned seed){ x=123456789; y=362436069; z=521288629; w=seed; } inline unsigned get(void){ unsigned t; t = (x^(x<<11)); x=y; y=z; z=w; w = (w^(w>>19))^(t^(t>>8)); return w; } inline double getUni(void){ return get()/4294967296.0; } inline int get(int a){ return (int)(a*getUni()); } inline int get(int a, int b){ return a+(int)((b-a+1)*getUni()); } inline long long get(long long a){ return(long long)(a*getUni()); } inline long long get(long long a, long long b){ return a+(long long)((b-a+1)*getUni()); } inline double get(double a, double b){ return a+(b-a)*getUni(); } inline int getExp(int a){ return(int)(exp(getUni()*log(a+1.0))-1.0); } inline int getExp(int a, int b){ return a+(int)(exp(getUni()*log((b-a+1)+1.0))-1.0); } } ; struct modint{ static unsigned md; unsigned val; modint(){ val=0; } modint(int a){ val = ord(a); } modint(unsigned a){ val = ord(a); } modint(long long a){ val = ord(a); } modint(unsigned long long a){ val = ord(a); } void setmod(unsigned m){ md = m; } unsigned ord(unsigned a){ return a%md; } unsigned ord(int a){ a %= (int)md; if(a < 0){ a += md; } return a; } unsigned ord(unsigned long long a){ return a%md; } unsigned ord(long long a){ a %= (int)md; if(a < 0){ a += md; } return a; } unsigned get(){ return val; } inline modint &operator++(){ val++; if(val >= md){ val -= md; } return *this; } inline modint &operator--(){ if(val == 0){ val = md - 1; } else{ --val; } return *this; } inline modint operator++(int a){ modint res(*this); val++; if(val >= md){ val -= md; } return res; } inline modint operator--(int a){ modint res(*this); if(val == 0){ val = md - 1; } else{ --val; } return res; } modint &operator+=(modint a){ val += a.val; if(val >= md){ val -= md; } return *this; } modint &operator-=(modint a){ if(val < a.val){ val = val + md - a.val; } else{ val -= a.val; } return *this; } modint &operator*=(modint a){ val = ((unsigned long long)val*a.val)%md; return *this; } modint &operator/=(modint a){ return *this *= a.inverse(); } modint operator+(modint a){ return modint(*this)+=a; } modint operator-(modint a){ return modint(*this)-=a; } modint operator*(modint a){ return modint(*this)*=a; } modint operator/(modint a){ return modint(*this)/=a; } modint operator+(int a){ return modint(*this)+=modint(a); } modint operator-(int a){ return modint(*this)-=modint(a); } modint operator*(int a){ return modint(*this)*=modint(a); } modint operator/(int a){ return modint(*this)/=modint(a); } modint operator+(long long a){ return modint(*this)+=modint(a); } modint operator-(long long a){ return modint(*this)-=modint(a); } modint operator*(long long a){ return modint(*this)*=modint(a); } modint operator/(long long a){ return modint(*this)/=modint(a); } modint operator-(void){ modint res; if(val){ res.val=md-val; } else{ res.val=0; } return res; } operator bool(void){ return val!=0; } operator int(void){ return get(); } operator long long(void){ return get(); } modint inverse(){ int a = val; int b = md; int u = 1; int v = 0; int t; modint res; while(b){ t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } if(u < 0){ u += md; } res.val = u; return res; } modint pw(unsigned long long b){ modint a(*this); modint res; res.val = 1; while(b){ if(b&1){ res *= a; } b >>= 1; a *= a; } return res; } bool operator==(int a){ return ord(a)==val; } bool operator!=(int a){ return ord(a)!=val; } } ; unsigned modint::md; modint operator+(int a, modint b){ return modint(a)+=b; } modint operator-(int a, modint b){ return modint(a)-=b; } modint operator*(int a, modint b){ return modint(a)*=b; } modint operator/(int a, modint b){ return modint(a)/=b; } modint operator+(long long a, modint b){ return modint(a)+=b; } modint operator-(long long a, modint b){ return modint(a)-=b; } modint operator*(long long a, modint b){ return modint(a)*=b; } modint operator/(long long a, modint b){ return modint(a)/=b; } inline int my_getchar_unlocked(){ static char buf[1048576]; static int s = 1048576; static int e = 1048576; if(s == e && e == 1048576){ e = fread_unlocked(buf, 1, 1048576, stdin); s = 0; } if(s == e){ return EOF; } return buf[s++]; } inline void rd(long long &x){ int k; int m=0; x=0; for(;;){ k = my_getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = my_getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } struct MY_WRITER{ char buf[1048576]; int s; int e; MY_WRITER(){ s = 0; e = 1048576; } ~MY_WRITER(){ if(s){ fwrite_unlocked(buf, 1, s, stdout); } } } ; MY_WRITER MY_WRITER_VAR; void my_putchar_unlocked(int a){ if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){ fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout); MY_WRITER_VAR.s = 0; } MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a; } inline void wt_L(char a){ my_putchar_unlocked(a); } inline void wt_L(int x){ int s=0; int m=0; char f[10]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } inline void wt_L(long long x){ int s=0; int m=0; char f[20]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } template inline T pow2_L(T a){ return a*a; } template inline T pow_L(T a, S b){ T res = 1; res = 1; for(;;){ if(b&1){ res *= a; } b >>= 1; if(b==0){ break; } a *= a; } return res; } inline double pow_L(double a, double b){ return pow(a,b); } template inline T GCD_L(T a, U b){ T r; while(b){ r=a; a=b; b=r%a; } return a; } inline long long Isqrt_f_L(const long long n){ long long r = sqrt(n); r =max_L(r-2, 0); while((pow2_L((r+1)))<= n ){ r++; } return r; } long long euler(long long a){ long long p=a; long long i=2; while(a>1){ if(a%i==0){ p-=p/i; } while(a%i==0){ a/=i; } ++i; if(i*i>a){ i=a; } } return p; } long long d[100000]; int main(){ int cTE1_r3A; wmem = memarr; { isPrime32_init(); } { Factor32_init(); } { modint x; x.setmod(MD); } long long t; rd(t); for(cTE1_r3A=(0);cTE1_r3A<(t);cTE1_r3A++){ long long n; rd(n); while(n%2==0){ n/=2; } while(n%5==0){ n/=5; } if(n==1){ wt_L(1); wt_L('\n'); continue; } Divisor(euler(n),d); modint x; x.setmod(n); long long a=0; while(1){ x=10; (x = pow_L(x,d[a])); if(x==1){ break; } ++a; } wt_L(d[a]); wt_L('\n'); } return 0; } template inline int isPrime(T n){ T i; if(n<=1){ return 0; } if(n <= (1ULL<<32) - 1){ return isPrime32(n); } if(n <= (1ULL<<63) - 1 + (1ULL<<63)){ return isPrime64(n); } if(n<=3){ return 1; } if(n%2==0){ return 0; } for(i=3;i*i<=n;i+=2){ if(n%i==0){ return 0; } } return 1; } int isPrime32_sub(int b, unsigned n){ unsigned i; unsigned t = 0; unsigned u = n-1; unsigned long long nw; unsigned long long nx; while(!(u&1)){ t++; u >>= 1; } nw = 1; nx = b % n; while(u){ if(u&1){ nw = (nw * nx) % n; } nx = (nx * nx) % n; u >>= 1; } for(i=(0);i<(t);i++){ nx = (nw * nw) % n; if(nx == 1 && nw != 1 && nw != n-1){ return 0; } nw = nx; } if(nw == 1){ return 1; } return 0; } int isPrime32(unsigned n){ if(n < 100000){ return isPrime_prime_table[n]; } if(n % 2 == 0){ return 0; } if(!isPrime32_sub(2,n)){ return 0; } if(n<=1000000){ if(!isPrime32_sub(3,n)){ return 0; } } else{ if(!isPrime32_sub(7,n)){ return 0; } if(!isPrime32_sub(61,n)){ return 0; } } return 1; } int isPrime64_sub(long long b, unsigned long long n){ unsigned long long i; unsigned long long t = 0; unsigned long long u = n-1; __uint128_t nw; __uint128_t nx; while(!(u&1)){ t++; u >>= 1; } nw = 1; nx = b % n; while(u){ if(u&1){ nw = (nw * nx) % n; } nx = (nx * nx) % n; u >>= 1; } for(i=(0);i<(t);i++){ nx = (nw * nw) % n; if(nx == 1 && nw != 1 && nw != n-1){ return 0; } nw = nx; } if(nw == 1){ return 1; } return 0; } int isPrime64(unsigned long long n){ if(n < 100000){ return isPrime_prime_table[n]; } if(n < (1ULL<<32)){ return isPrime32(n); } if(n % 2 == 0){ return 0; } if(!isPrime64_sub(2,n)){ return 0; } if(n <= 21652684502221ULL){ if(!isPrime64_sub(1215,n)){ return 0; } if(!isPrime64_sub(34862,n)){ return 0; } if(!isPrime64_sub(574237825,n)){ return 0; } } else{ if(!isPrime64_sub(325,n)){ return 0; } if(!isPrime64_sub(9375,n)){ return 0; } if(!isPrime64_sub(28178,n)){ return 0; } if(!isPrime64_sub(450775,n)){ return 0; } if(!isPrime64_sub(9780504,n)){ return 0; } if(!isPrime64_sub(1795265022,n)){ return 0; } } return 1; } void isPrime32_init(void){ int i; int j; int k; k =Isqrt_f_L(ISPRIME_PRE_CALC_SIZE); for(i=(2);i<(ISPRIME_PRE_CALC_SIZE);i++){ isPrime_prime_table[i] = 1; } for(i=(2);i<(k+1);i++){ if(isPrime_prime_table[i]){ for(j=(i*i);j<(ISPRIME_PRE_CALC_SIZE);j+=(i)){ isPrime_prime_table[j] = 0; } } } } template int Factor(T N, R1 fac[], R2 fs[], void *mem/* = wmem*/){ T i; int sz = 0; if(N <= 1){ return sz; } if(N <= (1ULL<<32) - 1){ return Factor32(N, fac, fs, mem); } if(N <= (1ULL<<63) - 1 + (1ULL<<63)){ return Factor64(N, fac, fs, mem); } if(N%2==0){ fac[sz] = 2; fs[sz] = 1; N /= 2; while(N%2==0){ N /= 2; fs[sz]++; } sz++; } for(i=3;i*i<=N;i+=2){ if(N%i==0){ fac[sz] = i; fs[sz] = 1; N /= i; while(N%i==0){ N /= i; fs[sz]++; } sz++; } } if(N > 1){ fac[sz] = N; fs[sz] = 1; sz++; } return sz; } template int Factor(T N, R1 fac[], void *mem/* = wmem*/){ int*fs; walloc1d(&fs,128,&mem); return Factor(N, fac, fs, mem); } template int Factor(T N, void *mem/* = wmem*/){ T*fac; int*fs; walloc1d(&fac,128,&mem); walloc1d(&fs,128,&mem); return Factor(N, fac, fs, mem); } unsigned Factor32_rho(unsigned n){ static Rand rnd; const int step = 16; int i; int s; int nx; int mx; unsigned long long x; unsigned long long y; unsigned long long memo; unsigned long long c; unsigned long long m; unsigned g; long long lm; lm =min_L(1ULL<<30, n - 1); for(;;){ x = y = rnd.get(1LL, lm); c = rnd.get(1LL, lm); g = 1; for(nx=1;g==1;nx<<=1){ x = y; for(i=(0);i<(nx);i++){ y = (y * y + c) % n; } for(s=0;s= y){ m = (m * (x - y)) % n; } else{ m = (m * (y - x)) % n; } } g =GCD_L(n, m); if(g != 1){ if(g != n){ return g; } y = memo; for(;;){ y = (y * y + c) % n; if(x >= y){ m = x - y; } else{ m = y - x; } g =GCD_L(n, m); if(g == n){ break; } if(g != 1){ return g; } } } } } } return 0; } template int Factor32(unsigned N, R1 fac[], R2 fs[], void *mem/* = wmem*/){ int res = 0; int sz = 0; int i; int k; unsigned*val; unsigned*valtmp; unsigned pf; unsigned n; if(N <= 1){ return 0; } walloc1d(&val, 128, &mem); walloc1d(&valtmp, 128, &mem); while(N%2==0){ val[res++] = 2; N /= 2; } while(N%3==0){ val[res++] = 3; N /= 3; } while(N%5==0){ val[res++] = 5; N /= 5; } if(N > 1){ valtmp[sz++] = N; } while(sz){ while(sz && isPrime32(valtmp[sz-1])){ val[res] = valtmp[sz-1]; res++; sz--; } if(sz==0){ break; } n = valtmp[sz-1]; if(n < FACTOR_PRE_CALC_SIZE){ while(n > 1){ val[res++] = factor_hasprime_table[n]; n /= factor_hasprime_table[n]; } sz--; } else{ pf = Factor32_rho(n); valtmp[sz-1] = pf; valtmp[sz] = n / pf; sz++; } } sortA_L(res, val, mem); k = 0; for(i=(0);i<(res);i++){ if(k && fac[k-1] == val[i]){ fs[k-1]++; continue; } fac[k] = val[i]; fs[k] = 1; k++; } res = k; return res; } unsigned long long Factor64_rho(unsigned long long n){ static Rand rnd; const int step = 16; int i; int s; int nx; int mx; __uint128_t x; __uint128_t y; __uint128_t memo; __uint128_t c; __uint128_t m; unsigned long long g; long long lm; lm =min_L(1ULL<<30, n - 1); for(;;){ x = y = rnd.get(1LL, lm); c = rnd.get(1LL, lm); g = 1; for(nx=1;g==1;nx<<=1){ x = y; for(i=(0);i<(nx);i++){ y = (y * y + c) % n; } for(s=0;s= y){ m = (m * (x - y)) % n; } else{ m = (m * (y - x)) % n; } } g =GCD_L(n, m); if(g != 1){ if(g != n){ return g; } y = memo; for(;;){ y = (y * y + c) % n; if(x >= y){ m = x - y; } else{ m = y - x; } g =GCD_L(n, m); if(g == n){ break; } if(g != 1){ return g; } } } } } } return 0; } template int Factor64(unsigned long long N, R1 fac[], R2 fs[], void *mem/* = wmem*/){ int res = 0; int sz = 0; int i; int k; unsigned long long*val; unsigned long long*valtmp; unsigned long long pf; unsigned long long n; if(N <= 1){ return 0; } walloc1d(&val, 128, &mem); walloc1d(&valtmp, 128, &mem); while(N%2==0){ val[res++] = 2; N /= 2; } while(N%3==0){ val[res++] = 3; N /= 3; } while(N%5==0){ val[res++] = 5; N /= 5; } if(N > 1){ valtmp[sz++] = N; } while(sz){ while(sz && isPrime64(valtmp[sz-1])){ val[res] = valtmp[sz-1]; res++; sz--; } if(sz==0){ break; } n = valtmp[sz-1]; if(n < FACTOR_PRE_CALC_SIZE){ while(n > 1){ val[res++] = factor_hasprime_table[n]; n /= factor_hasprime_table[n]; } sz--; } else if(n < (1ULL<<32)){ pf = Factor32_rho(n); valtmp[sz-1] = pf; valtmp[sz] = n / pf; sz++; } else{ pf = Factor64_rho(n); valtmp[sz-1] = pf; valtmp[sz] = n / pf; sz++; } } sortA_L(res, val, mem); k = 0; for(i=(0);i<(res);i++){ if(k && fac[k-1] == val[i]){ fs[k-1]++; continue; } fac[k] = val[i]; fs[k] = 1; k++; } res = k; return res; } void Factor32_init(void){ int i; int j; int k; k =Isqrt_f_L(FACTOR_PRE_CALC_SIZE); for(i=(2);i<(FACTOR_PRE_CALC_SIZE);i++){ factor_hasprime_table[i] = i; } for(i=(2);i<(k+1);i++){ if(factor_hasprime_table[i]==i){ for(j=(i*i);j<(FACTOR_PRE_CALC_SIZE);j+=(i)){ factor_hasprime_table[j] = i; } } } } template int Divisor(T N, R res[], void *mem/* = wmem*/){ int i; int j; int k; int s; int sz = 0; T*fc; int*fs; int fsz; walloc1d(&fc, 128, &mem); walloc1d(&fs, 128, &mem); fsz = Factor(N, fc, fs, mem); res[sz++] = 1; for(i=(0);i<(fsz);i++){ s = sz; k = s * fs[i]; for(j=(0);j<(k);j++){ res[sz++] = res[j] * fc[i]; } } sort(res, res+sz); return sz; } // cLay version 20210708-1 // --- original code --- // ll euler(ll a){ // ll p=a; // ll i=2; // while(a>1){ // if(a%i==0){ // p-=p/i; // } // while(a%i==0){ // a/=i; // } // ++i; // if(i*i>a){ // i=a; // } // } // return p; // } // // // ll d[1d5]; // { // ll@t; // rep(t){ // ll@n; // while(n%2==0) n/=2; // while(n%5==0) n/=5; // if(n==1) wt(1),continue; // Divisor(euler(n),d); // modint x; // x.setmod(n); // ll a=0; // while(1){ // x=10; // x**=d[a]; // if(x==1) break; // ++a; // } // wt(d[a]); // } // } //