Du får en bipartit graf. Den vänstra delen innehåller $n_1$ hörn numrerade från 1 till $n_1$, och den högra delen innehåller $n_2$ hörn numrerade från 1 till $n_2$. Det finns $m$ kanter, som var och en förbinder ett hörn till vänster med ett hörn till höger.

För varje intervall $[l, r]$ på den högra sidan (där $1 \le l \le r \le n_2$), betrakta delgrafen som erhålls genom att:

• behålla alla vänstra hörn $1, 2, \dots, n_1$;
• behålla endast de högra hörnen med index i $[l, r]$;
• behålla endast kanter vars båda ändpunkter har behållits.

Beräkna i denna delgraf storleken på en maximal matchning (det maximala antalet parvis disjunkta kanter). Låt detta värde betecknas med $f(l, r)$.

Du ska beräkna följande värde:

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

där $\oplus$ betecknar den bitvisa XOR-operationen.

Skriv ut värdet av denna summa modulo $998\,244\,353$.

Indata

Indata innehåller flera testfall.

Den första raden innehåller ett enda heltal $T$ ($1 \le T \le 2000$), antalet testfall.

För varje testfall innehåller den första raden tre heltal $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), som representerar antalet hörn till vänster, antalet hörn till höger respektive antalet kanter.

Var och en av de följande $m$ raderna innehåller två heltal $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), vilket anger att det finns en kant mellan det vänstra hörnet $u$ och det högra hörnet $v$.

Det garanteras att det inte finns några multipelkanter, och att varken summan av $n_1$ eller summan av $n_2$ överstiger $5000$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett heltal — den efterfrågade summan modulo $998\,244\,353$.

Exempel

Indata

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

Utdata

81
529
12
81