WPC5I - LCM

Given n, and m, find the smallest k such that:

n divides lcm(m, k); m divides lcm(n, k)

Even if there are no Galactic Wars, you are still a Martian. Just do it.

Input

First line contains a single integer T, denoting the number of Test Cases.

T lines containing space separated integers: m and n.

Output

Output T lines each containing the smallest k that satisfies the problem.

Constraints

1 <= T <= 2000

1 <= m, n < 2^31

Example

Input:
1
3 4

Output:
12

Added by:triveni
Date:2014-03-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACA judge IITK, WPC5

hide comments
2015-04-11 21:07:32 [Lakshman]
@Saurabh Jain: Yes I am.
2015-04-11 11:48:10 Saurabh Jain
@Lakshman are you sure that he answer is 1564 for the testcase you provided, I find 782 to work as well and my prog actually gives that output.
2014-04-17 17:37:07 candide
Nice question.
2014-04-01 13:31:44 [Lakshman]
BTW here is one 340 230 ans 1564

Last edit: 2014-04-01 13:31:59
2014-04-01 13:19:27 [Lakshman]
@Bhavik you can easily built test cases up to n,m < 500 using brute force, I did the same to check my answers.
2014-04-01 13:09:21 [Lakshman]
@Triveni Mahatha nice problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.