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
dengjiaqiang: 2023-08-05 14:58:12

@light_az help me

dengjiaqiang: 2023-08-05 14:57:09

<snip>
In fact,the answer is only the lcm(n,m)/(n,m的公共只因数 look this link->
https://www.luogu.com.cn/discuss/651408,you may know what is 只因数)
[Simes]: don't post source code here.

Last edit: 2023-08-05 19:56:10
itachi_2016: 2018-01-04 21:44:17

INPUT:
2
30 18
340 230

OUTPUT:
45
1564

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?


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