calculate-lcm

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

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
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(input())):
	 A,B=list(map(int, 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_)