003 - ゴールドバッハ予想

問題

ゴールドバッハ予想とは「6以上のどんな偶数も、2つの素数※1の和として表わすことができる」 というものです。

たとえば、偶数の12や18は

12=5+7, 18=5+13=7+11

などと表せます。

和が134となる2つの素数の組み合せをすべて書き出すと、以下の通りとなります。

  134 =3+131 =7+127 =31+103 =37+97 =61+73 =67+67
       =131+3 =127+7 =103+31 =97+37 =73+61

与えられた数が大きくなると、いくらでも素数の組み合せが見つかるような気がします。しかし、 現代数学をもってしてもこの予想を証明することも、反例を作ることもできません※2。ちょっと不 思議な感じがしますね。

そこで、ゴールドバッハ予想を鑑賞するために、偶数 n を入力とし、和がnとなる2つの素数の組 み合せの数を求めるプログラムを作成してください。

和がnとなる素数の組み合せの数とは n = p+q かつ p ≦ q であるような正の素数 p、q の組み合 せの数です。上の例からわかるように和が 134 となる素数の組み合せは6個です。ただし、n は 6 以上 1000,000 以下の偶数とします。

※1 素数とは、1または自分自身以外に約数を持たない整数のことである。なお、1は素数ではない。
※2 2007年2月現在、5×1017 までの全ての偶数について成り立つことが確かめられている。(Wikipedia)

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されま す。 各データセットは以下のとおりです。

 1行目 偶数 n

出力

入力データセット毎に素数の組み合せの数を出力します。

入出力例

入力例

134
4330
34808
98792
0

出力例

6
72
274
607