宝くじ
ある国の王様は素数とギャンブルが大好きです。この国の通貨の単位はプライムといいます。2007 年 11 月 1 日現在のプライムのクロス円レートは 9973 とちょうど素数になっていたので、王様は大喜びです。この国では 1/101 プライムを1サブプライムとする補助貨幣が使われています。
この国の政府は、国家財政の安定、国民の娯楽、王様の趣味を同時に満足させることを目的に宝くじ振興公社を設立し、宝くじ事業を始めることにしました。素数が大好きな王様は、素数が話題になればそれだけで満足して、賞金をあげたくなります。そこで振興公社は次のような宝くじを考えました。
- くじには 0 から MP までの一連の番号がつけられている。MP はこの国で知られている最大の素数で、毎月一日に官報で告示される。同時に、MP 以下のすべての素数も発表される。それ以上大きな素数が発見されても、その月の間は、宝くじ振興公社を含む全ての公的な機関では、一日に発表されたMP を最大の素数として扱う。2007 年 11 月 1 日 にはMP = 999983 (1000000 以下の最大の素数) が発表された。
- 宝くじの販売価格は 1 サブプライム。
- 宝くじの抽選では、当たりくじの番号 p と賞金算出のための数 m の組(p, m) が何組か選ばれる。p, m はそれぞれ0 以上 MP 以下の整数。
- この国で知られている素数の中で p - m 以上 p + m 以下のものが X 個あるとすると、抽選結果(p, m) の賞金は、X プライムとなる。
- 抽選結果 (p, m) の賞金 X プライムは番号 p の宝くじを持っている当選者に支払われるが、X = 0 の場合もあり、この場合には当選者には賞金は支払われない。
- 賞金のうち 1 プライムは宝くじの売り上げから支出され、X - 1 プライムは王様の内廷費から支出される（王様が払ってくれる）。X = 0 ならば宝くじの売り上げから 1 プライムが内廷費に繰り入れられる。（王様に対し支払われる）
- ひとつの番号 p が複数の当たりくじになることもある。この場合にはそれぞれの抽選結果(p, m) から算出される賞金の合計が当選者に支払われる。
このくじでは当たりくじを買った人は抽選結果から関係する素数を探し、その個数を数えるので、国民の話題に素数がよく出てきて王様はとてもご満悦です。宝くじ振興公社としては当たりくじ1本当たり公社負担が 1 プライム、販売価格が 1 サブプライムだから、当たりくじの本数 n を、販売した宝くじ 101 本あたり 1 本以下となるようにすれば (すなわち、n ≤ (販売した本数)/101 とすれば) 赤字にはなりません。
問題は内廷費からの支出額です。あなたの仕事は、抽選結果を入力として、2007 年 11 月における宝くじ振興公社が王様に請求する賞金の額を出力するプログラムを作成することです。ただし、請求する賞金の額が負になることはないものとします。
注意
- この国における素数の定義も日本の学校教育で学習する内容と同じです。即ち、素数とは 1 と自分自身以外の約数を持たない自然数をいいます（なお、1 は素数ではありません）。
- 我々は 1000003 が素数であることを知っていますが、この国では 2007 年 11 月段階では知られていません。そのため、999963 以上 1000003 以下の範囲にあるこの国で知られている素数は 999983 と 999979 の 2 個しかありません。
Input
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。
各データセットは以下の形式で与えられます。
n
p1 m1
p2 m2
:
pn mn
１行目に抽選結果の数 n (1 ≤ n ≤ 1000000)、続く n 行に i 番目の抽選結果の情報 pi, mi が空白区切りで与えられます。
データセットの数は 20 を超えません。
Output
データセットごとに王様への請求額をプライム単位（整数）で１行に出力します。
Sample Input
4
5 0
9 1
3 10
11 3
1
999983 20
0
Output for the Sample Input
5
1