Grand Prix of Xi'an | H. King

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author marX
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

using namespace std;

int check(vector<int> &a, int q, int p) {
    unordered_map<int, int> tot;
    int ans = 0, n = (int) a.size();

    for (int i = n - 1; i >= 0; --i) {
        int u = 1LL * a[i] * q % p;

        int c = 0;

        if (tot.find(u) != tot.end()) {
            c = tot[u];
        }
        tot[a[i]] = c + 1;
        ans = max(ans, c + 1);
    }

    if (ans * 2 >= n) {
        return ans;
    } else {
        return -1;
    }
}

/// Modular exponentiation for integers
long long mod_pow(long long val, long long n, long long mod) {
    long long tar = 1;

    while (n) {
        if (n & 1) {
            tar = tar * val % mod;
        }
        n >>= 1;
        val = val * val % mod;
    }

    return tar;
}

const int MAGIC = 22;

class H {
public:
    void solve(std::istream &in, std::ostream &out) {
        int t;
        in >> t;

        while (t--) {
            int n, p;
            in >> n >> p;

            vector<int> a(n), b(n);

            for (int i = 0; i < n; ++i) {
                in >> a[i];
                b[i] = mod_pow(a[i], p - 2, p);
            }

            int answer = -1;

            if (a.size() > 2) {
                answer = max(answer, check(a, 1LL * a[2] * b[0] % p, p));
            }

            if (a.size() > 3) {
                answer = max(answer, check(a, 1LL * a[3] * b[1] % p, p));
            }

            map<int, int> freq;

            for (int i = 0; i + 1 < n; ++i) {
                freq[1LL * b[i] * a[i + 1] % p]++;
            }

            for (int i = 0; i + 2 < n; ++i) {
                freq[1LL * b[i] * a[i + 2] % p]++;
            }

            vector<pair<int, int>> rev_freq;

            for (auto p : freq) {
                rev_freq.push_back({p.second, p.first});
            }

            sort(rev_freq.begin(), rev_freq.end());
            reverse(rev_freq.begin(), rev_freq.end());

            for (int i = 0; i < min(MAGIC, (int) rev_freq.size()); ++i) {
                answer = max(answer, check(a, rev_freq[i].second, p));
            }

            out << answer << '\n';
        }
    }
};


int main() {
    H solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);
    return 0;
}