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$$$.

✓	#	Name		✎	Rating↕	Solved↕
	2096H	Wonderful XOR Problem bitmasks combinatorics dp fft math			3200	235
	1773G	Game of Questions bitmasks combinatorics dp fft math probabilities			2800	560

Problemset