暂无测试数据。

蒜头君对数字非常敏感，他非常钟爱质数，因此他的幸运数字也与质数有关。

蒜头君的幸运数字有两种，假设 $x$ 是蒜头君的幸运数字：

1. $x$ 是质数。
2. $x$ 不是质数，但是 $x$ 可以是两个质数的积。

现在蒜头君想要知道在区间 $[L,R]$ 中有多少个幸运数字。

质数是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数，例如 $2,3,5,7,11,\cdots$。

输入格式

第一行输入一个正整数 $Q$，表示数据的组数。

接下来 $Q$ 行。包含两个正整数 $L$ 和 $R$，表示区间 $[L,R]$，保证 $L\leq R$。

输出格式

输出 $Q$ 行，每行一个整数，第 $i$ 行表示第 $i$ 组数据中区间 $[L,R]$ 中有多少个幸运数字。

数据范围与约定

1
1 6

5

10
282 491
31 178
645 856
227 367
267 487
474 697
219 468
582 792
315 612
249 307

97
78
92
65
102
98
114
90
133
29

10
20513 96703
15236 86198
23185 78205
40687 48854
42390 95450
63915 76000
36793 92543
35347 53901
44188 76922
82177 90900

24413
23001
17784
2669
16785
3833
17712
6028
10442
2734