#include using namespace std; #if __has_include() #include using namespace atcoder; templateistream &operator>>(istream &is,static_modint &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<(0) ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } void SOLVE(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout<>testcase; for(int i=0;i>=1,s++; int q=63; while(!(d>>q))q--; ull r=n; for(int i=0;i<5;i++)r*=2-r*n; assert(r*n==1); auto redc=[&r,&n](__uint128_t x)->ull { x=(x+__uint128_t(ull(x)*-r)*n)>>64; return x>=n?x-n:x; }; __uint128_t r2=-__uint128_t(n)%n; ull one=redc(r2); for(ull base:{2,325,9375,28178,450775,9780504,1795265022}){ if(base%n==0)continue; ull a=base=redc((base%n)*r2); for(int i=q-1;i>=0;i--){ a=redc(__uint128_t(a)*a); if(d>>i&1)a=redc(__uint128_t(a)*base); } if(a==one)continue; for(int i=1;a!=n-one;i++){ if(i>=s)return false; a=redc(__uint128_t(a)*a); } } return true; } vectorfactorize(ull n)noexcept{ vectorret; auto div=[](ull x)noexcept->ull { ull r=x; for(int i=0;i<5;i++)r*=2-r*x; ull r2=-__uint128_t(x)%x; auto redc=[&r,&x](__uint128_t t)->ull { t=(t+__uint128_t(ull(t)*-r)*x)>>64; return t>=x?t-x:t; }; ull a=0,b=0; const ull one=redc(r2); ull e=one; ull m=1ll<<((63-__builtin_clzll(x))>>3); while(true){ ull ca=a,cb=b; ull sk=one; rep(i,m){ a=redc(__uint128_t(a)*a+e); b=redc(__uint128_t(b)*b+e); b=redc(__uint128_t(b)*b+e); ull c=redc(a),d=redc(b); sk=redc(__uint128_t(sk)*(c>d?c-d:d-c)); } ull g=gcd(redc(sk),x); if(g>1){ if(gd?c-d:d-c,x); if(cg>1){ if(cgst; while(!(n&1)){ n>>=1; ret.push_back(2); } if(n==1)return ret; st.push(n); while(!st.empty()){ ull now=st.top(); st.pop(); if(isprime(now)){ ret.push_back(now); continue; } ull d=div(now); st.push(d); now/=d; if(now!=1)st.push(now); } return ret; } void SOLVE(){ int n; ll k; cin>>n>>k; auto f=factorize(k); unordered_mapkf; for(auto i:f)kf[i]++; unordered_mapcnt; rep(i,n){ ll a; cin>>a; unordered_mapnow; for(auto [key,val]:kf){ while(a%key==0){ a/=key; now[key]++; } } for(auto [key,val]:now)chmax(cnt[key],val); } for(auto [key,val]:kf)if(cnt[key]