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) arrow.r 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$.
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 <= n <= 64$, $n + 1 <= p <= 2^(30)$ and $p$ is a prime.
We guarantee that the numbers of test cases satisfying $n >= 16$, $n >= 32$ and $n >= 48$ are no larger than $200$, $100$ and $20$ respectively.
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$.
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.
## 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 <= n <= 64$, $n + 1 <= p <= 2^(30)$ and $p$ is a prime.We guarantee that the numbers of test cases satisfying $n >= 16$, $n >= 32$ and $n >= 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$.
[samples]
## Note
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.
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ p $ a prime.
An **$ n $-rainbow graph** is a simple undirected graph $ G = (V, E) $ with $ |V| = 2n $, equipped with a vertex colouring $ c: V \to \{1, 2, \dots, n\} $ such that for every vertex $ v \in V $, the multiset of colours of its neighbours is exactly $ \{1, 2, \dots, n\} $, each appearing exactly once.
*(Note: Adjacent vertices may share the same colour; colouring is not proper.)*
Two $ n $-rainbow graphs $ G, H $ are **isomorphic** if there exists a bijection $ f: V(G) \to V(H) $ such that $ \{u,v\} \in E(G) \iff \{f(u),f(v)\} \in E(H) $, and $ c_G(u) = c_H(f(u)) $ for all $ u \in V(G) $.
**Constraints**
1. $ 1 \le n \le 64 $
2. $ n+1 \le p \le 2^{30} $, $ p $ prime
3. Number of test cases $ T \le 1000 $, with at most 200 cases where $ n \ge 16 $, 100 where $ n \ge 32 $, 20 where $ n \ge 48 $
**Objective**
For each test case, compute the number of **non-isomorphic** $ n $-rainbow graphs on $ 2n $ vertices, modulo $ p $.