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