You are the proud... never mind, just solve this problem.

There are $n$ intervals $[l_1, r_1], [l_2, r_2], \ldots [l_n, r_n]$. For each $x$ from $0$ to $2^m - 1$, find the number, modulo $998\,244\,353$, of sequences $a_1, a_2, \ldots a_n$ such that:

• $l_i \leq a_i \leq r_i$ for all $i$ from $1$ to $n$;
• $a_1 \oplus a_2 \oplus \ldots \oplus a_n = x$, where $\oplus$ denotes the bitwise XOR operator.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq m \leq 18$).

The $i$-th of the next $n$ lines contains two integers $l_i$ and $r_i$ ($0 \leq l_i \leq r_i \lt 2^m$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$, and the sum of $2^m$ over all test cases does not exceed $2^{18}$.

Output

For each $x$ from $0$ to $2^m - 1$, let:

• $f_x$ be the number of valid sequences, modulo $998\,244\,353$;
• $g_x = f_x \cdot 2^x \mod 998\,244\,353$.

Here, $f_x$ and $g_x$ are both integers in the interval $[0, 998\,244\,352]$.

Let $h = g_0 \oplus g_1 \oplus \ldots \oplus g_{2^m - 1}$.

Output a single integer — the value of $h$ itself. Do not perform a modulo operation.

Note

For the first test case, the values of $f_x$ are as follows:

• $f_0 = 2$, because there are $2$ valid sequences: $[1, 1]$ and $[2, 2]$;
• $f_1 = 2$, because there are $2$ valid sequences: $[0, 1]$ and $[2, 3]$;
• $f_2 = 2$, because there are $2$ valid sequences: $[0, 2]$ and $[1, 3]$;
• $f_3 = 3$, because there are $3$ valid sequences: $[0, 3]$, $[1, 2]$, and $[2, 1]$.

The values of $g_x$ are as follows:

• $g_0 = f_0 \cdot 2^0 = 2 \cdot 2^0 = 2$;
• $g_1 = f_1 \cdot 2^1 = 2 \cdot 2^1 = 4$;
• $g_2 = f_2 \cdot 2^2 = 2 \cdot 2^2 = 8$;
• $g_3 = f_3 \cdot 2^3 = 3 \cdot 2^3 = 24$.

Thus, the value to output is $2 \oplus 4 \oplus 8 \oplus 24 = 22$.

For the second test case, the values of $f_x$ are as follows:

• $f_{0} = 120$;
• $f_{1} = 120$;
• $f_{2} = 119$;
• $f_{3} = 118$;
• $f_{4} = 105$;
• $f_{5} = 105$;
• $f_{6} = 106$;
• $f_{7} = 107$.