r=range
def q():
 for x in r(2,10301):
  b=1
  for i in r(2,x):
   if x%i==0:b=0;break
  if b:yield x
z=set(q())
for n in r(10000,10301):
 s=n;t=1
 for p in z:
  if n%p==0:s*=p-1;t*=p
 print s/t