Gegeben ist ein bipartiter Graph. Der linke Teil enthält $n_1$ Knoten, die von 1 bis $n_1$ nummeriert sind, und der rechte Teil enthält $n_2$ Knoten, die von 1 bis $n_2$ nummeriert sind. Es gibt $m$ Kanten, die jeweils einen Knoten auf der linken Seite mit einem Knoten auf der rechten Seite verbinden.

Betrachten Sie für jedes Intervall $[l, r]$ auf der rechten Seite (wobei $1 \le l \le r \le n_2$) den Teilgraphen, der entsteht, indem man:

• alle linken Knoten $1, 2, \dots, n_1$ behält;
• nur die rechten Knoten mit Indizes in $[l, r]$ behält;
• nur Kanten behält, deren beide Endpunkte behalten wurden.

Berechnen Sie in diesem Teilgraphen die Größe eines maximalen Matchings (die maximale Anzahl paarweise disjunkter Kanten). Dieser Wert sei mit $f(l, r)$ bezeichnet.

Sie müssen den folgenden Wert berechnen:

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

wobei $\oplus$ die bitweise XOR-Operation bezeichnet.

Geben Sie den Wert dieser Summe modulo $998\,244\,353$ aus.

Eingabe

Die Eingabe enthält mehrere Testfälle.

Die erste Zeile enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 2000$), die Anzahl der Testfälle.

Für jeden Testfall enthält die erste Zeile drei ganze Zahlen $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), die die Anzahl der Knoten auf der linken Seite, die Anzahl der Knoten auf der rechten Seite und die Anzahl der Kanten angeben.

Jede der nächsten $m$ Zeilen enthält zwei ganze Zahlen $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), was bedeutet, dass es eine Kante zwischen dem linken Knoten $u$ und dem rechten Knoten $v$ gibt.

Es wird garantiert, dass es keine Mehrfachkanten gibt und weder die Summe der $n_1$ noch die Summe der $n_2$ den Wert $5000$ überschreitet.

Ausgabe

Geben Sie für jeden Testfall eine einzige Zeile mit einer ganzen Zahl aus — die gesuchte Summe modulo $998\,244\,353$.

Beispiel

Eingabe

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

Ausgabe

81
529
12
81