def f(n,arr,dp,v) if n==1 return v else if dp.key?([v,n])!=false return dp[[v,n]] end arr.size.times{|i| t=arr[i] if n%t==0 s=f(n/t,arr,dp,1-v) if v!=s dp[[v,n]]=s return s end end } dp[[v,n]]=v return dp[[v,n]] end end n=gets.to_i n2=n d=2 arr=[] while d*d<=n if n%d==0 d2=d while n%d == 0 n/=d arr<1 arr<