H. Bessie and GCD
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For two positive integers $$$l, r$$$, $$$f(l, r)$$$ is defined as the number of ordered pairs $$$(a, b)$$$ such that $$$l \le a + b \le r$$$, $$$a$$$ and $$$b$$$ are positive, and $$$\text{gcd}(a, b) = p$$$, where $$$p$$$ is a prime number.

There will be $$$q$$$ queries of the form $$$l, r$$$. For each query, output $$$f(l, r)$$$.

Input

The first line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$). Then $$$q$$$ lines follow, each containing two integers $$$l, r$$$ ($$$2 \le l \le r \le 2 \cdot 10^5$$$).

Output

Print $$$q$$$ lines, each containing one integer, $$$f(l, r)$$$.

Example
Input
2
10 11
53 67670
Output
5
629501299
Note

In the first query, the ordered pairs would be $$$(2, 8), (8, 2), (4, 6), (6, 4), (5, 5)$$$.