ARC 166

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto check = [](string X, string Y) -> bool {
        int n = X.size();
        int xa = 0, ya = 0;
        for (char c : X) {
            if (c == 'A')
                xa++;
        }
        for (char c : Y) {
            if (c == 'A')
                ya++;
        }

        if (xa > ya)
            return false;

        int rema = ya - xa;
        rep(i, n) {
            if (X[i] == 'C') {
                if (rema) {
                    X[i] = 'A';
                    rema--;
                } else {
                    X[i] = 'B';
                }
            }
        }

        set<int> xbpos;
        rep(i, n) {
            if (X[i] == 'B')
                xbpos.insert(i);
        }

        rep(i, n) {
            if (X[i] == Y[i])
                continue;
            if (X[i] == 'B' && Y[i] == 'A')
                return false;
            if (X[i] == 'A' && Y[i] == 'B') {
                auto it = xbpos.lower_bound(i);
                if (it == xbpos.end())
                    return false;
                swap(X[i], X[*it]);
                xbpos.erase(it);
            }
        }

        return true;
    };

    auto cal = [&]() -> void {
        int N;
        string X, Y;
        cin >> N >> X >> Y;

        if (X == Y) {
            yesno(true);
            return;
        }

        // sentinel
        X.push_back('C');
        Y.push_back('C');

        N++;
        int start = 0;
        rep(i, N) {
            if (Y[i] == 'C' && X[i] != 'C') {
                yesno(false);
                return;
            }

            if (X[i] == 'C' && Y[i] == 'C') {
                int len = i - start;
                if (!check(X.substr(start, len), Y.substr(start, len))) {
                    yesno(false);
                    return;
                };
                start = i + 1;

                continue;
            }
        }
        yesno(true);
    };

    int t;
    cin >> t;
    rep(i, t) {
        cal();
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, a, b, c;
    cin >> N >> a >> b >> c;

    vll X(N + 1);
    rep(i, N) cin >> X[i + 1];

    vvll rem(N + 1, vll(8));

    rep2(i, 1, N + 1) {
        rep(x, 2) rep(y, 2) rep(z, 2) {
            ll mul = 1;
            if (x)
                mul = lcm(mul, a);
            if (y)
                mul = lcm(mul, b);
            if (z)
                mul = lcm(mul, c);
            ll add = (mul - X[i] % mul) % mul;
            ll t = 1 * x + 2 * y + 4 * z;
            rem[i][t] = add;
        }
    }

    vvll dp(N + 1, vll(8, INF));
    dp[0][0] = 0;

    rep2(i, 1, N + 1) {
        rep(p, 8) rep(q, 8) {
            ll t = p | q;
            chmin(dp[i][t], dp[i - 1][p] + rem[i][q]);
        }
    }

    ll ans = INF;
    rep2(i, 1, N + 1) chmin(ans, dp[i][7]);
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, a, b, c;
    cin >> N >> a >> b >> c;

    vll X(N + 1);
    rep(i, N) cin >> X[i + 1];

    vvll rem(N + 1, vll(8));

    rep2(i, 1, N + 1) {
        rep(x, 2) rep(y, 2) rep(z, 2) {
            ll mul = 1;
            if (x)
                mul = lcm(mul, a);
            if (y)
                mul = lcm(mul, b);
            if (z)
                mul = lcm(mul, c);
            ll add = (mul - X[i] % mul) % mul;
            ll t = 1 * x + 2 * y + 4 * z;
            rem[i][t] = add;
        }
    }

    vvll dp(N + 1, vll(8, INF));
    dp[0][0] = 0;

    rep2(i, 1, N + 1) {
        rep(p, 8) rep(q, 8) {
            ll t = p | q;
            chmin(dp[i][t], dp[i - 1][p] + rem[i][q]);
        }
    }

    ll ans = INF;
    rep2(i, 1, N + 1) chmin(ans, dp[i][7]);
    cout << ans << endl;
}