《数据结构与算法》期末考试的第一道题包含 $N$ 个术语和 $N$ 个定义。学生需要将每个术语与正确的定义匹配。不幸的是，高中时编写 Visual BASIC 程序并自认为精通计算机科学的 Joe，根本没去上课，也没看教科书。他只能随机猜测匹配结果。令 $S(N, k)$ 表示 Joe 回答该问题并至少有 $k$ 个匹配错误的方案数。

对于本题，你需要编写一个程序来计算 $S(N, k)$。

输入格式

输入的第一行包含一个整数 $P$ ($1 \le P \le 1000$)，表示随后数据组的数量。每组数据应被独立处理。

每组数据由一行输入组成，包含三个以空格分隔的十进制整数。第一个整数是数据组编号。第二个整数是 $N$ ($1 \le N \le 17$)，即问题中需要匹配的术语数量。第三个整数是 $k$ ($0 \le k \le N$)，即要求至少有 $k$ 个匹配错误。

输出格式

对于每组数据，输出一行。包含数据组编号，后跟一个空格，再后跟 $S(N, k)$ 的值。

样例

输入格式 1

4
1 4 1
2 7 3
3 10 5
4 17 17

输出格式 1

1 18
2 3216
3 2170680
4 130850092279664