#include #include #include #include #include #include using namespace std; typedef long long ll; ll MOD = 1e9+7; bool dp[5000][5000];//dp[1個しかない素因数][2個以上ある素因数]=先手が勝つかどうか int main() { ll n; int ans=0; cin>>n; ll k=n; int c1=0; int c2=0; int cnt=0; while(k%2==0) { k/=2; cnt++; } if(cnt==1) c1++; else if(cnt>1) c2++; for(int i=3;i<11000;i+=2) { if(k==1) break; cnt=0; while(k%i==0) { k/=i; cnt++; } if(cnt==1) c1++; else if(cnt>1) c2++; } if(k!=1) c1++;//でかい素数の分 //ここからdp dp[0][0]=false; dp[1][0]=true; dp[0][1]=true; for(int i=2;i