一共有几种组队

题目描述

给定整数 n，统计满足 p≤q、p 和 q 均为质数且 p+q=n 的数对数量。交换 p、q 不产生新方案。

输入格式

一行输入整数 n，满足 4≤n≤1000000。

输出格式

输出不同无序质数拆分的数量；若没有方案，输出 0。

样例

输入

4

输出

1