Description

有 $n$ 个人前来打乒乓。

由于时间有限，一共只能打 $m$ 场，你需要告诉他们一共有多少种安排方式，使得恰好有 $k$ 个人只打了一场比赛，答案对 $998244353$ 取模。

具体的，一种安排由 $m$ 场比赛组成，每场比赛由两个不同的人完成。且在一个安排中，两个人之间不能打多次。可以有人一场也不打。两种安排不同，当且仅当存在两个人，他们在一个安排中打了，而在另一个安排中没有。

Input

第一行一个正整数 $T$（$1\le T\le 1000$），表示数据组数。

对于每组数据，一行三个整数，分别为 $n$，$m$，$k$（$1\le n \leq 5 \times 10^3$，$0\le m \leq \frac{n \times (n - 1)}{2}$，$0 \leq k \leq n$）。

保证对于所有数据，满足 $\sum n \leq 5\times 10^3$。

Output

对于每组数据，输出一行一个整数，表示答案。

Samples

2
4 3 2
3 2 2

12
3

Resources

The 23rd UESTC Programming Contest Preliminary