Tiles of Tetris, NOT!

Time limit1sMemory limit128 MB

Summary

Given a tile of width W and height H in fixed orientation, find the smallest square it can tile and count the tiles needed.

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

Problem

You bought a large batch of identical rectangular tiles. Each tile is $W$ units wide and $H$ units tall, and every tile must be laid down in the same orientation — tiles may not be rotated. By placing several tiles side by side with no gaps you can cover a square region, but only when the square's side length is a multiple of both $W$ and $H$ .

Find the minimum number of tiles needed to fill the smallest possible square.

Input

The input contains one or more test cases. Each test case is a single line with two positive integers $W$ and $H$ ( $0 < W, H < 10^6$ ), the width and height of each tile. The input ends with a line containing two $0$ s, which is not processed.

Output

For each test case, print on its own line the minimum number of tiles required to fill the smallest possible square.

Examples3

Example 1
Input
```
2 3
1 2
0 0
```
Expected output
```
6
2
```
Example 2
Input
```
5 5
0 0
```
Expected output
```
1
```
Example 3
Input
```
6 4
0 0
```
Expected output
```
6
```