Ti viene dato un grafo bipartito. La parte sinistra contiene $n_1$ vertici numerati da 1 a $n_1$, e la parte destra contiene $n_2$ vertici numerati da 1 a $n_2$. Ci sono $m$ archi, ciascuno dei quali collega un vertice a sinistra a un vertice a destra.

Per ogni intervallo $[l, r]$ sul lato destro (dove $1 \le l \le r \le n_2$), considera il sottografo ottenuto:

• mantenendo tutti i vertici sinistri $1, 2, \dots, n_1$;
• mantenendo solo i vertici destri con indici in $[l, r]$;
• mantenendo solo gli archi i cui estremi sono entrambi mantenuti.

In questo sottografo, calcola la dimensione di un accoppiamento massimo (il numero massimo di archi a due a due disgiunti). Indichiamo questo valore con $f(l, r)$.

Devi calcolare il seguente valore:

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

dove $\oplus$ indica l'operazione XOR bit a bit.

Stampa il valore di questa somma modulo $998\,244\,353$.

Input

L'input contiene più casi di test.

La prima riga contiene un singolo intero $T$ ($1 \le T \le 2000$), il numero di casi di test.

Per ciascun caso di test, la prima riga contiene tre interi $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), che rappresentano il numero di vertici a sinistra, il numero di vertici a destra e il numero di archi.

Ciascuna delle successive $m$ righe contiene due interi $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), a indicare che c'è un arco tra il vertice sinistro $u$ e il vertice destro $v$.

È garantito che non ci sono archi multipli e che né la somma degli $n_1$ né la somma degli $n_2$ supera $5000$.

Output

Per ciascun caso di test, stampa una singola riga contenente un intero — la somma richiesta modulo $998\,244\,353$.

Esempio

Input

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

Output

81
529
12
81