On vous donne un graphe biparti. La partie gauche contient $n_1$ sommets numérotés de 1 à $n_1$, et la partie droite contient $n_2$ sommets numérotés de 1 à $n_2$. Il y a $m$ arêtes, chacune reliant un sommet à gauche à un sommet à droite.

Pour chaque intervalle $[l, r]$ du côté droit (où $1 \le l \le r \le n_2$), on considère le sous-graphe obtenu en :

• conservant tous les sommets gauches $1, 2, \dots, n_1$ ;
• conservant uniquement les sommets droits dont les indices sont dans $[l, r]$ ;
• conservant uniquement les arêtes dont les deux extrémités sont conservées.

Dans ce sous-graphe, calculez la taille d'un couplage maximum (le nombre maximum d'arêtes deux à deux disjointes). Notons cette valeur $f(l, r)$.

Vous devez calculer la valeur suivante :

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

où $\oplus$ désigne l'opération XOR bit à bit.

Affichez la valeur de cette somme modulo $998\,244\,353$.

Entrée

L'entrée contient plusieurs cas de test.

La première ligne contient un seul entier $T$ ($1 \le T \le 2000$), le nombre de cas de test.

Pour chaque cas de test, la première ligne contient trois entiers $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), représentant le nombre de sommets à gauche, le nombre de sommets à droite et le nombre d'arêtes.

Chacune des $m$ lignes suivantes contient deux entiers $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), indiquant qu'il y a une arête entre le sommet gauche $u$ et le sommet droit $v$.

Il est garanti qu'il n'y a pas d'arêtes multiples, et que ni la somme des $n_1$ ni la somme des $n_2$ ne dépasse $5000$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un entier — la somme demandée modulo $998\,244\,353$.

Exemple

Entrée

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

Sortie

81
529
12
81