Arya and Bran are playing with some square and rectangular tiles of different sizes with integer edges.There are tiles of two different colors- blue and red.Blue tiles have area ranging from 1 to X and red tiles have area ranging from 1 to Y.Ai means tile with area i.
A pair of blue tiles Ai and Red tiles Aj are said to be compatible only if both i and j are not divisible by same n^2 (n > 1).
A function F(i,j) is defined only on compatible pair of blue tiles Ai and red tiles Aj as i*j*GCD(i,j)
As Arya is very intelligent in maths,she gives Bran two numbers X and Y and asks him to find the sum of F(i,j) over all possible compatible pairs of blue Ai and red Aj such that i <= X and j <= Y.
Help Bran to find the solution of the problem.
Give your answer modulo 10^9+7.

Input
The first line contains the number of test cases, t (<= 100). Each of the next t lines contains two space-separated integers X and Y (1 <= X,Y <= 1000000).

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

Input:
4
2 4
3 3
6 5
8 3

Output:
42
58
509
310