#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<int> A(N);
        for (int i = 0; i < N; i++) cin >> A[i];
        
        // Count frequencies
        map<int,int> freq;
        for (int x : A) freq[x]++;
        vector<int> vals;
        vals.reserve(freq.size());
        for (auto &p : freq) vals.push_back(p.first);
        int V = vals.size();
        
        // Precompute divisors of N
        vector<int> divisors;
        for (int d = 1; d * d <= N; ++d) {
            if (N % d == 0) {
                divisors.push_back(d);
                if (d != N/d) divisors.push_back(N/d);
            }
        }
        sort(divisors.begin(), divisors.end());
        
        int answer = 1; // at least 1 block always possible
        // Try smallest block size m to maximize blocks k = N/m
        for (int m : divisors) {
            if (m < 2) continue;
            int k = N / m;
            bool ok = false;
            
            // Gather possible D values
            unordered_set<int> Dset;
            // include D=0 specially
            Dset.insert(0);
            for (int i = 0; i < V; i++) {
                for (int j = i+1; j < V; j++) {
                    Dset.insert(abs(vals[j] - vals[i]));
                }
            }
            
            // Check each D
            for (int D : Dset) {
                int pairs = 0;
                if (D == 0) {
                    // count pairs from identical values
                    for (auto &p : freq) pairs += p.second / 2;
                } else {
                    for (int x : vals) {
                        auto it = freq.find(x + D);
                        if (it != freq.end()) {
                            pairs += min(freq[x], it->second);
                        }
                    }
                }
                if (pairs >= k) {
                    ok = true;
                    break;
                }
            }
            if (ok) {
                answer = k;
                break;
            }
        }
        
        cout << answer;
        if (T) cout << '\n';
    }
    return 0;
}