#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <iostream>
using namespace std;

const int MAXN = 3000;
const int SQRT_MAXN = 54;
int MOD = 1000000007;

vector<int> primes;
int f[MAXN + 1], prime2index[MAXN + 1], dp[2][1 << 16];

int main()
{
    // f[i] is the maximum prime factor of i.
    memset(f, -1, sizeof(f));
    memset(prime2index, -1, sizeof(prime2index));
    f[1] = 1;
    for (int i = 2; i <= MAXN; ++ i) {
        if (f[i] == -1) {
            for (int j = i; j <= MAXN; j += i) {
                f[j] = i;
            }
            prime2index[i] = primes.size();
            primes.push_back(i);
        }
    }

    int tests, test = 1;
    for (scanf("%d", &tests); test <= tests; ++ test) {
        int n;
        scanf("%d%d", &n, &MOD);
        int sqrt_n = (int)sqrt(n) + 1;
        int smallPrimes = 0; // the number of primes smaller than or equal to sqrt(n)
        for (int i = 2; i <= sqrt_n; ++ i) {
            if (f[i] == i) {
                ++ smallPrimes;
            }
        }
        vector<int> odd(smallPrimes, 0);
        vector< vector<int> > special(primes.size(), vector<int>());
        vector<int> specialCnt(primes.size(), 0);
        vector<int> normal;
        for (int i = 0; i < n; ++ i) {
            int affect = 0, value = i + 1;
            //assert(scanf("%d", &value) == 1);
            assert(value >= 1 && value <= n);
            bool valid = true;
            for (int x = value; x > 1; x /= f[x]) {
                if (f[x] <= sqrt_n) {
                    int id = prime2index[f[x]];
                    assert(id != -1);

                    odd[id] ^= 1;
                    if (affect >> id & 1) {
                        valid = false; // we only need to consider the square free numbers
                    }

                    affect ^= 1 << id;
                }
            }
            if (valid) {
                if (f[value] <= sqrt_n) {
                    normal.push_back(affect);
                } else {
                    int id = prime2index[f[value]]; // for a value between 1 and n, there is at most ONE prime factor which is larger than sqrt(n)
                    assert(prime2index[f[value]] != -1);
                    special[id].push_back(affect);
                }
            }

            if (f[value] > sqrt_n) {
                int id = prime2index[f[value]];
                specialCnt[id] ^= 1;
            }

        }

        // compute the set of small primes which should be covered by removed numbers.
        int todo = 0;
        for (int i = 0; i < smallPrimes; ++ i) {
            todo ^= odd[i] << i;
        }

        memset(dp, 0, sizeof(dp));
        dp[0][todo] = 1;
        int now = 0, old = 1;
        for (int i = 0; i < normal.size(); ++ i) {
            if ((todo & normal[i]) != normal[i]) {
                continue;
            }
            int item = normal[i];

            now = 1 - now;
            old = 1 - old;
            memcpy(dp[now], dp[old], sizeof(dp[old]));
            for (int mask = 0; mask < 1 << smallPrimes; ++ mask) {
                if ((mask & item) == item) {
                    dp[now][mask ^ item] += dp[old][mask];
                    if (dp[now][mask ^ item] >= MOD) {
                        dp[now][mask ^ item] -= MOD;
                    }
                }
            }
        }

        int counter = 0;
        for (int i = 0; i < special.size(); ++ i) {
            if (specialCnt[i]) {
                // we must select one number from special[i]
                ++ counter;
                now = 1 - now;
                old = 1 - old;
                memset(dp[now], 0, sizeof(dp[now]));
                for (int j = 0; j < special[i].size(); ++ j) {
                    int item = special[i][j];
                    if ((item & todo) != item) {
                        continue;
                    }
                    for (int mask = 0; mask < 1 << smallPrimes; ++ mask) {
                        if ((mask & item) == item) {
                            dp[now][mask ^ item] += dp[old][mask];
                            if (dp[now][mask ^ item] >= MOD) {
                                dp[now][mask ^ item] -= MOD;
                            }
                        }
                    }
                }
            }
        }
        printf("%d\n", dp[now][0]);
    }
    return 0;
}