n=int(input()) #プライムナンバーゲーム #エラトステネスの篩 prime=[] s=[1]*(n+1) s[0]=s[1]=0 for i in range(2,n,2): s[i]=0 for i in range(3,int(math.sqrt(n))): for j in range(2,math.ceil(n/i)): if s[i*j]==1: s[i*j]=0 for i in range(n): if s[i]==1: prime.append(i) winlose=[-1]*(n+1) #勝ち負けを記録するリスト +1が勝ち -1が負け winlose[0],winlose[1]=1,1 #0,1は入力に無いが便宜上勝ちとする for i in range(2,n+1): for j in prime: if i