Sinulle annetaan kaksijakoinen verkko. Vasen osa sisältää $n_1$ solmua, jotka on numeroitu 1:stä $n_1$:een, ja oikea osa sisältää $n_2$ solmua, jotka on numeroitu 1:stä $n_2$:een. Verkossa on $m$ kaarta, joista jokainen yhdistää yhden vasemmanpuoleisen solmun yhteen oikeanpuoleiseen solmuun.

Jokaiselle oikean puolen välille $[l, r]$ (missä $1 \le l \le r \le n_2$), tarkastele aliverkkoa, joka saadaan:

• säilyttämällä kaikki vasemmanpuoleiset solmut $1, 2, \dots, n_1$;
• säilyttämällä vain ne oikeanpuoleiset solmut, joiden indeksit kuuluvat välille $[l, r]$;
• säilyttämällä vain ne kaaret, joiden molemmat päätepisteet on säilytetty.

Laske tässä aliverkossa suurimman sovituksen (maximum matching) koko (suurin mahdollinen määrä pareittain erillisiä kaaria). Merkitään tätä arvoa $f(l, r)$:llä.

Sinun tulee laskea seuraava arvo:

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

missä $\oplus$ tarkoittaa bittikohtaista XOR-operaatiota.

Tulosta tämän summan arvo modulo $998\,244\,353$.

Syöte

Syöte sisältää useita testitapauksia.

Ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 2000$), testitapausten lukumäärän.

Jokaisen testitapauksen ensimmäinen rivi sisältää kolme kokonaislukua $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), jotka ilmaisevat vasemman puolen solmujen määrän, oikean puolen solmujen määrän ja kaarien määrän.

Jokainen seuraavista $m$ rivistä sisältää kaksi kokonaislukua $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), mikä tarkoittaa, että vasemman solmun $u$ ja oikean solmun $v$ välillä on kaari.

On taattu, ettei verkossa ole moninkertaisia kaaria, eikä $n_1$:n summa eikä $n_2$:n summa ylitä arvoa $5000$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää yhden kokonaisluvun — vaaditun summan modulo $998\,244\,353$.

Esimerkki

Syöte

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

Tuloste

81
529
12
81