#include<bits/stdc++.h>
template<typename...>using my_void_t=void;
template<>struct std::is_integral<__int128>:public std::true_type{};template<>struct std::is_integral<__uint128_t>:public std::true_type{};
template<typename _Tp>constexpr int my_countr_zero(_Tp __x)noexcept{constexpr auto _Nd=std::numeric_limits<_Tp>::digits;if(__x==0)return _Nd;constexpr auto _Nd_ull=std::numeric_limits<uint64_t>::digits;constexpr auto _Nd_u=std::numeric_limits<unsigned>::digits;if _GLIBCXX17_CONSTEXPR(_Nd<=_Nd_u)return __builtin_ctz(__x);else if _GLIBCXX17_CONSTEXPR(_Nd<=_Nd_ull)return __builtin_ctzll(__x);else{constexpr auto __max_ull=std::numeric_limits<uint64_t>::max();uint64_t __low=__x&__max_ull;if(__low)return __builtin_ctzll(__low);uint64_t __high=__x>>_Nd_ull;return __builtin_ctzll(__high)+_Nd_ull;}}
template<typename _Clock,typename=my_void_t<typename _Clock::rep,typename _Clock::period,typename _Clock::duration,typename _Clock::time_point,decltype(_Clock::is_steady),decltype(_Clock::now())>>struct __check_time_helper{typename _Clock::time_point t;double used;__check_time_helper(){used=0;}void start(){t=_Clock::now();}void stop(){used+=std::chrono::duration_cast<std::chrono::nanoseconds>(_Clock::now()-t).count()/1e6;}~__check_time_helper(){fprintf(stderr,"time used: %.2lfms\n",used);}};
namespace OY{template<uint64_t _BufferSize,uint64_t _BlockSize>class inputHelper{public:FILE*m_filePtr;char m_buf[_BufferSize],*m_end,*m_cursor;bool m_ok;void flush(){uint64_t a=m_end-m_cursor;if(a>=_BlockSize)return;memmove(m_buf,m_cursor,a);uint64_t b=fread(m_buf+a,1,_BufferSize-a,m_filePtr);m_cursor=m_buf;if(a+b<_BufferSize){m_end=m_buf+a+b;*m_end=EOF;}}public:explicit inputHelper(const char*inputFileName):m_ok(true){if((ptrdiff_t)inputFileName<=0||!*inputFileName)m_filePtr=stdin;else m_filePtr=fopen(inputFileName,"rt");m_end=m_cursor=m_buf+_BufferSize;}~inputHelper(){fclose(m_filePtr);}static constexpr bool isBlank(char c){return c==' '||c=='\t'||c=='\n'||c=='\r';}static constexpr bool isEndline(char c){return c=='\n'||c==EOF;}const char&getChar_Checked(){if(m_cursor<m_end)return*m_cursor;uint64_t b=fread(m_buf,1,_BufferSize,m_filePtr);m_cursor=m_buf;if(b<_BufferSize){m_end=m_buf+b;*m_end=EOF;}return*m_cursor;}const char&getChar_Unchecked()const{return*m_cursor;}void next(){++m_cursor;}void setState(bool _ok){m_ok=_ok;}template<typename _Tp,typename std::enable_if<std::is_signed<_Tp>::value&std::is_integral<_Tp>::value,int>::type=0>inputHelper<_BufferSize,_BlockSize>&operator>>(_Tp&ret){while(isBlank(getChar_Checked()))next();flush();if(getChar_Unchecked()=='-'){next();if(isdigit(getChar_Unchecked())){ret=-(getChar_Unchecked()-'0');while(next(),isdigit(getChar_Unchecked()))ret=ret*10-(getChar_Unchecked()-'0');}else m_ok=false;}else{if(isdigit(getChar_Unchecked())){ret=getChar_Unchecked()-'0';while(next(),isdigit(getChar_Unchecked()))ret=ret*10+(getChar_Unchecked()-'0');}else m_ok=false;}return*this;}template<typename _Tp,typename std::enable_if<std::is_unsigned<_Tp>::value&std::is_integral<_Tp>::value,int>::type=0>inputHelper<_BufferSize,_BlockSize>&operator>>(_Tp&ret){while(isBlank(getChar_Checked()))next();flush();if(isdigit(getChar_Unchecked())){ret=getChar_Unchecked()-'0';while(next(),isdigit(getChar_Unchecked()))ret=ret*10+(getChar_Unchecked()-'0');}else m_ok=false;return*this;}template<typename _Tp,typename std::enable_if<std::is_floating_point<_Tp>::value,int>::type=0>inputHelper<_BufferSize,_BlockSize>&operator>>(_Tp&ret){bool neg=false,integer=false,decimal=false;while(isBlank(getChar_Checked()))next();flush();if(getChar_Unchecked()=='-'){neg=true;next();}if(!isdigit(getChar_Unchecked())&&getChar_Unchecked()!='.'){m_ok=false;return*this;}if(isdigit(getChar_Unchecked())){integer=true;ret=getChar_Unchecked()-'0';while(next(),isdigit(getChar_Unchecked()))ret=ret*10+(getChar_Unchecked()-'0');}if(getChar_Unchecked()=='.'){next();if(isdigit(getChar_Unchecked())){if(!integer)ret=0;decimal=true;_Tp unit=0.1;ret+=unit*(getChar_Unchecked()-'0');while(next(),isdigit(getChar_Unchecked())){unit*=0.1;ret+=unit*(getChar_Unchecked()-'0');}}}if(!integer&&!decimal)m_ok=false;else if(neg)ret=-ret;return*this;}inputHelper<_BufferSize,_BlockSize>&operator>>(char&ret){while(isBlank(getChar_Checked()))next();ret=getChar_Checked();if(ret==EOF)m_ok=false;else next();return*this;}inputHelper<_BufferSize,_BlockSize>&operator>>(std::string&ret){while(isBlank(getChar_Checked()))next();if(getChar_Checked()!=EOF){ret.clear();do{ret+=getChar_Checked();next();}while(!isBlank(getChar_Checked())&&getChar_Unchecked()!=EOF);}else m_ok=false;return*this;}explicit operator bool(){return m_ok;}};template<uint64_t _BufferSize=1<<20>class outputHelper{FILE*m_filePtr=nullptr;char m_buf[_BufferSize],*m_end,*m_cursor;char m_tempBuf[50],*m_tempBufCursor,*m_tempBufDot;uint64_t m_floatReserve,m_floatRatio;public:outputHelper(const char*outputFileName,int prec=6):m_end(m_buf+_BufferSize){if((ptrdiff_t)outputFileName<=0||!*outputFileName)m_filePtr=stdout;else m_filePtr=fopen(outputFileName,"wt");m_cursor=m_buf;m_tempBufCursor=m_tempBuf;precision(prec);}~outputHelper(){flush();fclose(m_filePtr);}void precision(int prec){m_floatReserve=prec;m_floatRatio=pow(10,prec);m_tempBufDot=m_tempBuf+prec;}outputHelper<_BufferSize>&flush(){fwrite(m_buf,1,m_cursor-m_buf,m_filePtr);fflush(m_filePtr);m_cursor=m_buf;return*this;}void putChar(const char&c){if(m_cursor==m_end)flush();*m_cursor++=c;}void putS(const char*c){while(*c)putChar(*c++);}template<typename _Tp,typename std::enable_if<std::is_signed<_Tp>::value&std::is_integral<_Tp>::value,int>::type=0>outputHelper<_BufferSize>&operator<<(const _Tp&ret){_Tp _ret=_Tp(ret);if(_ret>=0){do{*m_tempBufCursor++='0'+_ret%10;_ret/=10;}while(_ret);do putChar(*--m_tempBufCursor);while(m_tempBufCursor>m_tempBuf);}else{putChar('-');do{*m_tempBufCursor++='0'-_ret%10;_ret/=10;}while(_ret);do putChar(*--m_tempBufCursor);while(m_tempBufCursor>m_tempBuf);}return*this;}template<typename _Tp,typename std::enable_if<std::is_unsigned<_Tp>::value&std::is_integral<_Tp>::value,int>::type=0>outputHelper<_BufferSize>&operator<<(const _Tp&ret){_Tp _ret=_Tp(ret);do{*m_tempBufCursor++='0'+_ret%10;_ret/=10;}while(_ret);do putChar(*--m_tempBufCursor);while(m_tempBufCursor>m_tempBuf);return*this;}template<typename _Tp,typename std::enable_if<std::is_floating_point<_Tp>::value,int>::type=0>outputHelper<_BufferSize>&operator<<(const _Tp&ret){if(ret<0){putChar('-');return*this<<-ret;}_Tp _ret=ret*m_floatRatio;uint64_t integer=_ret;if(_ret-integer>=0.4999999999)integer++;do{*m_tempBufCursor++='0'+integer%10;integer/=10;}while(integer);if(m_tempBufCursor>m_tempBufDot){do putChar(*--m_tempBufCursor);while(m_tempBufCursor>m_tempBufDot);putChar('.');}else{putS("0.");for(int i=m_tempBufDot-m_tempBufCursor;i--;)putChar('0');}do putChar(*--m_tempBufCursor);while(m_tempBufCursor>m_tempBuf);return*this;}outputHelper<_BufferSize>&operator<<(const char&ret){putChar(ret);return*this;}outputHelper<_BufferSize>&operator<<(const std::string&ret){putS(ret.data());return*this;}};template<uint64_t _BufferSize,uint64_t _BlockSize>inputHelper<_BufferSize,_BlockSize>&getline(inputHelper<_BufferSize,_BlockSize>&ih,std::string&ret){ret.clear();if(ih.getChar_Checked()==EOF)ih.setState(false);else{while(!inputHelper<_BufferSize,_BlockSize>::isEndline(ih.getChar_Checked())){ret+=ih.getChar_Unchecked();ih.next();}ih.next();}return ih;}}using OY::getline;
template<__uint128_t __mod,bool __isprime=true>class DynamicModInt{public:using u32=uint64_t;using i64=__int128_t;using u64=__uint128_t;using m64=DynamicModInt;using value_type=u64;static inline u64 mod(){return s_mod;}static inline u64 get_primitive_root_prime(){if(!s_isPrime)return 0;u64 tmp[500]={};u64 cnt=0;const u64 phi=s_mod-1;u64 m=phi;for(u64 i=2;i*i<=m;++i){if(m%i==0){tmp[cnt++]=i;do m/=i;while(m%i==0);}}if(m!=1)tmp[cnt++]=m;for(m64 res=2;;res+=1){bool f=true;for(int i=0;i<cnt&&f;++i)f&=res.pow(phi/tmp[i])!=1;if(f)return u64(res);}}constexpr DynamicModInt():v_(){}~DynamicModInt()=default;template<typename T,typename std::enable_if<std::is_arithmetic<T>::value||std::is_same<T,i64>::value||std::is_same<T,u64>::value,int>::type=0>inline DynamicModInt(T v):v_(reduce(mul(norm(v%i64(s_mod)),r2))){}constexpr DynamicModInt(const m64&)=default;inline u64 val()const{return reduce({0,v_});}template<typename T,typename std::enable_if<std::is_arithmetic<T>::value||std::is_same<T,i64>::value||std::is_same<T,u64>::value,int>::type=0>explicit constexpr operator T()const{return T(val());}inline m64 operator-()const{m64 res;res.v_=(s_mod&-(v_!=0))-v_;return res;}inline m64 inv_exgcd()const{i64 x1=1,x3=0,a=val(),b=s_mod;while(b!=0){i64 q=a/b,x1_old=x1,a_old=a;x1=x3,x3=x1_old-x3*q,a=b,b=a_old-b*q;}return m64(x1);}inline m64 inv_fermat()const{return pow(s_mod-2);}inline m64 inv()const{return s_isPrime?inv_fermat():inv_exgcd();}inline m64&operator=(const m64&)=default;inline m64&operator+=(const m64&rhs){v_+=rhs.v_-s_mod;v_+=s_mod&-(v_>>127);return*this;}inline m64&operator-=(const m64&rhs){v_-=rhs.v_;v_+=s_mod&-(v_>>127);return*this;}inline m64&operator*=(const m64&rhs){v_=reduce(mul(v_,rhs.v_));return*this;}inline m64&operator/=(const m64&rhs){return operator*=(rhs.inv());}friend inline m64 operator+(const m64&lhs,const m64&rhs){return m64(lhs)+=rhs;}friend inline m64 operator-(const m64&lhs,const m64&rhs){return m64(lhs)-=rhs;}friend inline m64 operator*(const m64&lhs,const m64&rhs){return m64(lhs)*=rhs;}friend inline m64 operator/(const m64&lhs,const m64&rhs){return m64(lhs)/=rhs;}friend inline bool operator==(const m64&lhs,const m64&rhs){return lhs.v_==rhs.v_;}friend inline bool operator!=(const m64&lhs,const m64&rhs){return lhs.v_!=rhs.v_;}template<typename _Istream>friend inline _Istream&operator>>(_Istream&is,m64&rhs){i64 x;is>>x;rhs=m64(x);return is;}template<typename _Ostream>friend _Ostream&operator<<(_Ostream&os,const m64&rhs){return os<<rhs.val();}inline m64 pow(u64 y)const{m64 res(1),x(*this);for(;y!=0;y>>=1,x*=x)if(y&1)res*=x;return res;}static inline void set_mod(u64 mod,bool prime=true){s_mod=mod;s_isPrime=prime;r=get_r();r2=get_r2();}static inline u64 init(u64 val){return reduce(mul(val,r2));}private:static constexpr std::pair<u64,u64>mul(u64 x,u64 y){u64 a=x>>64,b=u32(x),c=y>>64,d=u32(y),ad=a*d,bc=b*c;return{a*c+(ad>>64)+(bc>>64)+(((ad&~UINT64_C(0))+(bc&~UINT64_C(0))+(b*d>>64))>>64),x*y};}static constexpr u64 mulh(u64 x,u64 y){u64 a=x>>64,b=u32(x),c=y>>64,d=u32(y),ad=a*d,bc=b*c;return a*c+(ad>>64)+(bc>>64)+(((ad&~UINT64_C(0))+(bc&~UINT64_C(0))+(b*d>>64))>>64);}static inline u64 get_r(){u64 two=2,iv=s_mod*(two-s_mod*s_mod);iv*=two-s_mod*iv;iv*=two-s_mod*iv;iv*=two-s_mod*iv;iv*=two-s_mod*iv;return iv*(two-s_mod*iv);}static inline u64 get_r2(){u64 iv=-u64(s_mod)%s_mod;for(int i=0;i!=128;++i)((iv<<=1)>=s_mod)&&(iv-=s_mod);return iv;}static constexpr u64 reduce(const std::pair<u64,u64>&x){u64 res=x.first-mulh(x.second*r,s_mod);return res+(s_mod&-(res>>127));}static constexpr u64 norm(i64 x){return x+(s_mod&-(x<0));}u64 v_;static inline u64 s_mod=__mod;static inline u64 s_isPrime=__isprime;static inline u64 r=get_r();static inline u64 r2=get_r2();};using mint=DynamicModInt<3,true>;
bool prime(const __uint128_t&x){static constexpr __uint128_t first_prime[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};if(x<=100)return std::binary_search(first_prime,first_prime+25,x);mint::set_mod(x,false);const mint one(1),none(-1);__uint128_t y(x-1);const unsigned iend=my_countr_zero(y);y>>=iend;for(mint base:{2,7,61,325}){mint z(base.pow(y));if(z.val()==1)continue;unsigned i=0;for(;i^iend;i++){if(z==none)break;z*=z;}if(i==iend)return false;}return true;}
uint64_t seed=5489ull;static std::mt19937_64 rng;__uint128_t gcd(__uint128_t a,__uint128_t b){if(!a||!b)return a|b;int i=my_countr_zero(a),j=my_countr_zero(b),k=std::min(i,j);a>>=i;b>>=j;while(true){if(a<b)std::swap(a,b);if(!(a-=b))break;a>>=my_countr_zero(a);}return b<<k;}
template<typename _Tp>struct Cipolla{static inline _Tp legrende(unsigned a){return _Tp(a).pow((_Tp::mod()-1)>>1);}static inline std::pair<_Tp,_Tp>find_nsqr(unsigned n){_Tp none(-1);for(unsigned i=sqrt(n)+1e-6+1;i<_Tp::mod();i++)if(unsigned tmp(i*i-n);legrende(tmp)==none)return{_Tp(i),_Tp(tmp)};return none;}static inline _Tp a,n,c;static inline void set_nsqr(unsigned n){_Tp none(-1);for(unsigned i=sqrt(n)+1e-6+1;i<_Tp::mod();i++)if(unsigned tmp(i*i-n);legrende(tmp)==none){a=i;c=tmp;return;}}struct cp{_Tp _M_real,_M_imag;public:cp(const _Tp&r,const _Tp&i):_M_real(r),_M_imag(i){}cp(const _Tp&r=_Tp()):_M_real(r),_M_imag(0){}cp(const cp&o):_M_real(o._M_real),_M_imag(o._M_imag){}cp(cp&&o):_M_real(o._M_real),_M_imag(o._M_imag){}public:cp&operator=(const cp&o){_M_real=o._M_real;_M_imag=o._M_imag;return*this;}cp&operator=(const _Tp&o){_M_real=o;_M_imag=0;return*this;}public:~cp(){_M_real=0;_M_imag=0;}public:cp operator+(const cp&o)const{return cp(_M_real+o._M_real,_M_imag+o._M_imag);}cp operator*(const cp&o)const{return cp(_M_real*o._M_real+_M_imag*o._M_imag*c,_M_real*o._M_imag+_M_imag*o._M_real);}friend cp operator-(const cp&o){return cp(-o._M_real,-o._M_imag);}cp operator-(const cp&o)const{return*this+-o;}public:cp&operator+=(const cp&o){return*this=*this+o;}cp&operator*=(const cp&o){return*this=*this*o;}cp&operator-=(const cp&o){return*this=*this-o;}public:_Tp&real(){return _M_real;}_Tp&imag(){return _M_imag;}const _Tp&real()const{return _M_real;}const _Tp&imag()const{return _M_imag;}cp conj()const{return cp(_M_real,-_M_imag);}};static cp qpow(const cp&bs,unsigned po){cp ans(1,0),base(bs);while(po){if(po&1)ans*=base;base*=base;po>>=1;}return ans;}static inline _Tp get_sqr(const _Tp&nn){n=nn;if(n==_Tp(0))return _Tp(0);if(legrende(n.val())!=1)return _Tp(-1);set_nsqr(n.val());return qpow(cp(a,1),(_Tp::mod()+1)>>1).real();}static inline _Tp get_sqr_unchecked(const _Tp&nn){n=nn;set_nsqr(n.val());return qpow(cp(a,1),(_Tp::mod()+1)>>1).real();}};
__uint128_t rho(__uint128_t value){mint::set_mod(value,false);mint x,y,z,c;uint64_t i,j;while(true){y=x=rng();z=1;c=rng();i=0;j=1;while(++i){y=y*y+c;z*=(x.val()>y.val())?(x-y):(y-x);if(x==y||!z.val())break;if(!(i&127)||i==j){if(__uint128_t g=gcd(z.val(),value);g>1)return g;if(i==j){x=y;j<<=1;}}}}}
__uint128_t squfof(__uint128_t value){__uint128_t s=sqrtl(1.0l*value)+1e-6;while(s*s>value)s--;if(s*s==value)return s;__int128 d,po,p,p_prev,q,q_prev,q_,b,r;long long l,b_,i;int k=0;l=2*sqrtl(2.0l*s);b_=3*l;if(b_>20000000)return rho(value);while(++k){d=k*value;po=p_prev=p=sqrtl(1.0l*d);q_prev=1;q=d-po*po;while(q<0){po--;p_prev--;p--;q=d-po*po;}if(!q)return gcd(value,k);for(i=2;i<b_;i++){b=(po+p)/q;p=b*q-p;q_=q;q=q_prev+b*(p_prev-p);r=sqrtl(1.0*q)+1e-6;if(!(i&1)&&r*r==q)break;q_prev=q_;p_prev=p;}if(i>=b_)continue;b=(po-p)/r;p_prev=p=b*r+p;q_prev=r;q=(d-p_prev*p_prev)/q_prev;i=0;do{b=(po+p)/q;p_prev=p;p=b*q-p;q_=q;q=q_prev+b*(p_prev-p);q_prev=q_;i++;}while(p!=p_prev&&i<b_);if(i>=b_)continue;r=gcd(value,q_prev);if(r!=1)return r;}return 0;}
template<typename _ModType>class barrett{_ModType _M_mod;int _M_l;__uint128_t _M_inv;static constexpr auto _Nd=std::numeric_limits<_ModType>::digits;static constexpr auto _Nd_ull=std::numeric_limits<uint64_t>::digits;static constexpr auto _Nd_ul=std::numeric_limits<unsigned long>::digits;static constexpr auto _Nd_u=std::numeric_limits<unsigned>::digits;public:static_assert(std::is_integral<_ModType>::value&&std::is_unsigned<_ModType>::value,"_ModType must be an unsigned integral type");constexpr barrett()=default;constexpr barrett(const _ModType&mod):_M_mod(mod),_M_l(_Nd_ull+_Nd-__builtin_clzll((uint64_t)mod)-((mod&(mod-1))!=0)),_M_inv(((unsigned __int128)1<<_M_l)/mod+((mod&(mod-1))!=0)){}constexpr void set_mod(const _ModType&mod){_M_mod=mod;_M_l=_Nd_ull+_Nd-__builtin_clzll((uint64_t)mod)-((mod&(mod-1))!=0);_M_inv=((unsigned __int128)1<<_M_l)/mod+((mod&(mod-1))!=0);}constexpr _ModType mod()const{return _M_mod;}constexpr _ModType mod(const _ModType&x)const{__uint128_t tmp=_M_inv*x;_ModType ret=x-(tmp>>_M_l)*_M_mod;return ret;}};
namespace qs {
const size_t L=256;uint32_t pcnt,root[L];mint primes[L];double log_primes[L];struct word{std::bitset<L>mask;mint lhs,rhs;size_t bit;word():mask(),lhs(),rhs(),bit(L){}void merge(const word&rOther){lhs*=rOther.lhs;rhs*=rOther.rhs;const std::bitset<L>cons(mask&rOther.mask);for(size_t pos=cons._Find_first();pos<L;pos=cons._Find_next(pos))rhs*=primes[pos];mask^=rOther.mask;bit=mask._Find_first();}bool operator<(const word&rOther)const{return bit<rOther.bit;}};
std::vector<word>smooth;std::unordered_map<long long,word>data;__uint128_t insert(word&o){size_t x;for(x=0;x<smooth.size();x++){if(smooth[x].bit>o.bit)break;if(smooth[x].bit==o.bit)o.merge(smooth[x]);}if(o.bit==L){__uint128_t g(gcd((o.lhs+o.rhs).val(),mint::mod()));if(g!=1&&g!=mint::mod())return g;}smooth.insert(smooth.begin()+x,o);return 0;return 0;}__int128 try_insert(mint x,__int128 y){word ins;ins.lhs=x;ins.rhs=1;for(size_t k=1;k<=pcnt;k++){size_t cnt=0;while(y%(__int128)primes[k].val()==0)y/=(__int128)primes[k].val(),++cnt;if(cnt){ins.mask[k]=cnt&1;ins.rhs*=primes[k].pow(cnt>>1);}}ins.bit=ins.mask._Find_first();if(y!=1){if(data.count(y)){ins.merge(data[y]);ins.rhs*=mint(y);y=1;}else data[y]=ins;}if(y==1)return insert(ins);return 0;}
void append(uint32_t p){++pcnt;primes[pcnt]=p;log_primes[pcnt]=log(1.0*p);}uint32_t fastpow(__uint128_t base,uint32_t power,uint32_t mod){barrett<uint32_t>brt(mod);base%=mod;uint32_t ans=1;for(;power;base=brt.mod(base*base),power>>=1)if(power&1)ans=brt.mod(ans*base);return ans;}void init(){using mint_=DynamicModInt<5,true>;uint32_t i,j;__uint128_t value=mint::mod();uint32_t B=pow(log(1.0*mint::mod()),2)*0.6;std::vector<char>mark((B>>1)+5);for(i=3;i*i<=B;i+=2)if(!mark[i>>1])for(j=i*i;j<=B;j+=i<<1)mark[j>>1]=true;for(append(2u),i=3;i<=B;i+=2)if(!mark[i>>1])if(fastpow(value,i>>1,i)==1)append(i);root[1]=value%2;for(i=2;i<=pcnt;i++)mint_::set_mod(primes[i].val(),true),root[i]=Cipolla<mint_>::get_sqr(value).val();}__uint128_t next_prime(__uint128_t x){x+=~x&1;while(!prime(x+=2));return x;}
__uint128_t quadratic_sieve(__int128 value){if(__int128 tmp=sqrtl(1.0*value)+1e-6;tmp*tmp==value)return tmp;static constexpr __uint128_t first_prime[30]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113};for(int i=1;i<30;i++)if(value%first_prime[i]==0)return first_prime[i];if(value<=1024)return squfof(value);pcnt=0;data.clear();smooth.clear();mint::set_mod(value,false);init();uint32_t M=pcnt*50;uint64_t D=sqrtl(sqrtl(2.0L*value)/M);double bound=log(M*sqrtl(0.5L*value))*0.75;barrett<uint64_t>brt;while(true){do D=next_prime(D);while((D&3)==1);mint::set_mod(D,true);uint64_t y0;mint y1;{mint tmp_value(value);if(!tmp_value.val())return D;mint tmp_y0=tmp_value.pow((D+1)>>2);if(tmp_y0*tmp_y0!=tmp_value)continue;y0=tmp_y0.val();y1=(value-y0*y0)/D;y1=y1*(D/2+1)/tmp_y0;}__int128 A(D);A*=A;__int128 B(y1.val()*D+y0);__int128 C((B*B-value)/A);mint::set_mod(value,false);__int128 E=(mint(B)/D).val();std::vector<double>pos(M),neg(M);for(uint32_t x=1;x<=pcnt;x++){uint32_t p=primes[x].val();brt.set_mod(p);uint32_t s=brt.mod(A);uint32_t a=s;uint32_t inv_a=1;if(!a)continue;while(a>1)inv_a=brt.mod(1ull*(p-inv_a)*(p/a)),a=p%a;uint32_t u=brt.mod(1ull*(p-brt.mod(B))*inv_a);uint32_t v=brt.mod(1ull*root[x]*inv_a);uint32_t r1=brt.mod(u+v),r2=brt.mod(u+p-v);for(uint32_t su=0;su<M;su+=p){if(su+r1<M)pos[su+r1]+=log_primes[x];if(su+r2<M)pos[su+r2]+=log_primes[x];if(su>=r1)neg[su-r1]+=log_primes[x];if(su>=r2)neg[su-r2]+=log_primes[x];}}for(uint32_t x=0;x<M;++x){if(pos[x]>bound)if(__uint128_t tmp(try_insert(E+D*x,A*x*x+2*B*x+C));tmp)return tmp;if(neg[x]>bound)if(__uint128_t tmp(try_insert(E-D*x,A*x*x-2*B*x+C));tmp)return tmp;}}return value;}
}
main(){OY::inputHelper<1<<18,20>cin("");OY::outputHelper<1<<18>cout("");__uint128_t x=0;cin>>x;__check_time_helper<std::chrono::high_resolution_clock>_Helper;_Helper.start();__uint128_t factor=qs::quadratic_sieve(x);_Helper.stop();if(factor>x/factor)factor=x/factor;cout<<factor<<' '<<x/factor;}