Farabi is a very attentive student and as usual he gets CGPA 4 out of 4.

On these behalf he wants to arrange a party.

Though he is a good student he isn't a good person of pure heart. He hates too many people.

But the reason behind his hating other people are weird.

His roll number is the last roll number in the class and it also indicates the number of students present in his class where the roll number starts with 1.

He hates the person with roll number with whom the common divisor is equal to or greater than 2.

He doesn't want to invite them.

But he is confuse with the number of people he is going to invite.

Can you help him?

Input

There will be only one line of input which is an integer n (1 <= n <= 10^9).

Output

Output the expected result in one line.

Example

Input:
1

Output:
1