Du får oppgitt en bipartitt graf. Den venstre delen inneholder $n_1$ noder nummerert fra 1 til $n_1$, og den høyre delen inneholder $n_2$ noder nummerert fra 1 til $n_2$. Det er $m$ kanter, som hver forbinder én node til venstre med én node til høyre.

For hvert intervall $[l, r]$ på høyre side (der $1 \le l \le r \le n_2$), betrakt delgrafen som oppnås ved å:

• beholde alle venstre noder $1, 2, \dots, n_1$;
• beholde kun de høyre nodene med indekser i $[l, r]$;
• beholde kun kanter der begge endepunktene er beholdt.

I denne delgrafen skal du beregne størrelsen på en maksimal matching (det maksimale antallet parvis disjunkte kanter). La denne verdien betegnes med $f(l, r)$.

Du må beregne følgende verdi:

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

der $\oplus$ betegner den bitvise XOR-operasjonen.

Skriv ut verdien av denne summen modulo $998\,244\,353$.

Inndata

Inndataene inneholder flere testtilfeller.

Den første linjen inneholder et enkelt heltall $T$ ($1 \le T \le 2000$), antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen tre heltall $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), som representerer antallet noder til venstre, antallet noder til høyre og antallet kanter.

Hver av de neste $m$ linjene inneholder to heltall $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), som betyr at det går en kant mellom venstre node $u$ og høyre node $v$.

Det er garantert at det ikke finnes multikanter, og at verken summen av $n_1$ eller summen av $n_2$ overstiger $5000$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder ett heltall — den ønskede summen modulo $998\,244\,353$.

Eksempel

Inndata

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