You have landed in an ancient jungle, which is made to trap all that visit it. A seer approaches you from the dense jungle and proposes a way out. But he will help you only if you are able to solve his problem.

The seer is fond of prime factors, especially the count of unique prime factors of a number. He gives you two numbers, l and r and asks you to find all good pairs (x, y) ( $l \le x, y \le r$) such that the number of unique prime factors of x is equal to number of unique prime factors of y. For example, 15 and 20 make a good pair as 15 has 2 unique prime factors (3, 5) and 20 has (2, 5). For every test case, you are given the number l, r and are asked to return the number of good pairs, mod 1e9 + 7. 

Input Format:The first line contains a single integer, T, the number of test cases.

T lines follow, each line has two integers l, r.

Output Format:For every test case, output a single integer, the number of good pairs, mod 1e9 + 7.Constraints:$1 \le T \le 10^6$

$2 \le l < r \le 10^6$