B. Fair and Square
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob want to play a game on a rectangular grid. They consider the game fair if the grid on which the game is played is a square (i.e., has equal side lengths).

However, they currently have an $$$n \times m$$$ grid (where $$$n$$$ is not necessarily equal to $$$m$$$). They decided to take multiple copies of this $$$n \times m$$$ grid. These copies must maintain their original $$$n \times m$$$ orientation (no rotation allowed) and must be attached together side-by-side, without intersections, to form a perfect square grid.

They are asking you to determine the minimum number of $$$n \times m$$$ grid copies required to achieve this. Can you help them?

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$), representing the number of test cases.

Then $$$T$$$ test cases follow.

Each test case consists of a single line containing two integers, $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^9$$$), representing the dimensions (height and width) of the initial grid.

Output

For each test case, print a single integer representing the minimum number of $$$n \times m$$$ grid copies required to form a square grid.

Example
Input
2
2 3
1 1
Output
6
1