该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 9B.连分数拆解

时间限制：2000ms

空间限制：256MB

题目描述

“人的眼睛，听不到东西；人的耳朵，看不到东西。”
威廉·佩坦西整天神经兮兮的，只对他认为美的东西感兴趣，数字也是一样。
他认为，连分数是最美丽的数字，他希望把所有真分数都写成有限的分子为1的连分数的形式（其中\(a_i\)为正整数）：

\(\frac{n}{m}=\frac{1}{a_1+\frac{1}{...}}\)

不过他不是很擅长数学运算，对于一个给定的分数\(\frac{n}{m}\)，希望你帮忙告诉他，将它化为连分数后，\(\sum^{n}_{i=1} a_i\)的值

输入格式

输入的第一行包含一个正整数 \(T\)，表示有\(T\)组询问。
之后\(T\)行，每行包含两个正整数\(n,m\)。

输出格式

输出共\(T\)行，对于每一个给定的分数，求出将它化为连分数后，\(\sum^{n}_{i=1} a_i\)的值。

样例输入

1
7 10

样例输出

6

样例解释

\(\frac{7}{10}=\frac{1}{1+\frac{1}{2+\frac{1}{3}}}\)

\(a_1=1,a_2=2,a_3=3\)

数据范围及约定

对于60%的数据，保证 \(1 \le T \le 100\)，\(1 \le n,m \le 10^5\)。
对于所有的数据，保证 \(1 \le n \le {10}^5\)，\(1 \le n,m \le 10^9\), \(n \le m\)。