你有两个号码。只要它们都大于零,它们就会执行相同的操作:用较大的数字减去较小的数字。如果它们相等,则用一个数减去另一个数。例如,一个操作将对 (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