#import<bits/stdc++.h>
#import<boost/multiprecision/cpp_int.hpp>
#define B begin()
#define E end()
#define Z size()
#define F first
#define C second
#define W vector
#define P push_back
#define R for
#define O auto
#define Q if
#define N;using
#define T insert
N namespace boost::multiprecision;N namespace std;N U=int1024_t;N A=array<U,2>N V=array<pair<U,W<U>>,2>N _=int64_t;void M(W<A>*f,W<int>*G,W<A>*q,int x,int ct,int nt,promise<U>*pr){U m=0,g0,g1,f0,f1,n,K,o;R(size_t i=0,j,k,$=3<<30;i<f->Z;i++)Q(i%nt==ct){A h={1,1};R(j=0;j<2;j++)R(n=(*f)[i][j],k=0;n>0;n>>=1,k++)Q(n%2)h[j]*=(*G)[k];R(A j:*q){g0=h[0]*j[0],g1=h[1]*j[1];_*k,f2,f3,n2;W<U>d;W<_>e;Q(g0>g1)swap(g0,g1);f0=g0;R(f1=g1;f0>1&&(f0>=~$||f1>=~$);f1=n)n=f0,d.P(f1/f0),f0=f1%f0;Q(f0>1)R(f2=(_)f0,f3=(_)f1;f2>1;f3=n2)n2=f2,e.P(f3/f2),f2=f3%f2;f2=0;f3=1;R(k=&*e.E;k--!=&e[0];f2=n2)n2=f3,f3=*k*f3+f2;f0=f2;f1=f3;R(U*k=&*d.E;k--!=&d[0];f0=n)n=f1,f1=*k*f1+f0;K=(x*f0+g0/2)/g0,o=min(abs(f1*x-g1*K)*g0,abs(f0*x-g0*K)*g1);Q(!m||o<m)m=o;}}pr->set_value(m);}double tt,rt;main(){int nt=8,x,mp,i,j,k,cn;R(bool e,D;cin>>x;){O X=chrono::system_clock::now();W<array<set<int>,2>>v(x-1),nv;W<pair<A,int>>r,s;W<A>f;map<int,int>c,ns;set<int>y;U t=i=1,m,o;R(mp=0;++i<x;)Q(!v[i-1][0].Z){R(j=0;++j<=~-x/i;v[x-i*j-1][1].T(i))v[i*j-1][0].T(i);Q(x%i<1)t*=i;else Q(!mp)mp=i;}Q(v[cn=0][1].Z!=1)R(O i:v){Q(i[e=0].Z)R(O j:i[0])Q(t%j<1){e=1;break;}Q(!e){Q(i[j=0].Z?*i[0].B!=mp:mp)nv.P(i);R(;j<2;)R(O k:i[j++]){O n=c.find(k);Q(n==c.E)c.T(make_pair(k,1));else n->C++;}}}W<int>G;W<V>bs;R(O i:v=nv)Q(i[0].Z==1&&c[j=*i[0].B]<3&&c[k=*i[1].B]<3){Q(j!=k)j*=k;Q(!y.count(j))y.T(j);}else{V b;R(j=0;j<2;j++){b[j].F=0;R(O k:i[j]){O n=ns.find(k);b[j].C.P(m=U(1)<<(n==ns.E?ns.T(make_pair(k,cn)),G.P(k),cn++:n->C));b[j].F|=m;}}bs.P(b);}sort(bs.B,bs.E,[](V&x,V&y){return min(x[0].F,x[1].F)<min(y[0].F,y[1].F);});R(r.P(make_pair(A{U(1)<<ns[mp],D=0},0));!D&&r.Z>0;r=s){s.clear();R(O i:r){R(;i.C<bs.Z&&(i.F[e=0]&bs[i.C][0].F||i.F[1]&bs[i.C][1].F);i.C++);Q(i.C==bs.Z)D=1,f.P(i.F);else R(j=0;j<2;j++)R(O k:bs[i.C][j].C)Q(!(i.F[0]&k||i.F[1]&k)){A b{i.F[0],i.F[1]};b[j]|=k;s.P(make_pair(b,i.C+1));}}sort(s.B,s.E);s.erase(unique(s.B,s.E),s.E);}Q(D){O i=y.Z;W<A>q(1<<i);R(j=0;j<1<<i;q[j++][0]*=t){q[j]={1,1};O l=y.B;R(k=0;k<i;k++)q[j][(j&1<<k)/(1<<k)]*=*l++;}W<thread>ts(min(f.Z,(size_t)nt));W<promise<U>>ps(ts.Z);R(i=0;i<ts.Z;i++)ts[i]=thread(&M,&f,&G,&q,x,i,nt,&ps[i]);R(m=i=0;i<ts.Z;)Q(ts[i].join(),o=ps[i++].get_future().get(),!m||o<m)m=o;tt+=rt=(double)((chrono::duration<double>)(std::chrono::system_clock::now()-X)).count();cout<<x<<"->"<<m<<" : "<<rt<<" secs;total "<<tt<<" secs\n";}}}