冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较每对相邻元素，如果它们的顺序错误就交换它们。遍历列表的工作重复进行，直到不需要交换为止，这表明列表已经排好序。

Izdihar 是一位 ACM-ICPC 大师，她为你提供了冒泡排序的伪代码实现。对于一个可排序项列表 $A$，该算法可以表示为（基于 1 的数组）：

1: function BUBBLESORT(A)
2: n ← the length of A
3: k ← n − 1  ▷ note the initial value of k might be replaced by a given number
4: for step = 1 to k do  ▷ passing through the list k times
5: for i = 2 to n do
6: if A[i − 1] > A[i] then
7: swap A[i − 1] and A[i]

她说，如果一个 $1$ 到 $n$ 的排列的最长上升子序列长度至少为 $n-1$，则称该排列为“几乎有序”的。

你需要计算 $1$ 到 $n$ 的排列中，有多少个排列在经过冒泡排序的 $k$ 次遍历后，会变成一个几乎有序的排列。

输入格式

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

对于每个测试用例，一行包含三个整数 $n, k$ ($1 \le n, k \le 50$)，如上所述，以及 $q$ ($10^8 \le q \le 10^9$)，这是一个用于输出的质数。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是从 $1$ 开始的测试用例编号，$y$ 是满足要求的排列数量对 $q$ 取模后的余数。

样例

输入 1

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

输出 1

Case #1: 74
Case #2: 114
Case #3: 120
Case #4: 120
Case #5: 120