#include using namespace std; template struct Montgomery{ //2^62未満&奇数modのみ. //初めにsetmodする. using u64 = uint64_t; using u128 = __uint128_t; private: static u64 mod,N2,Rsq; //N*N2≡1(mod N); //Rsq = R^2modN; R=2^64. u64 v = 0; public: long long val()const{return reduce(v);} static constexpr u64 getmod(){return mod;} static void setmod(u64 m){ assert(m<(1LL<<62)&&(m&1)); mod = m; N2 = mod; for(int i=0; i<5; i++) N2 *= 2-N2*mod; Rsq = (-u128(mod))%mod; } //reduce = T*R^-1modNを求める. u64 reduce(const u128 &T)const{ //T*R^-1≡(T+(T*(-N2))modR*N)/R 2N未満なので-N必要かだけで良い. u64 ret = (T+u128(((u64)T)*(-N2))*mod)>>64; if(ret >= mod) ret -= mod; return ret; } //初期値reduce(R^2)でok. Montgomery(){v = 0;} Montgomery(long long w):v(reduce(u128(w)*Rsq)){} Montgomery &operator=(const Montgomery &b) = default; Montgomery operator-()const{return Montgomery()-Montgomery(*this);} Montgomery operator+(const Montgomery &b)const{return Montgomery(*this)+=b;} Montgomery operator-(const Montgomery &b)const{return Montgomery(*this)-=b;} Montgomery operator*(const Montgomery &b)const{return Montgomery(*this)*=b;} Montgomery operator/(const Montgomery &b)const{return Montgomery(*this)/=b;} Montgomery &operator+=(const Montgomery &b){ v += b.v; if(v >= mod) v -= mod; return (*this); } Montgomery &operator-=(const Montgomery &b){ v += mod-b.v; if(v >= mod) v -= mod; return (*this); } Montgomery &operator*=(const Montgomery &b){ v = reduce(u128(v)*b.v); return (*this); } Montgomery &operator/=(const Montgomery &b){ (*this) *= b.inv(); return (*this); } Montgomery pow(long long b)const{ Montgomery ret = 1,p = (*this); if(b < 0) p = p.inv(),b = -b; while(b){ if(b&1) ret *= p; p *= p; b >>= 1; } return ret; } Montgomery inv()const{assert(v); return pow(mod-2);} friend bool operator!=(const Montgomery &a,const Montgomery &b){return a.v!=b.v;} friend bool operator==(const Montgomery &a,const Montgomery &b){return a.v==b.v;} }; template uint64_t Montgomery::mod; template uint64_t Montgomery::N2; template uint64_t Montgomery::Rsq; using mont = Montgomery<0>; bool MillerRabin(long long N,const vector &A){ mont::setmod(N); long long s = __builtin_ctzll(N-1),d = N-1; d >>= s; for(auto &a : A){ if(N <= a) break; mont x = mont(a).pow(d); if(x != 1){ long long t; for(t=0; t> L >> R; int Need = 15010000; vector prime(Need+1,true); prime.at(0) = false; prime.at(1) = false; for(int i=2; i*i<=Need; i++){ if(!prime.at(i)) continue; for(int k=i*i; k<=Need; k+=i) prime.at(k) = false; } for(long long a=3; a*a*a*a<=R; a++) if(prime.at(a)) for(long long b=a+1; a*a*b*b<=R; b++) if(prime.at(b)){ for(long long c=max(b+1,(L+a*a*b-1)/(a*a*b)); a*a*b*c<=R; c++){ if((c<=Need&&prime.at(c)) || isprime(c)){cout << a*a*b*c << endl; return 0;} } } cout << "-1" << endl; }