← 返回题目列表

Codeforces · 267/A

A. 减法

中文机器翻译题面 查看原题

你有两个号码。只要它们都大于零,它们就会执行相同的操作:用较大的数字减去较小的数字。如果它们相等,则用一个数减去另一个数。例如,一个操作将对 (4,17) 转换为对 (4,13),将 (5,5) 转换为 (0,5)。

你有一定数量的对 (ai, bi)。他们每个人将执行多少次操作?

输入

第一行包含对数 n (1 ≤ n ≤ 1000)。然后是n行,每行包含一对正整数ai,bi(1≤ai,bi≤109)。

输出

在一行上打印每对所需的操作数。

示例

输入 #1

2
4 17
7 987654321

输出 #1

8
141093479