题目描述

小可这一天学完了辗转相减法和辗转相除法求$GCD$，小可突然想知道现在给了两个数$a$和$b$，每次做辗转相减操作，即先对比两个数字的数值大小，然后用较大的那个数减去较小的数，得出差值之后，再把原本较大的那个数替换成这个差值。就这样反复操作，一轮一轮进行下去，直到有一个数变为0。

但计算操作次数太麻烦了，小可想让你帮他计算一下。

输入格式

第一行包含一个整数$t$，表示测试数据的数量。

接下来的 $t$ 行，每行包含两个正整数 $a$ 和 $b$，表示两个数字。

输出格式

对于每组测试数据，输出一个整数，操作次数，每个结果占一行。

样例

3
1 1
2 5
3 6

1
4
2

数据范围

【评测用例规模与约定】

对于 $100\%$ 的数据，$1 \leq t \leq 10 ^ 5$，$1 \leq a,b \leq 10 ^ {9}$。