题目描述

小$\red{X }$是一位热爱数学的男孩子，在茫茫的数字中，他对质数更有一种独特的情感。小$\red{X }$认为，质数是一切自然数起源的地方。

在小$\red{X }$的认知里，质数是除了本身和$\red{1 }$以外，没有其他因数的数字。

但由于小$\red{X }$对质数的热爱超乎寻常，所以小$\red{X }$同样喜欢那些虽然不是质数，但却是由两个质数相乘得来的数。

于是，我们定义，一个数是小$\red{X }$喜欢的数，当且仅当其是一个质数，或是两个质数的乘积。

而现在，小$\red{X }$想要知道，在$\red{L }$到$\red{R }$之间，有多少数是他喜欢的数呢？

输入格式

第一行输入一个正整数$\red{Q，}$表示询问的组数。

接下来$\red{Q }$行。包含两个正整数$\red{L }$和$\red{R}$。保证$\red{L≤}$$\red{R}$。

输出格式

输出$\red{Q }$行，每行一个整数，表示小$\red{X }$喜欢的数的个数。

样例

输入样例1

1

1 6

输出样例1

5

输入样例2

10

282 491

31 178

645 856

227 367

267 487

474 697

219 468

582 792

315 612

249 307

输出样例2

97

78

92

65

102

98

114

90

133

29

输入样例3

10

20513 96703

15236 86198

23185 78205

40687 48854

42390 95450

63915 76000

36793 92543

35347 53901

44188 76922

82177 90900

输出样例3

24413

23001

17784

2669

16785

3833

17712

6028

10442

2734

提示

数据范围