哥德巴赫猜想

题目描述

众所周知，哥德巴赫猜想是说，任何大于2的偶数都能写成两个质数（素数）之和。例如：

• $4=2+2$
• $6=3+3$
• $8=3+5$
• $10=3+7=5+5$

聪明的你肯定想知道，对于大于2的偶数 $n$，它有多少种写成两个质数之和的方法。例如4、6和8都只有一种方法，10有两种方法。请你编写程序计算这个问题的答案。

在本题中，我们认为两种方案不同，当且仅当两种分解方案包含的素数互不相同；即 $10=3+7$ 和 $10=7+3$ 是同一种方案，不能重复计数。

输入格式

一行，一个大于2的偶数 $n$。

输出格式

一行，一个整数，表示将 $n$ 写成两个质数之和的方法数。

输入样例 1

14

输出样例 1

11

输入样例 2

110

输出样例 2

12

数据范围

对于40%的测试点，保证 $4\le n\le100$。

对于所有测试点，保证 $4\le n\le10^6$。

时间限制：1.0 s；内存限制：512.0 MB。