Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Kitchen Decorate

By sohel_sec · Limits 1s, 512 MB

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

InputOutput
2
18 27
12 6
9
6

Discussion

Statistics


85% Solution Ratio

edge555Earliest, Mar '20

ishtupeedFastest, 0.0s

edge555Lightest, 262 kB

bokaifShortest, 91B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.