## Starks and Tiles

Time Limit: 2 sec
Memory Limit: 256 MB
Attempts: 0
Accuracy: 0.00%
Author: Akashdeep Goel

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

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED