[C언어] 서로소

서로소의 개수를 구하는 오일러 파이 함수를 사용하는 문제다.

혹시 오일러 파이 함수가 뭔지 모른다 싶으면 위키백과를 찾아보고

이 문제를 풀 때 필요한 성질만 알고 싶다 싶으면 이 링크로

DESCRIPTION

두 수의 최대공약수가 1인 것을 서로소라고 한다.

1이상 n이하의 수 중 n과 서로소인 정수의 갯수를 구해보자.

INPUT

Line 1: 입력의 갯수 N

Line 2~N+1: 자연수 n

OUTPUT

1~N: n과 서로소면서 n을 넘지 않는 양의 정수 갯수를 출력한다.

SAMPLE INPUT

3
24
36
47

SAMPLE OUTPUT

8
12
46