J. No Duplicates
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers $$$n$$$ and $$$m$$$, and $$$q$$$ restriction of the form $$$(l_i, r_i)$$$.

For each $$$k$$$ from $$$1$$$ to $$$q$$$, count, modulo $$$998\,244\,353$$$, the number of sequences of positive integers $$$a_1, a_2, \ldots, a_n$$$ such that the following conditions are satisfied:

  • $$$1 \leq a_i \leq m$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$.
  • For each $$$i$$$ from $$$1$$$ to $$$k$$$, all elements in the subarray $$$a_{l_i}, a_{l_i+1}, \ldots, a_{r_i}$$$ are distinct. That is, for each pair of indices $$$l_i \leq x \lt y \leq r_i$$$, $$$a_x \neq a_y$$$ is satisfied.
Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 5 \cdot 10^4)$$$ — the number of test cases.

The first line of each test case contains three integers $$$n, m$$$ and $$$q$$$ $$$(1 \leq n, q \leq 3 \cdot 10^5, n \leq m \leq 10^6)$$$.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \leq l_i \leq r_i \leq n)$$$.

It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$. Note that there are no constraints on the sum of $$$n$$$ or $$$m$$$.

Output

For each test case, print $$$q$$$ integers on separate lines — the $$$k$$$-th integer represents the answer for $$$k$$$ modulo $$$998\,244\,353$$$.

Example
Input
2
3 10 2
1 2
2 3
4 6 3
1 2
3 4
1 4
Output
900
810
1080
900
360