#include <bits/stdc++.h>
using namespace std;
 
const int M = 400005;
int spf[M]; 
 
 
void sieveSPF() {
    for (int i = 0; i < M; i++) spf[i] = i;
 
    for (int i = 2; i * i < M; i++) {
        if (spf[i] == i) { // i is prime
            for (int j = i * i; j < M; j += i) {
                if (spf[j] == j)
                    spf[j] = i;
            }
        }
    }
}
 
set<int> gpf(int x) {
    set<int> f;
    while (x > 1) {
        f.insert(spf[x]);
        x /= spf[x];
    }
    return f;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    sieveSPF();
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
 
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
 
        string temp;
        getline(cin, temp); 
 
        unordered_map<int, vector<int>> d;
 
        for (int x : a) {
 
            for (int p : gpf(x)) {
                d[p].push_back(0);
            }
 
            for (int p : gpf(x + 1)) {
                d[p].push_back(1);
            }
        }
 
        int ans = n;
        for (auto &entry : d) {
            auto &c = entry.second;
            if (c.size() >= 2) {
                sort(c.begin(), c.end());
                int cost = c[0] + c[1];
                ans = min(ans, cost);
            }
        }
 
        cout << ans << "\n";
    }
 
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTSA9IDQwMDAwNTsKaW50IHNwZltNXTsgCgoKdm9pZCBzaWV2ZVNQRigpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTTsgaSsrKSBzcGZbaV0gPSBpOwoKICAgIGZvciAoaW50IGkgPSAyOyBpICogaSA8IE07IGkrKykgewogICAgICAgIGlmIChzcGZbaV0gPT0gaSkgeyAvLyBpIGlzIHByaW1lCiAgICAgICAgICAgIGZvciAoaW50IGogPSBpICogaTsgaiA8IE07IGogKz0gaSkgewogICAgICAgICAgICAgICAgaWYgKHNwZltqXSA9PSBqKQogICAgICAgICAgICAgICAgICAgIHNwZltqXSA9IGk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KCnNldDxpbnQ+IGdwZihpbnQgeCkgewogICAgc2V0PGludD4gZjsKICAgIHdoaWxlICh4ID4gMSkgewogICAgICAgIGYuaW5zZXJ0KHNwZlt4XSk7CiAgICAgICAgeCAvPSBzcGZbeF07CiAgICB9CiAgICByZXR1cm4gZjsKfQoKaW50IG1haW4oKSB7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKG51bGxwdHIpOwoKICAgIHNpZXZlU1BGKCk7CgogICAgaW50IHQ7CiAgICBjaW4gPj4gdDsKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBpbnQgbjsKICAgICAgICBjaW4gPj4gbjsKCiAgICAgICAgdmVjdG9yPGludD4gYShuKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgY2luID4+IGFbaV07CgogICAgICAgIHN0cmluZyB0ZW1wOwogICAgICAgIGdldGxpbmUoY2luLCB0ZW1wKTsgCgogICAgICAgIHVub3JkZXJlZF9tYXA8aW50LCB2ZWN0b3I8aW50Pj4gZDsKCiAgICAgICAgZm9yIChpbnQgeCA6IGEpIHsKICAgICAgICAgICAgCiAgICAgICAgICAgIGZvciAoaW50IHAgOiBncGYoeCkpIHsKICAgICAgICAgICAgICAgIGRbcF0ucHVzaF9iYWNrKDApOwogICAgICAgICAgICB9CiAgICAgICAgICAgIAogICAgICAgICAgICBmb3IgKGludCBwIDogZ3BmKHggKyAxKSkgewogICAgICAgICAgICAgICAgZFtwXS5wdXNoX2JhY2soMSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGludCBhbnMgPSBuOwogICAgICAgIGZvciAoYXV0byAmZW50cnkgOiBkKSB7CiAgICAgICAgICAgIGF1dG8gJmMgPSBlbnRyeS5zZWNvbmQ7CiAgICAgICAgICAgIGlmIChjLnNpemUoKSA+PSAyKSB7CiAgICAgICAgICAgICAgICBzb3J0KGMuYmVnaW4oKSwgYy5lbmQoKSk7CiAgICAgICAgICAgICAgICBpbnQgY29zdCA9IGNbMF0gKyBjWzFdOwogICAgICAgICAgICAgICAgYW5zID0gbWluKGFucywgY29zdCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGNvdXQgPDwgYW5zIDw8ICJcbiI7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K

NgoyCjEgMQoxIDEKMgo0IDgKMSAxCjUKMSAxIDcyNyAxIDEKMSAxIDEgMSAxCjIKMyAxMQoxIDEKMwoyIDcgMTEKMSAxIDEKMwo3IDEyIDEzCjEgMSAxCg==

6
2
1 1
1 1
2
4 8
1 1
5
1 1 727 1 1
1 1 1 1 1
2
3 11
1 1
3
2 7 11
1 1 1
3
7 12 13
1 1 1