Given A and B, compute the sum of lcm(a, b) over all pairs of positive integers a and b such that:

(1) a<=A and b<=B.
(2) There is no integer n>1 such that n² divides both a and b.

Give your answer modulo 2³⁰.

Input

The first line contains the number of test cases, t (about 200). Each of the next t lines contains two space-separated integers A and B (1<=A, B<=4000000).

Output

Print the answer to each test case on a separate line.

A number X is called Permut number if X and 2X ( both without leading zeroes ) have same number of digits and are permutations of each other. Given A and B, find the number of Permut numbers >= A and <= B.

Note : X is called permutation of Y if every digit ( 0 - 9 ) occurs same number of times in both the numbers ( maybe at different positions ).

Input :

The first line contains the number of test cases T. T lines follow, containing two integers A and B.

Output :