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

hide comments
[Lakshman]: 2015-04-11 21:07:32

@Saurabh Jain: Yes I am.

Saurabh Jain: 2015-04-11 11:48:10

@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.

candide: 2014-04-17 17:37:07

Nice question.

[Lakshman]: 2014-04-01 13:31:44

BTW here is one 340 230 ans 1564

Last edit: 2014-04-01 13:31:59
[Lakshman]: 2014-04-01 13:19:27

@Bhavik you can easily built test cases up to n,m < 500 using brute force, I did the same to check my answers.

[Lakshman]: 2014-04-01 13:09:21

@Triveni Mahatha nice problem.


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