Description

小杨非常喜欢研究质数。他定义两个质数之间的“距离”为它们的差的绝对值。

现在给定一个正整数N，请你找出在1到N之间（包含1和N），有多少对质数(p1​,p2​)满足p2​−p1​=2。（注：满足该条件的质数对通常被称为“孪生素数”）。

Input Format

输入一行，包含一个正整数N。数据范围：1≤N≤1000000。

Output Format

输出一个整数，表示满足条件的质数对的数量。

20

4

Hint

在 20 以内，满足相差为 2 的质数对有：(3,5),(5,7),(11,13),(17,19)，共 4 对。

Source