import math


def A000010(n: int) -> int:
    """Euler totient function phi(n): count numbers <= n and prime to n."""
    numbers = []
    i = 0
    for i in range(n):
        if math.gcd(i, n) == 1:
            numbers.append(i)
    return len(numbers)