R=range n=int(input()) P,t=set(),n for i in R(2,min(n+1,31623)): if t%i<1:P.add(i) while t%i<1:t//=i D=[t]*(t>1) def G(a,b): while a:a,b=b%a,a return b def r(t): for j in R(len(D)): while D[j]%t<1:D[j]//=t P.add(t) while D: t=D.pop() c=int(t**0.25) if t<10**9:r(t) else: while c: x,d=c,1 y=(x*x+1)%t while (d<2)*c:x,y,d,c=(x*x+1)%t,(y**4+2*y*y+2)%t,G(abs(x-y),t),c-1 if d