output_description: The number of totatives in a line.
input_description: n
      
  
  An integer n (1 ≤ n ≤ 1000000000).
attempt: N = int(input())
  orgN = N
  div = []
  
  def bitsoncount(x):
      return bin(x).count('1')
  
  for d in range(2, N):
      if d*d > N:
          break
      if N % d == 0:
          div.append(d)
          while N % d == 0:
              N = N // d
  if N != 1: div.append(N)
  
  M = len(div)
  ans = 0
  for i in range(1, 2 ** M): # divを因数にもちうるものであるため、i=0は不適
      mul = 1
      bc = bitsoncount(i)
      for m in range(M):
          if i >> m & 1:
              mul *= div[m]
      if bc % 2 == 1:
          ans += orgN // mul
      else:
          ans -= orgN // mul
  
  ans = orgN - ans
  print(ans)
  
problem_description: Euler's Phi Function
  
    
  
  For given integer n, count the totatives of n, that is, the positive integers
  less than or equal to n that are relatively prime to n.
samples: [{"input": "6", "output": "2"}, {"input": "1000000", "output": "400000"}]