题目背景

在遥远的星海深处，有一座名为“数律塔”的古老建筑。传说数律塔中封存着无数星门，而每一扇星门都对应着一枚编号为 $N$ 的星纹徽章。只有真正理解“数之秩序”的旅人，才能唤醒徽章中的力量。

数律塔的守门人告诉小杨：每一枚星纹徽章都拥有一个正整数编号 $N$。若要开启与这枚徽章对应的星门，必须从 $1$ 到 $N$ 的编号中，找出所有与 $N$ 互质的编号。所谓互质，是指两个数的最大公约数为 $1$。这些编号会被化作一串串密钥碎片，而密钥碎片的数量，正是开启星门所需的力量值。

然而，数律塔的星门数量众多，编号也可能非常庞大。小杨无法逐一检查每一个编号，因此他需要你帮助他计算：在 $1$ 到 $N$ 中，究竟有多少个数与 $N$ 互质？

传说中，只有准确算出这个数量的人，才能让星门上的纹路重新亮起，继续踏上通往数律塔高层的旅途。

题目描述

给定一个正整数 $N$，请你计算在区间 $[1, N]$ 中，有多少个数与 $N$ 互质（即最大公约数为 $1$）。

因为结果可能很大，你只需要输出结果即可。

输入格式

第一行，包含一个正整数 $N$。

输出格式

一行，包含一个整数，表示在 $1$ 到 $N$ 中，与 $N$ 互质的数的个数。

输入输出样例

12

4

提示

【样例 1 解释】

对于 $N = 12$，在 $1$ 到 $12$ 中，与 $12$ 互质的数有：$1, 5, 7, 11$，共 $4$ 个。

【数据范围】