100429 - 两数相减
两个正整数a,b，若相等则直接相减，若不相等则用较大的减去较小的；相减得到的差值代替被减数。求经过多少次之后，其中一个变为0。
Input
第一行，一个整数n表示询问个数。
接下来n行，每行两正整数a_i，b_i。
对于100%的数据：
1\le n \le 1000；
1\le a_i，b_i \le 10^9。
Output
按输入顺序依次输出所需次数，每行一个。
Examples
Input
2 4 17 7 987654321
Output
8 141093479