多组相遇时间

题目描述

给定 T 组正整数。对每组 a、b，求两个周期从时刻 0 同时发生后，下一次同时发生的正时刻，即 lcm(a,b)。各组数据相互独立。

输入格式

第一行输入整数 T，满足 1≤T≤100。接下来 T 行，每行输入两个整数 a、b，满足 1≤a,b≤10^9。每组的最小公倍数不超过 10^18。

输出格式

按输入顺序输出 T 行，每行输出对应 a、b 的最小公倍数。

样例

输入

3
6 8
12 18
5 7

输出

24
36
35