Bob 写了一个如下所示的伪快速排序实现。你能算出如果他从 $1, 2, \dots, n$ 中等概率随机选择一个排列 $p = [p_1, p_2, \dots, p_n]$，在调用 QuickSort(p, 1, n, k) 后，排列 $p$ 的期望逆序对数量是多少吗？

函数 1 — 一个伪快速排序实现

1: function QuickSort(A, l, r, h) ▷ Elements in A would be modified
2: if h > 1 and l < r then
3: m ← Partition(A, l, r)
4: QuickSort(A, l, m - 1, h - 1)
5: QuickSort(A, m + 1, r, h - 1)
6: function Partition(A, l, r) ▷ Elements in A would be modified
7: i ← l
8: j ← r
9: m ← ⌊(l + r) / 2⌋
10: pivot ← Am
11: Am ← Ai
12: while i < j do
13: while i < j and Aj ≥ pivot do
14: j ← j - 1
15: if i < j then
16: Ai ← Aj
17: while i < j and Ai < pivot do
18: i ← i + 1
19: if i < j then
20: Aj ← Ai
21: Ai ← pivot
22: return i

排列 $[p_1, p_2, \dots, p_n]$ 的逆序对数量是指满足 $1 \le u < v \le n$ 且 $p_u > p_v$ 的整数对 $(u, v)$ 的数量。

为了避免精度问题，请你输出 $n!$（$n$ 的阶乘）与期望逆序对数量的乘积，对 $998244353$ 取模。该结果应当是一个整数。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。接下来描述所有测试用例。对于每个测试用例：

仅一行，包含两个整数 $n$ 和 $k$。

• $1 \le T \le 3 \times 10^5$
• $1 \le n, k \le 6000$

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是从 1 开始的测试用例编号，$y$ 是该测试用例的答案。

样例

样例输入 1

5
5 1
5 2
5 3
5 4
5 5

样例输出 1

Case #1: 600
Case #2: 240
Case #3: 64
Case #4: 8
Case #5: 0