#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;
}