11. 箱子世界

0 Judge

Code: 0


箱子世界

sprout

題目敘述

為了收納所有的檔案,$Sylveon$購買了很多的箱子來擺放資料,但是因為箱子太多了,$Sylveon$為了避免東西放在那些箱子,他把所有的箱子由1開始編號,有趣的是,$Sylveon$發現所有具有質數編號的箱子都有東西,反之都沒有。

當$Sylveon$把所有的箱子依編號排成一排後,高興地邀請默默在偷窺的你來欣賞整齊的箱子,$Sylveon$隨意地帶你走到一排箱子前,你知道你眼前的箱子有多少個是有存放物品的嗎? 如果你能正確的告訴$Sylveon$,或許他就會送你一個$AC$

輸入說明

有多筆測資,不超過100筆,每筆測資佔1行。每筆測資包含兩個數$A B$,表示你眼前箱子最左邊與最右邊的編號。

在所有測試資料中:

  • $0 \leq A \leq B \leq 10^{12}$
  • $|A-B| \leq 10^6$

輸出說明

對於每一筆資料輸出一行,告訴$Sylveon$ $A~B$號箱子間有多少箱子是有存放物品的(頭尾皆包含)。

範例輸入

1 10
123456789 123466789

範例輸出

4
534

提示

整體的複雜度不大於$O(T \times nloglogn)$,$T$是測資筆數,$n$是詢問的區間大小。


Judge Setting

run-time limit: 600 ms
memory limit: 6553600 byte
測資數量: 0