Þér er gefið tvíhluta net (bipartite graph). Vinstri hlutinn inniheldur $n_1$ hnúta sem eru númeraðir frá 1 til $n_1$, og hægri hlutinn inniheldur $n_2$ hnúta sem eru númeraðir frá 1 til $n_2$. Það eru $m$ leggir, og tengir hver þeirra einn hnút vinstra megin við einn hnút hægra megin.

Fyrir sérhvert bil $[l, r]$ hægra megin (þar sem $1 \le l \le r \le n_2$), skoðið hlutnetið sem fæst með því að:

• halda öllum vinstri hnútunum $1, 2, \dots, n_1$;
• halda aðeins þeim hægri hnútum sem hafa vísa á bilinu $[l, r]$;
• halda aðeins þeim leggjum sem hafa báða endapunkta sína inni.

Í þessu hlutneti skal reikna stærð stærstu pörunar (hámarksfjölda innbyrðis sundurlægra leggja). Látum þetta gildi vera táknað með $f(l, r)$.

Þú þarft að reikna eftirfarandi gildi:

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

þar sem $\oplus$ táknar bitbundnu XOR-aðgerðina.

Prentið gildi þessarar summu modulo $998\,244\,353$.

Inntak

Inntakið inniheldur mörg prófunartilvik.

Fyrsta línan inniheldur eina heiltölu $T$ ($1 \le T \le 2000$), fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan þrjár heiltölur $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), sem tákna fjölda hnúta vinstra megin, fjölda hnúta hægra megin og fjölda leggja.

Hver af næstu $m$ línum inniheldur tvær heiltölur $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), sem táknar að leggur sé á milli vinstri hnútsins $u$ og hægri hnútsins $v$.

Tryggt er að engir margfaldir leggir séu til staðar, og hvorki summa $n_1$ né summa $n_2$ fer yfir $5000$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina heiltölu — umbeðnu summuna modulo $998\,244\,353$.

Dæmi

Inntak

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

Úttak

81
529
12
81