An Euler's totient function is defined as $\varphi(n)$ is the number of $i$, $1 \le i \le n$, such that $i$ and $n$ are co-prime.
Your task is, given $a$ and $b$, to output $\varphi(a) + \varphi(a+1) + \ldots + \varphi(b)$.

Input:

First line of input contains $T$, number of testcases, $T \le 10^5$.
In each of next $T$ lines there is a pair of integers $a,b$, $1 \le a \le b \le 10^7$.

Output:

For each testcase, output a single integer, the answer to the problem.

Example:

3
6 6 
7 10
10 1000

2
20
304164

Explanation:
$\varphi(6) = 2$, and $\varphi(7) = 6$, $\varphi(8) = 4$, $\varphi(9) = 6$ and $\varphi(10) = 4$.