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^2 divides both a and b.

Give your answer modulo 2^30.

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.

SAMPLE INPUT
4
2 4
3 3
6 5
8 3

SAMPLE OUTPUT
24
28
233
178

见题面

见题面