#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
vector<int> sieve_primes(int limit) {
    vector<char> is_prime(limit + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= limit; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            if ((ll)i * i <= limit) {
                for (int j = i * i; j <= limit; j += i) is_prime[j] = false;
            }
        }
    }
    return primes;
}
 
vector<ll> factor_unique(ll x, const vector<int>& primes) {
    vector<ll> res;
    for (int p : primes) {
        if ((ll)p * p > x) break;
        if (x % p == 0) {
            res.push_back(p);
            while (x % p == 0) x /= p;
        }
    }
    if (x > 1) res.push_back(x);
    return res;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
 
    int sieve_limit = 200000;
    auto primes = sieve_primes(sieve_limit);
 
    while (T--) {
        int n;
        cin >> n;
        vector<ll> a(n);
        vector<ll> b(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) cin >> b[i];
 
        unordered_map<ll, vector<int>> orig_idx;
        unordered_map<ll, vector<int>> plus_idx;
 
        for (int i = 0; i < n; ++i) {
            auto facs = factor_unique(a[i], primes);
            for (ll p : facs) orig_idx[p].push_back(i);
 
            auto facs_plus = factor_unique(a[i] + 1, primes);
            for (ll p : facs_plus) plus_idx[p].push_back(i);
        }
 
        bool zero = false;
        for (auto &kv : orig_idx) {
            if (kv.second.size() >= 2) { zero = true; break; }
        }
        if (zero) {
            cout << 0 << '\n';
            continue;
        }
 
        bool one = false;
        for (auto &kv : plus_idx) {
            ll p = kv.first;
            const auto &plusvec = kv.second;
 
            if (!orig_idx.count(p)) continue;
            const auto &origvec = orig_idx[p];
 
            if (origvec.empty()) continue;
            int idx0 = origvec[0];
            for (int j : plusvec) {
                if (j != idx0) { one = true; break; }
            }
            if (one) break;
        }
        if (one) {
            cout << 1 << '\n';
            continue;
        }
 
        
        cout << 2 << '\n';
    }
    return 0;
}