Arnie's Dog Biscuits

Our discerning gourmet puppy Arnie is turning to you for a program to help him split his dog biscuits. Each biscuit is shaped like a rectangle and perforated into equal sized squares:

Unfortunately, Arnie will only eat square-shaped biscuits; therefore, he must break the biscuit into squares. Each break, termed a split, is applied to one rectangle, runs along one straight perforated line, and separates the rectangle into two pieces:

Input

The first line of the input contains one positive integer n, the number of biscuits to split. Each of the next n lines contains two positive integers r and c, the number of rows and columns of one biscuit, separated by white space.

Output

The output contains one line for each biscuit specifying the minimal number of splits required to break the biscuit into squares.

Sample Input

2
6 7
5 5
This defines two biscuits: the one shown above which requires four splits, and a square biscuit which requires no splits.

Sample Output

4
0

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!