描述

给定 n，一个正整数，有多少个小于 n 的正整数相对于 n 来说是素数？如果没有整数 x > 1、y > 0、z > 0，使得 a = xy 和 b = xz，则两个整数 a 和 b 是相对素数。

输入

有几个测试用例。对于每个测试用例，标准输入包含一行 n <= 1,000,000,000。包含 0 的行跟在最后一种情况之后。

输出

对于每个测试用例，应该有一行输出来回答上面提出的问题。

输入数据 1

7
12
0

输出数据 1

6
4

来源

Waterloo local 2002.07.01