서로소

양의 정수 $n$이 주어졌을 때, $n$보다 작은 양의 정수 중에서 $n$과 서로소인 수의 개수를 구하는 프로그램을 작성하시오.

두 정수 $a$와 $b$가 서로소라는 것은, $x > 1$인 정수 $x$와 양의 정수 $y$, $z$에 대해 $a = xy$이고 $b = xz$가 되는 경우가 존재하지 않는다는 뜻이다. 즉, $a$와 $b$의 공약수가 $1$뿐이라는 것과 같다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 정수 $n$ 하나로 주어지며, $1 \le n \le 1{,}000{,}000{,}000$이다.

입력의 마지막 줄에는 $0$이 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 $n$보다 작은 양의 정수 중에서 $n$과 서로소인 수의 개수를 한 줄에 하나씩 출력한다.