def m(n): x=bin(int(n))[2:][::-1] s=0 for i in range(1,len(x)): if x[i-1]=="1" and x[i]=="0": s+=i return s def gcd(a, b): while b: a, b = b, a % b return a def phi(n): s=0 for i in range(1,n+1): if gcd(i,n)==1: s+=1 return s def cototient(n): return n-phi(n) def a(n): return m(cototient(n)) for i in range(1,10001): print str(i)+" "+str(a(i))