Problem E
Colorful Segments 2

Consider $n$ segments on the number axis, where the left endpoint of the $i$-th segment is $l_i$ and the right endpoint is $r_i$. You need to paint each segment into one of the $k$ colors, so that for any two segments with the same color they do not overlap.

Calculate the number of ways to color the segments.

We say segment $i$ overlaps with segment $j$, if there exists a real number $x$ satisfying both $l_i \le x \le r_i$ and $l_j \le x \le r_j$.

We say two ways of coloring the segments are different, if there exists one segment which has different colors in the two ways.

Input

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($1 \le n \le 5 \times 10^5$, $1 \le k \le 10^9$) indicating the number of segments and the number of colors.

For the following $n$ lines, the $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le 10^9$) indicating the left and right endpoints of the $i$-th segment.

It’s guaranteed that the sum of $n$ of all test cases will not exceed $5 \times 10^5$.

Output

For each test case output one line containing one integer indicating the answer. As the answer might be large, output it modulo $998244353$.

Note

Let $c_i$ be the color of the $i$-th segment.

For the first sample test case, one valid way to color the segments is $c_1 = 1$, $c_2 = 3$, $c_3 = 3$, and $c_4 = 1$. Because the $1$-st and the $4$-th segments do not overlap, also the $2$-nd and the $3$-rd segments do not overlap.

However, $c_1 = 1$, $c_2 = 2$, $c_3 = 1$, and $c_4 = 3$ is not a valid way. Because the $1$-st and the $3$-rd segments overlap with each other and they can’t have the same color.

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

24
1000000