插入排序是一种简单的排序算法，它通过每次迭代构建最终的有序数组。

更准确地说，插入排序在每次重复时消耗一个输入元素，并增长一个有序输出列表。在每次迭代中，插入排序从输入数据中移除一个元素，找到它在有序列表中的所属位置，并将其插入。该过程重复进行，直到没有剩余的输入元素。

这种排序通常是原地进行的，通过遍历数组，在数组后面增长有序部分。在每个数组位置，它将该处的值与有序数组中的最大值（恰好位于其前一个已检查的数组位置）进行比较。如果较大，则保持该元素不动并移动到下一个位置。如果较小，则在有序数组中找到正确的位置，将所有较大的值向上移动以腾出空间，并插入到该正确位置。

经过 $k$ 次迭代后，结果数组具有前 $k$ 个条目已排序的特性。在每次迭代中，输入中第一个剩余的条目被移除，并插入到结果中的正确位置，从而扩展了结果。

Knuth 是一位 ACM-ICPC 大师，他为你提供了一个插入排序的修改版伪代码实现。他针对可排序项数组 $A$（1-based 数组）的修改算法可以表示为：

1: function INSERTIONSORT(A, k) ▷ Elements in A would be modified
2:     n ← the length of A
3:     i ← 1
4:     while i ≤ n and i ≤ k do ▷ the i-th iteration
5:         j ← i
6:         while j > 1 and A[j - 1] > A[j] do
7:             t ← A[j]
8:             A[j] ← A[j - 1]
9:             A[j - 1] ← t
10:            j ← j - 1
11:        end while
12:        i ← i + 1
13:    end while
14: end function

他指出，如果一个 $1$ 到 $n$ 的排列的最长递增子序列长度至少为 $(n - 1)$，则称该排列为“几乎有序”的。

给定参数 $k$，请你计算满足以下条件的 $1$ 到 $n$ 的不同排列的数量：在经过他的修改版插入排序后，每个排列都会变成一个几乎有序的排列。

输入格式

输入包含多个测试用例，第一行包含一个正整数 $T$，表示测试用例的数量，最多为 $5000$。

对于每个测试用例，唯一的一行包含三个整数 $n, k$ 和 $q$，分别表示排列的长度、他实现中的参数以及输出所需的质数，其中 $1 \le n, k \le 50$ 且 $10^8 \le q \le 10^9$。

输出格式

对于每个测试用例，输出一行包含 “Case #x: y”（不含引号），其中 $x$ 是从 $1$ 开始的测试用例编号，$y$ 是满足条件的排列数量除以 $q$ 的余数。

样例

输入格式 1

4
4 1 998244353
4 2 998244353
4 3 998244353
4 4 998244353

输出格式 1

Case #1: 10
Case #2: 14
Case #3: 24
Case #4: 24

说明

在第一个样例中，我们可以发现有 $10$ 个排列满足条件，它们列出如下：

• [1, 2, 3, 4];
• [1, 2, 4, 3];
• [1, 3, 2, 4];
• [1, 3, 4, 2];
• [1, 4, 2, 3];
• [2, 1, 3, 4];
• [2, 3, 1, 4];
• [2, 3, 4, 1];
• [3, 1, 2, 4];
• [4, 1, 2, 3].