Code: A Simple GCD Problem (Hard Version)

#include <bits/stdc++.h>

#define int long long
std::vector<int> minp, primes;

void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();

    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }

        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

struct st {
    int k, c;
};

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1), b(n + 1), g(n), l(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        std::cin >> b[i];
    }

    for (int i = 1; i < n; ++i) {
        g[i] = std::gcd(a[i], a[i + 1]);
    }

    if (n > 1) {
        l[1] = g[1];
        l[n] = g[n - 1];
        for (int i = 2; i < n; ++i) {
            l[i] = (g[i - 1] / std::gcd(g[i - 1], g[i])) * g[i];
        }
    }

    std::vector<int> u(n + 1, 1), v(n + 2, 1);
    for (int i = 1; i < n; ++i) {
        u[i] = l[i] / g[i];
    }
    for (int i = 2; i <= n; ++i) {
        v[i] = l[i] / g[i - 1];
    }

    std::vector<std::vector<st>> st(n + 1);

    for (int i = 1; i <= n; ++i) {
        int t = a[i] / l[i];

        if (a[i] != l[i]) {
            if (l[i] <= b[i]) {
                st[i].push_back({1, 1});
            }
            st[i].push_back({t, 0});
        } else {
            st[i].push_back({1, 0});

            int lim = b[i] / l[i], cnt = 0;
            for (auto pi : primes) {
                if (pi > lim) {
                    break;
                }
                if ((i > 1 && u[i - 1] % pi == 0) ||
                    (i < n && v[i + 1] % pi == 0)) {
                    continue;
                }
                st[i].push_back({pi, 1});
                cnt++;
                if (cnt == 25) {
                    break;
                }
            }
        }
    }

    std::vector<std::vector<int>> dp(n + 1);
    for (int i = 1; i <= n; ++i) {
        dp[i].assign(st[i].size(), -1);
    }

    for (int c = 0; c < (int)st[1].size(); ++c) {
        dp[1][c] = st[1][c].c;
    }

    for (int i = 2; i <= n; ++i) {
        for (int c = 0; c < (int)st[i].size(); ++c) {
            int k = st[i][c].k;
            int mx = -1;

            for (int p = 0; p < (int)st[i - 1].size(); ++p) {
                if (dp[i - 1][p] == -1) {
                    continue;
                }
                int pre = st[i - 1][p].k;

                if (k == 1 || pre == 1 || std::gcd(k, pre) == 1) {
                    if (dp[i - 1][p] > mx) {
                        mx = dp[i - 1][p];
                    }
                }
            }

            if (mx != -1) {
                dp[i][c] = mx + st[i][c].c;
            }
        }
    }

    int ans = 0;
    for (int c = 0; c < (int)st[n].size(); ++c) {
        if (dp[n][c] > ans) {
            ans = dp[n][c];
        }
    }

    std::cout << ans << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

    sieve(1e5 + 5);

    int _ = 1;
    std::cin >> _;

    while (_--) {
        solve();
    }

    return 0;
}