1023: 互质

Time Limit: 1 Sec Memory Limit: 128 MB

Submission：67 AC：36 Score：100.00

Description

给定正整数n,有多少个小于等于n的正整数与n互质,两个数互质的条件为两个数只有1这个共同的因子.

Input

只有一个正整数n.(n<=5000)

Output

输出有多少个与 n 互质的数

Samples

input:

9

output:

6