Se te da un grafo bipartito. La parte izquierda contiene $n_1$ vértices numerados de 1 a $n_1$, y la parte derecha contiene $n_2$ vértices numerados de 1 a $n_2$. Hay $m$ aristas, cada una conectando un vértice de la izquierda con un vértice de la derecha.

Para cada intervalo $[l, r]$ en el lado derecho (donde $1 \le l \le r \le n_2$), considera el subgrafo obtenido al:

• conservar todos los vértices izquierdos $1, 2, \dots, n_1$;
• conservar únicamente los vértices derechos con índices en $[l, r]$;
• conservar únicamente las aristas cuyos dos extremos se hayan conservado.

En este subgrafo, calcula el tamaño de un emparejamiento máximo (el número máximo de aristas disjuntas dos a dos). Sea $f(l, r)$ dicho valor.

Debes calcular el siguiente valor:

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

donde $\oplus$ denota la operación XOR bit a bit.

Imprime el valor de esta suma módulo $998\,244\,353$.

Entrada

La entrada contiene múltiples casos de prueba.

La primera línea contiene un solo entero $T$ ($1 \le T \le 2000$), el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene tres enteros $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), que representan el número de vértices a la izquierda, el número de vértices a la derecha y el número de aristas.

Cada una de las siguientes $m$ líneas contiene dos enteros $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), indicando que hay una arista entre el vértice izquierdo $u$ y el vértice derecho $v$.

Se garantiza que no hay aristas múltiples, y que ni la suma de $n_1$ ni la suma de $n_2$ supera $5000$.

Salida

Para cada caso de prueba, imprime una sola línea con un entero — la suma requerida módulo $998\,244\,353$.

Ejemplo

Entrada

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

Salida

81
529
12
81