Background

牛牛最近正在研究双子质数。
所谓双子质数，就是指一对相差2的质数。虽然质数有无限个很容易被证明，但是到目前为止还无法证明双子质数是否有无限多个。

Description

出于好奇，牛牛想要对一些区间内双子质数的数量进行研究，这样也许会对证明双子质数的无限性有一些帮助。但是在真正面对数海时却遇到了麻烦。你能帮帮他吗？

Format

Input

第一行一个数T，表示数据组数。T<=123.
接下来T行每行两个正整数数，L，R，表示被询问到的区间。

Output

对于每组数据输出一个数，表示这一段区间内的双子质数个数。

Sample 1

Input

1
1 32

Output

5

Limitation

2s, 32MB for each test case.

对于所有数据，满足1<=L,R<=10^18另有如下约定：

数据点	L，R限制	其他限制
1	<=100	无
2	<=1000	无
3	<=23333	无
4	<=1000000	R-L<=2×10^5
5	<=1000000	R-L<=2×10^5
6	<=1000000	R-L<=2×10^5
7	L=1，R=10^8	T=1
8	<=3*10^9	R-L<=10000,你的答案与标准答案相差不超过3即被认为正确。
9	<=3*10^9	R-L<=10000,你的答案与标准答案相差不超过3即被认为正确。
10	<=3*10^9	R-L<=10000,你的答案与标准答案相差不超过3即被认为正确。

---

Hint

样例解释：3与5,5与7,11与13,17与19,29与31均是双子质数

Source

Orz WHN