



"""simple docstring"""
def 			_SCREAMING_SNAKE_CASE						(__lowerCAmelCase = 1_00_00_00							) ->						int:







  '''simple docstring'''


  lowercase_								= set(range(3 ,  __lowerCAmelCase ,  2							)							)
  primes.add(2							)
  for p in range(3 ,  __lowerCAmelCase ,  2							):
    if p not in primes:
      continue
    primes.difference_update(set(range(p * p ,  __lowerCAmelCase ,  __lowerCAmelCase							)							)							)

  lowercase_								= [float(__lowerCAmelCase							) for n in range(limit + 1							)]

  for p in primes:
    for n in range(__lowerCAmelCase ,  limit + 1 ,  __lowerCAmelCase							):
      phi[n] *= 1 - 1 / p

  return int(sum(phi[2:]							)							)


if __name__ == "__main__":
       print(F"{solution() = }")






"""simple docstring"""
def 			_SCREAMING_SNAKE_CASE						(__lowerCAmelCase							) ->						list[list[int]]:







  '''simple docstring'''


  lowercase_								= []
  if len(__lowerCAmelCase							) == 1:
    return [nums.copy()]
  for _ in range(len(__lowerCAmelCase							)							):
    lowercase_								= nums.pop(0							)
    lowercase_								= permute(__lowerCAmelCase							)
    for perm in permutations:
      perm.append(__lowerCAmelCase							)
    result.extend(__lowerCAmelCase							)
    nums.append(__lowerCAmelCase							)
  return result


def 			_SCREAMING_SNAKE_CASE						(__lowerCAmelCase							) ->						Tuple:







  '''simple docstring'''


  def backtrack(__lowerCAmelCase							):
    if start == len(__lowerCAmelCase							) - 1:
      output.append(nums[:]							)
    else:
      for i in range(__lowerCAmelCase ,  len(__lowerCAmelCase							)							):
        lowercase_					,    lowercase_								= nums[i], nums[start]
        backtrack(start + 1							)
        lowercase_					,    lowercase_								= nums[i], nums[start]  # backtrack

  lowercase_								= []
  backtrack(0							)
  return output


if __name__ == "__main__":
       import doctest

       # use res to print the data in permute2 function
       UpperCAmelCase						:		Optional[Any]			= permutea([1, 2, 3])
       print(res)
       doctest.testmod()

