[백준]S5-1934

TODO : 유클리드호제법으로 다시 풀기

# PyPy3로 제출해야 시간초과가 나지 않습니다.
from collections import deque
test = int(input())

for _ in range(test):
    a, b = map(int, input().split())
    n = 1
    ans = deque()
    while n <= min(a,b):
        if a % n ==0 and b % n ==0:
            ans.append(n)
            n += 1
        else:
            n += 1
    M = max(ans)
    print(int(M*(a/M)*(b/M)))