Shira has now decided to decorate her kitchen of height H and width W more precisely, she wants to tile the floor.
After experimenting with different tile materials of Shira and her friend Linnea.
Linnea advised that it would be more eye-catching if the height and width of the tiles are as wide as possible. In other words the dimension of the tiles must be a square with maximum area that perfectly fit her kitchen without any scraps. Note that the dimension must be integers.
But Shira doesn’t know what the height of the square-tile will be. Can you help her ?
Input
Input starts with an integer T (1 ≤ T ≤ 105) denoting the number of test cases.
Each case contains two space separated integers W, H (1 ≤ W, H ≤ 1018) the width and height of the kitchen .
Output
For each test case print a single integer the maximum height of the tiles.
Sample
| Input | Output |
|---|---|
2 18 27 12 6 | 9 6 |
