The Totient Computer: Compute Euler's Totient ¤å(n)

In the Hall of Counting, the Royal Statistician needs to count numbers coprime to n. Euler's totient function ¤å(n) counts the integers from 1 to n that are coprime to n. For a prime p, ¤å(p) = p-1. For n = p1^a1 * p2^a2 * ..., ¤å(n) = n * product of (1 - 1/pi). "The totient function is central to number theory," the Statistician says. "Factorize n into primes, then apply the formula. For large n, efficient factorization is key." Given an integer n, compute ¤å(n). Constraints: 1 <= n <= 10^12 Input: 12 Output: 4 Input: 7 Output: 6