谁和它互质

题目描述

给定正整数 n，统计闭区间 [1,n-1] 中与 n 互质的整数数量。两个正整数互质，当且仅当它们的最大公因数为 1。

输入格式

一行输入一个整数 n，满足 2≤n≤100000。

输出格式

输出 [1,n-1] 中满足 gcd(x,n)=1 的整数 x 的数量。

样例

输入

10

输出

4