#include #include #ifdef LOCAL #include #define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (static_cast(0)) #endif using namespace atcoder; using mint=modint998244353; using namespace std; using ll=long long; using ul=unsigned long long; int dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0}; int dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0}; using Graph=vector>; ll op(ll a,ll b){return min(a,b);} ll e(){return 2e9;} vector erat(){ vectorans; vectorcheck(100001); for(int i=2;i<100001;i++){ if(check[i])continue; else{ ans.push_back(i); for(int j=i*2;j<100001;j+=i)check[j]=1; } } return ans; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int Q; cin>>Q; vectorprime=erat(); while(Q--){ ll A; cin>>A; int cnt=0; bool ok=true; for(ll i=0;i