#include #include #define INF 1000000000LL #define LUG 1000000000LL using namespace std; typedef long long ll; typedef pair P; std::random_device rd; std::mt19937 mt(rd()); ll rdn[201]; ll num[5],num2[5],num3[5]; bool C(ll v,ll tgt,int po){ ll vv=1; for(int i=0;i=1LL)return false; vv=num3[1]*LUG+num3[0]; if(vv>tgt)return false; } return vv<=tgt; } ll mulmod(ll a,ll b,ll m){ if(b>=1; b=(b<<1)%m; } return ans; } ll mod_pow(ll x,ll n,ll mod){ ll res=1; while(n>0){ if(n&1LL)res=mulmod(res,x,mod); x=mulmod(x,x,mod); n>>=1; } return res; } bool calc(ll v,ll tgt,int po){ ll ans=1; while(po>0){ if(po&1LL)ans=ans*v; v=v*v; po>>=1; } //printf("%lld %lld %lldde\n",ans,tgt,tgt-ans); if(anstgt)return false; return true; } bool is_prime(ll val){ if(val==1LL)return false; if(val==2LL)return true; if(val==3LL)return true; if(val%6LL!=1 && val%6LL!=5)return false; for(int i=0;i<50;i++){ ll v=rdn[i]%val; if(v==0LL)v=1; if(mod_pow(v,val-1LL,val)!=1LL)return false; } return true; } bool check(ll val,int po){ if(po==1)return is_prime(val); else{ ll l=3,r=min(val,INF); if(po==3)r=min(val,1000001LL); if(po==4)r=min(val,100001LL); if(po==5)r=min(val,10001LL); if(po==6)r=min(val,1001LL); if(po>6)r=min(val,1000LL); if(po>10)r=min(val,100LL); while(l+1LL