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
def lcm(x, y):
   p=x*y
   if x>y:
       x,y=y,x
   while(y):
       x, y = y, x % y
   gcd=x
   lcm = p/gcd
   return lcm

import math
def check(a,b):
    m=min(a,b)
    for n in range(2, int(math.sqrt(m)+1)):
        s=n**2
        if a%s==0 and b%s==0:
            return False
    return True




for i in range(int(raw_input())):
    A,B=map(int, raw_input().split())
    sum_=0
    for a in range(1,A+1):
        for b in range(1,B+1):
            if check(a,b):
                sum_=(sum_+lcm(a,b))%(2**30)
    print sum_