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

long long A[200000], iA[200000], M;
map<long long, long long> m, s;

long long pw(long long i, long long p) {
    if (!p) return 1;
    if (p == 1) return i;
    return pw(i * i % M, p / 2) * (p % 2 ? i : 1) % M;
}

int main() {
    //freopen("in.txt", "r", stdin);
    long long T;
    scanf("%lld", &T);
    while (T--) {
        long long N, w = 0, i, j;
        scanf("%lld %lld", &N, &M);
        for (i = 0; i < N; ++i) scanf("%lld", &A[i]), iA[i] = pw(A[i], M - 2);
        for (i = 1; i <= 4; ++i) for (j = 0; j + i < N; ++j) ++m[A[j + i] * iA[j] % M];
        for (auto it = m.begin(); it != m.end(); ++it) if (it->second >= N / 4) {
            long long z = it->first, zi = pw(z, M - 2);
            for (i = 0; i < N; ++i) {
                auto rt = s.find(A[i] * zi % M);
                long long t = (rt != s.end() ? rt->second : 0);
                s[A[i]] = max(s[A[i]], t + 1);
                w = max(w, t + 1);
            }
            s.clear();
            if (w >= (N + 1) / 2) break;
        }
        m.clear();
        printf("%lld\n", w >= (N + 1) / 2 ? w : -1);
    }
    return 0;
}