Subtractions

题意翻译

给定两个数，每次用大数减去小数的差代替这个数，并称为一次操作。问有一个数为 $0$ 的时候一共有多少次操作。 输入：第一行是一个正整数 $n$，表示数据的组数。接下来 $n$ 行，每行两个正整数 $a_i$ 和 $b_i$ 表示给定的两数。 输出：输出共 $n$ 行，每行一个整数，表示答案。 数据范围：$1\le n\le1000,1 \le a_i,b_i \le10^9$

题目描述

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?

输入输出格式

输入格式

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}<=10^{9} $ ).

输出格式

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

输入输出样例

输入样例 #1

2
4 17
7 987654321

输出样例 #1

8
141093479