给定一个包含顶点 $1, 2, \dots, n$ 的无向带权图 $G$。请输出以下 $x$ 个问题的答案之和：

• 第 $i$ 个问题（$1 \le i \le x$）：从顶点 $1$ 出发，到达顶点 $n$，且恰好包含 $i$ 条边的路径的最小长度是多少？

对于每个问题，如果不存在这样的路径，则答案视为 $0$。路径可以多次经过同一条边。请输出答案对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2000$)，表示测试用例的数量。

对于每个测试用例，第一行包含三个整数 $n, m, x$ ($1 \le n \le 2000, 0 \le m \le 5000, 1 \le x \le 10^9$)。

接下来的 $m$ 行，每行描述图中的一条边。第 $i$ 条边由三个整数 $a_i, b_i, w_i$ ($1 \le a_i, b_i \le n, 1 \le w_i \le 10^9$) 表示，分别为其连接的顶点编号及其权重。注意，图中可能存在自环和重边。

保证所有测试用例中 $n$ 的总和不超过 $2000$，$m$ 的总和不超过 $5000$。

输出格式

对于每个测试用例，输出一个整数，表示答案对 $998244353$ 取模的结果。

样例

输入 1

4
3 2 10
1 2 5
2 3 4
3 0 1000000000
3 3 100
1 2 3
1 3 4
2 3 5
4 6 1000000000
1 2 244
1 2 325
1 4 927
3 3 248
2 4 834
3 4 285

输出 1

125
0
15300
840659991