Least Common Multiple

Interview

Time limit1sMemory limit128 MB

Summary

For each of up to 1000 pairs of numbers, compute and print the least common multiple.

Level: Easy2 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

For two natural numbers A and B, a common multiple is a natural number that is a multiple of both A and B. The least common multiple is the smallest such number.

Given several pairs of natural numbers A and B, write a program that computes the least common multiple for each pair.

Input

The first line contains the number of test cases T (1 ≤ T ≤ 1,000). Each of the next T lines contains two natural numbers A and B (1 ≤ A, B ≤ 45,000).

Output

For each test case, print the least common multiple of A and B on its own line, in the same order as the input.

Examples1

Example 1
Input
```
3
1 45000
6 10
13 17
```
Expected output
```
45000
30
221
```