Problem Description

A graph without loops or multiple edges is known as a simple graph.

A vertex-colouring is an assignment of colours to each vertex of a graph. A proper vertex-colouring is a vertex-colouring in which no edge connects two identically coloured vertices.

A vertex-colouring with $n$ colours of an undirected simple graph is called an $n$-rainbow colouring if every colour appears once, and only once, on all the adjacent vertices of each vertex. Note that an $n$-rainbow colouring is not a proper colouring, since adjacent vertices may share the same colour.

An undirected simple graph is called an $n$-rainbow graph if the graph can admit at least one legal $n$-rainbow colouring. Two $n$-rainbow graphs $G$ and $H$ are called isomorphic if, between the sets of vertices in $G$ and $H$, a bijective mapping $f : V(G) \to V(H)$ exists such that two vertices in $G$ are adjacent if and only if their images in $H$ are adjacent.

Your task in this problem is to count the number of distinct non-isomorphic $n$-rainbow graphs having $2n$ vertices and report that number modulo a prime number $p$.

Input Format

The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $1000$.

For each test case, the only line contains two integers $n$ and $p$ where $1 \le n \le 64$ , $n+1 \le p \le 2^{30}$ and $p$ is a prime.

We guarantee that the numbers of test cases satisfying $n \ge 16$ , $n \ge 32$ and $n \ge 48$ are no larger than $200$, $100$ and $20$ respectively.

Output Format

For each test case, output a line containing "Case #x: y" (without quotes), where $x$ is the test case number starting from $1$ , and $y$ is the answer modulo $p$.

5
1 11059
2 729557
3 1461283
4 5299739
63 49121057

Case #1: 1
Case #2: 1
Case #3: 2
Case #4: 3
Case #5: 5694570

Hint

If you came up with a solution such that the time complexity is asymptotic to $p(n)$, the number of partitions of $n$, or similar, you might want to know $p(16) = 231$, $p(32) = 8349$, $p(48) = 147273$ and $p(64) = 1741630$ .

The following figures illustrate all the non-isomorphic rainbow graphs mentioned in the first four sample cases.

:::align{center}

Figure 1: the non-isomorphic 1-rainbow graph with 2 vertices

Figure 2: the non-isomorphic 2-rainbow graph with 4 vertices

Figure 3: the non-isomorphic 3-rainbow graphs with 6 vertices

Figure 4: the non-isomorphic 4-rainbow graphs with 8 vertices :::