#include<bits/stdc++.h>usingnamespacestd;#define rep(i, n) for (int i = 0; i < (n); ++i)
usingll=longlong;usingull=unsignedlonglong;#include"../../../cpp/library/math/miller-rabin.hpp"
#define PROBLEM "https://judge.yosupo.jp/problem/primality_test"
intmain(){cin.tie(nullptr)->sync_with_stdio(false);intq;cin>>q;while(q--){ulln;cin>>n;cout<<(asalib::math::miller_rabin_test(n)?"Yes":"No")<<'\n';}return0;}
#line 1 "tests/math/miller-rabin/libchecker.test.cpp"
#include<bits/stdc++.h>usingnamespacestd;#define rep(i, n) for (int i = 0; i < (n); ++i)
usingll=longlong;usingull=unsignedlonglong;#line 2 "library/math/miller-rabin.hpp"
#line 4 "library/math/miller-rabin.hpp"
#include<concepts>
#line 6 "library/math/miller-rabin.hpp"
usingnamespacestd;namespaceasalib{namespacemath{template<integralT>constexprboolmiller_rabin_test(Tn){if(n<2)[[unlikely]]returnfalse;if(n%2==0)returnn==2;Td=n-1,s=0;while(d%2==0)d>>=1,++s;assert(d%2==1);static_assert(sizeof(T)==4||sizeof(T)==8,"T must be 32-bit or 64-bit integer type");constexprboolis_64bit=sizeof(T)==8;function<T(T,T,T)>modpow=[&](Ta,Tn,Tmod){Tres=1;while(n){ifconstexpr(is_64bit){if(n&1)res=(__uint128_t)res*a%mod;a=(__uint128_t)a*a%mod;}else{if(n&1)res=(unsignedlonglong)res*a%mod;a=(unsignedlonglong)a*a%mod;}n>>=1;}returnres;};function<bool(T)>test=[&](Ta){Tx=modpow(a,d,n);if(x==0)[[unlikely]]returnfalse;if(x==1)[[unlikely]]returntrue;for(T_=0;_<s;++_){Ty;ifconstexpr(is_64bit)y=(__uint128_t)x*x%n;elsey=(unsignedlonglong)x*x%n;if(y==1&&x!=1&&x!=n-1)returnfalse;x=y;}returnx==1;};function<bool(vector<T>)>tests=[&](vector<T>basis){for(Ta:basis)if(!test(a))returnfalse;returntrue;};if(n<2'047)returntest(2);if(n<1'373'653)returntests({2,3});if(n<9'080'191)returntests({31,73});if(n<25'326'001)returntests({2,3,5});if(n<3'215'031'751)returntests({2,3,5,7});if(n<4'759'123'141)returntests({2,7,61});if(n<1'122'004'669'633)returntests({2,13,23,1662803});if(n<2'152'302'898'747)returntests({2,3,5,7,11});if(n<3'474'749'660'383)returntests({2,3,5,7,11,13});if(n<341'550'071'728'321)returntests({2,3,5,7,11,13,17});if(n<3'825'123'056'546'413'051)returntests({2,3,5,7,11,13,17,19,23});if(ull(n)<=18'446'744'073'709'551'615ULL)returntests({2,3,5,7,11,13,17,19,23,29,31,37});// 18'446'744'073'709'551'616 は 2^64 であり、これ以上の数は 64 ビット整数型では表現できない// TODO: 多倍長整数を使う場合は if を追加する// TODO: C++23 以降なら __builtin_unreachable() -> std::unreachable() に変更可能__builtin_unreachable();}}// namespace math}// namespace asalib#line 8 "tests/math/miller-rabin/libchecker.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/primality_test"
intmain(){cin.tie(nullptr)->sync_with_stdio(false);intq;cin>>q;while(q--){ulln;cin>>n;cout<<(asalib::math::miller_rabin_test(n)?"Yes":"No")<<'\n';}return0;}