Вам дан двудольный граф. Левая доля содержит $n_1$ вершин, пронумерованных от 1 до $n_1$, а правая доля содержит $n_2$ вершин, пронумерованных от 1 до $n_2$. В графе есть $m$ рёбер, каждое из которых соединяет одну вершину слева с одной вершиной справа.

Для каждого отрезка $[l, r]$ в правой доле (где $1 \le l \le r \le n_2$) рассмотрим подграф, полученный следующим образом:

• оставляем все вершины левой доли $1, 2, \dots, n_1$;
• оставляем только вершины правой доли с номерами из $[l, r]$;
• оставляем только те рёбра, оба конца которых остались.

В этом подграфе вычислим размер максимального паросочетания (максимальное количество попарно не пересекающихся рёбер). Обозначим это значение через $f(l, r)$.

Вам необходимо вычислить следующее значение:

$$\sum_{1 \le l \le r \le n_2} f(l, r) \cdot l \cdot r \cdot ((l \oplus r) + 1),$$

где $\oplus$ обозначает операцию побитового исключающего ИЛИ (XOR).

Выведите значение этой суммы по модулю $998\,244\,353$.

Входные данные

Входные данные содержат несколько наборов входных данных.

Первая строка содержит одно целое число $T$ ($1 \le T \le 2000$) — количество наборов входных данных.

Для каждого набора входных данных первая строка содержит три целых числа $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), обозначающих количество вершин в левой доле, количество вершин в правой доле и количество рёбер.

Каждая из следующих $m$ строк содержит два целых числа $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), означающих наличие ребра между вершиной $u$ левой доли и вершиной $v$ правой доли.

Гарантируется, что кратных рёбер нет, а сумма $n_1$ и сумма $n_2$ не превышают $5000$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую одно целое число — требуемую сумму по модулю $998\,244\,353$.

Пример

Входные данные

4
3 3 5
1 1
2 1
2 2
2 3
3 3
3 4 6
1 2
1 4
2 3
2 1
3 4
3 3
2 2 1
1 2
4 3 5
1 3
2 1
3 3
4 2
4 1

Выходные данные

81
529
12
81