시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 61 20 15 30.612%

문제

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

두 정수 a와 b가 서로소가 되려면 x > 1, y > 0, z > 0이면서, a = xy, b= xz를 만족하는 정수가 없어야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 n ≤ 1,000,000,000으로 이루어져 있다.

입력의 마지막 줄에는 0이 주어진다.

출력

입력으로 주어진 n마다 n보다 작으면서 서로소인 양의 정수의 수를 출력한다.

예제 입력

7
12
0

예제 출력

6
4

힌트