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