对于一棵具有 $n$ 个顶点（编号为 $1$ 到 $n$）的树 $t$，令 $f(t)$ 为满足以下条件的排列 $p = (p_1, \dots, p_n)$ 的数量：

• 对于每个 $i = 1, \dots, n$，连接顶点 $p_i$ 和 $p_{i+1}$ 的简单路径上最多有 $2$ 条边，其中 $p_{n+1} = p_1$。

给定正整数 $N, K$ 以及一棵具有 $N$ 个顶点（编号为 $1$ 到 $N$）的树 $T_0$。$T_0$ 的第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

通过连接 $K$ 个不相交的 $T_0$ 副本所得到的树称为“好树”（good tree）。更正式地说，我们将一棵具有 $NK$ 个顶点（编号为 $1$ 到 $NK$）的树称为好树，当且仅当满足以下条件：

• 对于所有整数 $1 \le i \le N - 1$ 和 $0 \le k \le K - 1$，顶点 $(A_i + N \times k)$ 和 $(B_i + N \times k)$ 之间存在一条边。

求所有好树 $T$ 的 $f(T)$ 之和，并将该值对 $998244353$ 取模。

共有 $Q$ 组测试数据；请解决每一组数据。

输入格式

输入通过标准输入给出，格式如下：

$Q$ $\text{case}_1$ $\vdots$ $\text{case}_Q$

每组测试数据格式如下：

$N \ K$ $A_1 \ B_1$ $\vdots$ $A_{N-1} \ B_{N-1}$

数据范围

• $1 \le Q \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $1 \le K \le 2 \times 10^5$
• $1 \le A_i < B_i \le N$
• 所有测试数据的 $N$ 之和不超过 $2 \times 10^5$
• $T_0$ 是一棵树。
• 所有输入值均为整数。

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 组测试数据的答案。

样例

输入格式 1

5
4 1
1 2
1 3
1 4
4 1
1 2
2 3
3 4
1 4
4 2
1 2
1 3
1 4
6 200000
1 3
2 3
3 4
4 5
4 6

输出格式 1

24
8
192
2304
210217795

说明

在第一组测试数据中，由于每条简单路径最多有 $2$ 条边，因此计算所有可能的排列。

在第二组测试数据中，你需要计算 $8$ 个排列：$(1, 2, 4, 3), (1, 3, 4, 2), (2, 1, 3, 4), (2, 4, 3, 1), (3, 1, 2, 4), (3, 4, 2, 1), (4, 2, 1, 3)$ 和 $(4, 3, 1, 2)$。

在第三组测试数据中，你需要计算所有具有 $4$ 个顶点的树 $T$ 的 $f(T)$ 之和。注意 $T_0$ 可能没有边。

在第四组测试数据中，以下树是好树的示例：