#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef pair pii; const int INF=(1<<30); int f(long x){ int sum=0; while(x){ sum+=x%10; x/=10; } if(sum<10) return sum; else return f(sum); } vector get_Prime(long K,long N){ vector prime(N+1,true); prime[0]=prime[1]=false; for(long i=2;i*i<=N;i++){ if(prime[i]){ for(int j=2;i*j<=N;j++) prime[i*j]=false; } } vector res; for(long i=K;i<=N;i++) if(prime[i]) res.push_back(i); return res; } int main(){ long N; cin>>N; vector prime=get_Prime(0,N); vector is_kachi(N+1,false); //必要 is_kachi[0]=is_kachi[1]=true; is_kachi[4]=true; for(long i=5;i<=N;i++){ for(int j=0;prime[j]<=i && j