#include <iostream>
#include <queue>
#include <random>

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 < 1000; ++i) {
        if (b < a) {
            cout << bfs(a, b) << endl;
        } else {
            cout << bfs(b, a) << endl;
        }
    }
    return 0;
}