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