CF267A.Subtractions

You've got two numbers. As long as they are both larger than zero, they go through the same operation: subtract the lesser number from the larger one. If they equal substract one number from the another. For example, one operation transforms pair (4,17) to pair (4,13), it transforms (5,5) to (0,5).

You've got some number of pairs (a__i, b__i). How many operations will be performed for each of them?

你有两个数。只要它们都大于零，就对它们执行相同的操作：用较大的数减去较小的数。如果两数相等，则用其中一个数减去另一个数。例如，一次操作将数对 $(4,17)$ 变为 $(4,13)$，将 $(5,5)$ 变为 $(0,5)$。

你有若干个数对 $(a_i,\,b_i)$。对每个数对，总共会执行多少次操作？

The first line contains the number of pairs n (1  ≤  n  ≤  1000). Then follow n lines, each line contains a pair of positive integers a__i, b__i (1  ≤  a__i,  b__i  ≤  109).

第一行包含数对的数量 $n$（$1 \le n \le 1000$）。接下来有 $n$ 行，每行包含一对正整数 $a_i,\,b_i$（$1 \le a_i,\,b_i \le 10^9$）。

Print the sought number of operations for each pair on a single line.

对每一对，输出所求的操作次数，每行一个。