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 $2 n$ vertices and report that number modulo a prime number $p$.

Input

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

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.