0151 - チェビシェフの定理

n が正の整数ならば，n より大きく 2n 以下の素数が1個以上存在する．このことはチェビシェフの定理またはベルトラン・チェビシェフの定理として知られている．ベルトラン(Joseph Louis François Bertrand, 1822–1900)が予想していたことを，1850年にチェビシェフ(Пафнутий Львович Чебышёв, 1821–1894)が証明した．ラマヌジャン(Srinivasa Aiyangar Ramanujan, 1887–1920)は，1919年に公表された論文で，初等的な証明を与えた．エルデシュ(Paul Erdős, 1913–1996)は，1932年に，別の初等的な証明を発見した．

たとえば，10より大きく20以下の素数は 11, 13, 17, 19 で，4個ある． 13より大きく26以下の素数は 17, 19, 23 で，3個ある．

あなたの使命は，与えられた正整数 n に対して，n より大きく 2n 以下の素数を数えるプログラムを書くことである． そのようなプログラムを使うと，個別の正整数に対してチェビシェフの定理が成り立つことを確認できる．

入力はデータセットの並びである． データセットは， ちょうど一つの正整数 n からなる行である． n ≤ 123456 と仮定してよい．

入力の終わりは，1文字のゼロからなる行で示される． これはデータセットではない．

出力は入力データセットと同数の行で構成されなければならない． 各行は一つの整数を含まなければならない． 余計な文字を含んではならない．

整数 n からなるデータセットに対応する出力の整数は，n < p ≤ 2n をみたす素数 p の個数でなくてはならない．

1
10
13
100
1000
10000
100000
0

1
4
3
21
135
1033
8392