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 <= 10^9
 
Time Limit: 1 second
 
Example:
Input:
1
3 4
 
Output:
12

 

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

 

Time Limit: 1 second

 

Example:

Input:

1

3 4

 

Output:

12

 


hide comments
Devil D: 2016-09-25 17:18:04

@Lakshman
i am not sure why 340, 230 should give 1564 and not 782.

square1001: 2016-08-07 02:54:04

Interesting!
You can't calculate only lcm(m, n).
Because if m=10 and n=6, the answer is 15.

Dewang Sultania: 2016-05-18 17:01:41

Nice problem my 100th :)

poojan : 2016-05-08 19:12:22

0.0 AC felling happy!

Bhuvnesh Jain: 2015-07-01 19:50:12

brute force works

Akshat Mathur: 2015-06-01 08:47:38

Good Problem...............AC in one go :)

lucky: 2015-05-15 21:45:15

@Lakshman why is 782 wrong?

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


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