CF2154C1 WA

// Problem: C1. No Cost Too Great (Easy Version)
// Contest: Codeforces - Codeforces Round 1060 (Div. 2)
// URL: https://codeforces.com/contest/2154/problem/C1
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

namespace rngs = std::ranges;
using ll = long long;
using a2l = array<ll, 2>;
using vl = vector<ll>;

void solve2()
{
    ll n;
    cin >> n;
    vl a(n), b(n);
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;
}

vl ps;

void solve()
{
    ll n, ecnt = 0;
    cin >> n;
    vl a(n), b(n);
    map<ll, ll> pcnt, p1cnt;
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;

    for (auto x : a) {
        for (auto f : ps) {
            if (f * f > x) {
                if (std::binary_search(ps.begin(), ps.end(), x))
                    pcnt[x] += 1;
                if (std::binary_search(ps.begin(), ps.end(), x + 1))
                    p1cnt[x + 1] += 1;
                break;
            }

            if (x % f == 0)
                pcnt[f] += 1;
            if ((x + 1) % f == 0)
                p1cnt[f] += 1;
        }
    }

    ll val = 2;
    for (auto [k, v] : pcnt) {
        if (v >= 2)
            dbg(k, v, val), val = 0;
        if (v == 1 && p1cnt.count(k))
            val = min(val, 1ll);
        if (p1cnt.count(k) && p1cnt[k] >= 2)
            val = min(val, 2ll);
        // val = min(val, 2 - min(v, 2ll));
    }

    cout << val << '\n';
}

int main(int argc, char **argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    for (ll i = 2; i < 2e5 + 3; ++i) {
        bool is_prime = true;
        for (ll j = 2; j * j <= i && is_prime; ++j)
            if (i % j == 0)
                is_prime = false;
        if (is_prime)
            ps.push_back(i);
    }

    ll t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
};