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.