题目描述

你有两个数。只要它们都大于零，你就对它们执行相同的操作：将较小的数从较大的数中减去。如果它们相等，就减去其中一个数。比如，一次操作可以把数对 $(4,17)$ 变成数对 $(4,13)$，也可以把 $(5,5)$ 变成 $(0,5)$。

你有若干组数对 $(a_i,b_i)$。对于每组数对，问要执行多少次操作？

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示数对的组数。接下来有 $n$ 行，每行包含一组正整数 $a_i, b_i$（$1 \leq a_i, b_i \leq 10^{9}$）。

输出格式

对于每一组数对，在一行内输出所需的操作次数。

说明/提示

由 ChatGPT 5 翻译

样例

2
4 17
7 987654321

8
141093479