题面

题目背景

$Jerry$教授又在给小老鼠讲课了。这回$Jerry$讲到了电学中电容的串并联，并给小老鼠留了搭电容的课后练习。但是$Jerry$还要继续备课，所以就请你帮忙给出标准答案了。

题目描述

电容，符号是$C$，单位是法拉($F$)，然而这个单位太大了，$Jerry$会用皮法($pF$)来表述一个电容，$1pF = 10^{-12} F$。$Jerry$告诉你：两个容量为$C_1$和$C_2$的电容并联，会形成一个新的容量为$C_1 + C_2$的电容；两个容量为$C_1$和$C_2$的电容串联，会形成一个新的容量为$\frac{1}{\frac{1}{C_1} + \frac{1}{C_2}}$的电容。受困于技术原因，$Jerry$只能在原来的基础上每次并上一个$1pF$电容或者串上一个$1pF$电容，而不能搭了两个后再串一起或并一起。$Jerry$的练习题要求用若干容量为$1pF$的电容搭成一个容量为$\frac{a}{b} pF$的电容。$Jerry$手头的$1pF$电容不多了，他要求你用尽可能少的$1pF$电容来完成任务并告诉他最少要用多少个。

输入格式

第一行一个正整数$T$，表示题目数量。
之后$T$行每行两个正整数$a$和$b$，表示这道题要求搭的电容容量为$\frac{a}{b} pF$。

输出格式

共$T$行，每行一个整数，表示完成该题所用的最少$1pF$电容个数。

样例

输入样例1

2
1 1
3 2

输出样例1

1
3

输入样例2

2
6 5
199 200

输出样例2

6
200

数据规模与约定

对于20%的数据，$1 \le a \le 10$，$1 \le b \le 10$。
对于另外20%的数据，$a = 1$。
对于另外20%的数据，$b = 1$。
对于100%的数据，$1\le a \le 10^{18}$，$1 \le b \le 10^{18}$，$1 \le T \le 5000$。

题意分析

首先因为只能串联或者并联上一个$1 pF$的电容，所以$C_2 = 1 pF$。公式就可以化成这样：
并联 : $C = C_1 + 1$
串联 : $C = \frac{1}{\frac{1}{C_1} + 1} = \frac{1}{\frac{C_1 + 1}{C_1}} = \frac{C_1}{C_1 + 1}$
然后DFS逆推，搜索每次应该串上一个还是并上一个。
记得先约分哦！

AC代码

#include <bits/stdc++.h>
using namespace std;
inline int rd() {
    register int ans = 0, flag = 1;
    register char c = getchar();
    for (; c > '9' || c < '0'; c = getchar()) if (c == '-') flag = -1;
    for (; c >= '0' && c <= '9'; c = getchar()) ans = ans * 10 - '0' + c;
    return ans * flag;
}
inline long long rdll() {
    register long long ans = 0, flag = 1;
    register char c = getchar();
    for (; c > '9' || c < '0'; c = getchar()) if (c == '-') flag = -1;
    for (; c >= '0' && c <= '9'; c = getchar()) ans = ans * 10 - '0' + c;
    return ans * flag;
}
long long gcd(long long a, long long b) {
    if (a < b) swap(a, b);
    return b ? gcd(b, a % b) : a;
}
long long ans = 0;
void dfs(long long a, long long b) {
    if (a >= b) {
        ans += a / b;
        a %= b;
    }
    if (a != 0 && b != 0 && a % b != 0) {
        ans += b / a;
        b %= a;
    }
    if (a != 0 && b != 0) {
        dfs(a, b);
    }
}
long long solve(long long a, long long b) {
    ans = 0;
    long long gcdd = gcd(a, b);
    a /= gcdd;
    b /= gcdd;
    if (b == 1ll) return a;
    if (a == 1ll) return b;
    dfs(a, b);
    return ans;
}
int main() {
    int t = rd();
    for (register int i = 1; i <= t; ++i) {
        printf("%lld\n", solve(rdll(), rdll()));
    }
    return 0;
}