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.