import random def miller(x): if x==2:return True elif x>2 and x&1==0:return False s,t=0,x-1 while t&1==0: s,t=s+1,t>>1 a=random.randint(1,x-1) if pow(a,t,x)==1:return True for i in range(0,s): if pow(a,pow(2,i)*t,x)==x-1:return True return False n=int(input()) if n==1:print(1) else: a=10**5+1 p=[] ans=[] m=6 while len(p)