# 1. 题目

$n \leq 28, m \leq 3 \times 10 ^ 4$

# 2. 题解

QAQ 居然找到了 zyf 蒯的题 QwQ

$f[i][j]$表示当前还没被选择集合为 $i$，最后一个选的元素为 $j$的方案数。

$c[i]$还要 $+ 1$的原因是可以不选，即我们要用这一位表示出 $[0, c[i]]$，一共 $c[i] + 1$个状态。

$f[i][j]$表示当前每一类的剩余数字数量状态为 $i$，最后选择的是第 $j$类的方案数。

#include <bits/stdc++.h>

#define REG register

using namespace std;

const int prm[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 0};

template <typename _Tp> inline void IN(_Tp& dig)
{
REG char c; REG bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int T, n, m, blk[30], x[16], tp, c[15];

bool book[15][15];

void Init()
{
REG int h[1 << 6] = {0}, d[15] = {0}, cnt = 0;
for (REG int i = 1; i <= 28; i += 1)
{
if (i == 1 || i == 17 || i == 19 || i == 23) {blk[i] = 0; continue;}
REG int st = 0;
for (REG int j = 0; j <= 5; j += 1)
if (i % prm[j] == 0)
st |= (1 << j);
if (h[st]) blk[i] = h[st];
else blk[i] = h[st] = ++cnt, d[cnt] = st;
}
for (REG int i = 0; i <= cnt; i += 1)
for (REG int j = 0; j <= cnt; j += 1)
if (d[i] & d[j]) book[i][j] = 0;
else book[i][j] = 1;
}

inline int hs(int (&a)[15])
{
REG int res = 0;
for (REG int i = 0; i <= tp; i += 1) res += a[i] * x[i];
return res;
}

inline int uhs(REG int st, REG int a)
{
return (st % x[a + 1]) / x[a];
}

int f[2000000][15], ans;

inline int pls(REG int a, REG int b) {return a + b >= m ? a + b - m : a + b;}

int Dfs(REG int rem, REG int p)
{
if (!rem) return 1;
if (f[rem][p] != -1) return f[rem][p];
int& F = f[rem][p]; F = 0;
for (REG int i = 0; i <= tp; i += 1)
if (book[p][i] && uhs(rem, i))
F = pls(F, Dfs(rem - x[i], i));
return F;
}

int main(int argc, char const* argv[])
{
Init(), IN(T);
while (T--)
{
IN(n), IN(m), tp = 0, memset(f, -1, sizeof(f)), memset(x, 0, sizeof(x));
if (m == 1) {puts("0"); continue;}
for (REG int i = 1; i <= n; i += 1)
tp = max(tp, blk[i]), x[blk[i]]++;
for (REG int i = 0; i <= tp; i += 1) c[i] = x[i], x[i]++;
for (REG int i = tp + 1; i >= 1; i -= 1) x[i] = x[i - 1];
x[0] = 1;
for (REG int i = 1; i <= tp + 1; i += 1) x[i] *= x[i - 1];
ans = Dfs(hs(c), 0);
for (REG int i = 0; i <= tp; i += 1)
while (c[i]) ans = ans * c[i] % m, c[i]--;
printf("%d\n", ans);
}
return 0;
}