#include <vector>
#include <map>

using namespace std;
using ull = unsigned long long;
using u128 = __uint128_t;

inline int m(int x) {return x%9; }
u128 gcd(u128 x, u128 y) {return x ? gcd(y % x, x) : y; }
u128 lcm(u128 x, u128 y) {return x / gcd(x, y) * y; }

ull qpow(ull x, int n) {
    ull r = 1;
    while (n) {if (n & 1) r = r * x; x = x * x; n >>= 1; }
    return r;
}

ull calc_cycle(vector<int>&v, vector<int>&k) {
    int L = v.size();
    ull val = 0, mask = (((ull)1) << (L << 2)) - 1;
    for (auto i : v) val = (val << 4) | i;
    map<ull, ull> mp;
    ull pos = 0;
    mp[val] = 0;
    while (1) {
        pos++;
        int a = 0;
        for (int i = 0; i < L; i++) a = m(a + v[i] * k[i]);
        for (int i = 1; i < L; i++) v[i-1] = v[i];
        v[L - 1] = a;
        val = ((val << 4) & mask) | a;
        if (mp.find(val) != mp.end()) return pos - mp[val];
        mp[val] = pos;
    }
}

u128 a(int n) {
    if (n == 0) return 1;
    vector<int> k(n);
    u128 res = 1;
    for (ull T = 0; T < qpow(9, n) ; T++) {
        ull t = T;
        for (int i = 0; i < n; i++) {
            k[i] = (t % 9) + 1;
            t /= 9;
        }
        vector<int> v(n, 0);
        v[n-1] = 1;
        res = lcm(res, calc_cycle(v, k));
    }
    return res;
}