#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair P; // using mint=modint998244353; // mint f[2000010], invf[2000010]; // void fac(int n){ // f[0]=1; // for(ll i=1; i<=n; i++) f[i]=f[i-1]*i; // invf[n]=f[n].inv(); // for(ll i=n-1; i>=0; i--) invf[i]=invf[i+1]*(i+1); // } // mint comb(int x, int y){ // if(!(0<=y && y<=x)) return 0; // return f[x]*invf[y]*invf[x-y]; // } set st[1000010]; int g[1000010]; int main() { for(int d=1; d<=1000000; d++){ for(int i=0; ; i++){ if(st[d].find(i)==st[d].end()){ g[d]=i;break; } } for(int i=2*d; i<=1000000; i+=d){ st[i].insert(g[d]); } } int n; cin>>n; int s=0; for(int i=0; i