#include <iostream>
#include <queue>

using namespace std;

uint64_t gcd(uint64_t a, uint64_t b) {
    uint64_t t;
    t = a % b;
    while (t)
        a = b, b = t, t = a % b;
    return b;
}

struct Pair {
    uint64_t a, b;
    int d;
};

int bfs(uint64_t const& a, uint64_t const& b) {
    queue<Pair> q;
    q.push({ a, b, 0 });
    while (true) {
        Pair& p = q.front();
        if (p.a % p.b == 0) {
            return p.d + 2;
        }
            
        uint64_t x = gcd(p.a, p.b);
        q.push({ p.a / x - 1, p.b / x, p.d + 1 });
        q.push({ p.a / x, p.b / x - 1, p.d + 1 });
        q.pop();
    }
    return 0;
}

int main() {
    int n;
    uint64_t a, b;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a >> b;
        if (b < a) {
            cout << bfs(a, b) << endl;
        } else {
            cout << bfs(b, a) << endl;
        }
    }
    return 0;
}

answer.code:6:1: error: ‘uint64_t’ does not name a type
    6 | uint64_t gcd(uint64_t a, uint64_t b) {
      | ^~~~~~~~
answer.code:3:1: note: ‘uint64_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?
    2 | #include <queue>
  +++ |+#include <cstdint>
    3 | 
answer.code:15:5: error: ‘uint64_t’ does not name a type
   15 |     uint64_t a, b;
      |     ^~~~~~~~
answer.code:15:5: note: ‘uint64_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?
answer.code:19:9: error: ‘uint64_t’ was not declared in this scope
   19 | int bfs(uint64_t const& a, uint64_t const& b) {
      |         ^~~~~~~~
answer.code:19:9: note: ‘uint64_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?
answer.code:19:28: error: ‘uint64_t’ was not declared in this scope
   19 | int bfs(uint64_t const& a, uint64_t const& b) {
      |                            ^~~~~~~~
answer.code:19:28: note: ‘uint64_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?
answer.code:19:45: error: expression list treated as compound expression in initializer [-fpermissive]
   19 | int bfs(uint64_t const& a, uint64_t const& b) {
      |                                             ^
answer.code: In function ‘int main()’:
answer.code:38:5: error: ‘uint64_t’ was not declared in this scope
   38 |     uint64_t a, b;
      |     ^~~~~~~~
answer.code:38:5: note: ‘uint64_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?
answer.code:41:16: error: ‘a’ was not declared in this scope
   41 |         cin >> a >> b;
      |                ^
answer.code:41:21: error: ‘b’ was not declared in this scope
   41 |         cin >> a >> b;
      |                     ^
answer.code:43:24: error: ‘bfs’ cannot be used as a function
   43 |             cout << bfs(a, b) << endl;
      |                     ~~~^~~~~~
answer.code:45:24: error: ‘bfs’ cannot be used as a function
   45 |             cout << bfs(b, a) << endl;
      |                     ~~~^~~~~~