Anyone who studies math will be mesmerized by Prime Number, so does Anduril.
Anduril likes all numbers which could be presented by the product of 2 prime numbers.
Unfortunately, even if Anduril majors in mathematics, he still considers 1 as a prime number.
You need to find out how many numbers are Anduril's favorite numbers in [l, r].
输入描述:
There are multiple test cases.
The First line is the quantity of test cases T.
The following T lines are test cases.
Each test case has exactly one line with 2 integers l, r.
输出描述:
For each test case, output one line with one number which is the quantity of Anduril's favorite numbers.
示例2
输入
复制
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
备注:
1 <= I, r <= 10^7
1 <= T <= 100