题目描述

给出两个正整数 $a, b$ , 保证 $1 \leq a \leq b$。你可以执行以下操作若干次：

选择将 $a$ 修改为 $a - gcd(a,b)$ 或者将 $b$ 修改为 $b - gcd(a,b)$ 。

其中 $gcd$ 代表最大公约数。特别的， $gcd(x, 0) = gcd(0, x) = x$,

请问需要执行多少次操作才能将 $a, b$ 修改为 $0$ 。

输入格式

第一行一个正整数 $T$ ， 代表数据组数。 接下来 $T$ 行，每行两个正整数 ， 表示$a, b$。

输出格式

对于每组数据，输出一行，表示答案。

样例

3
3 4
12 20
114 514

3
4
6

样例1解释： 对于第一组数据，(3,4)->(2,4)->(0,4)->(0,0)

5
345 78781231243213
321 1231231231231
12 12312312322222
4799 9729719
4859 1552318

5
6
4
16
16

数据范围

对于30%的数据，$1\leq{a,b}\leq{10}$ 对于60%的数据，$1\leq{a,b}\leq{500}$ 对于100%的数据，$1\leq{a}\leq{5000},1\leq{b}\leq{10^{18}},a\leq{b}，1\leq{T}\leq{5}$