考虑数轴上的 $n$ 个线段，其中第 $i$ 个线段的左端点为 $l_i$，右端点为 $r_i$。你需要将每个线段涂成 $k$ 种颜色之一，使得任意两个颜色相同的线段互不重叠。

如果存在实数 $x$ 满足 $l_i \le x \le r_i$ 且 $l_j \le x \le r_j$，则称线段 $i$ 与线段 $j$ 重叠。

如果两种涂色方案中至少有一个线段的颜色不同，则称这两种涂色方案不同。

计算涂色方案的总数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 5 \times 10^5$, $1 \le k \le 10^9$)，分别表示线段的数量和颜色的数量。

接下来的 $n$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le 10^9$)，表示第 $i$ 个线段的左端点和右端点。

保证所有测试数据的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示答案。由于答案可能很大，请输出其对 $998244353$ 取模的结果。

样例

输入 1

2
4 3
4 7
3 4
5 8
1 3
2 1000
100 200
300 400

输出 1

24
1000000

说明

设 $c_i$ 为第 $i$ 个线段的颜色。

对于第一个样例，一种合法的涂色方式是 $c_1 = 1, c_2 = 3, c_3 = 3, c_4 = 1$。因为第 1 个线段和第 4 个线段不重叠，且第 2 个线段和第 3 个线段也不重叠。

然而，$c_1 = 1, c_2 = 2, c_3 = 1, c_4 = 3$ 不是一种合法的涂色方式。因为第 1 个线段和第 3 个线段重叠，它们不能拥有相同的颜色。