Dany jest graf dwudzielny. Lewa część zawiera $n_1$ wierzchołków ponumerowanych od 1 do $n_1$, a prawa część zawiera $n_2$ wierzchołków ponumerowanych od 1 do $n_2$. Istnieje $m$ krawędzi, z których każda łączy jeden wierzchołek po lewej stronie z jednym wierzchołkiem po prawej stronie.

Dla każdego przedziału $[l, r]$ po prawej stronie (gdzie $1 \le l \le r \le n_2$) rozważ podgraf otrzymany poprzez:

• zachowanie wszystkich lewych wierzchołków $1, 2, \dots, n_1$;
• zachowanie tylko prawych wierzchołków o indeksach z przedziału $[l, r]$;
• zachowanie tylko tych krawędzi, których oba końce zostały zachowane.

W tym podgrafie oblicz rozmiar maksymalnego skojarzenia (maksymalną liczbę parami rozłącznych krawędzi). Oznaczmy tę wartość przez $f(l, r)$.

Musisz obliczyć następującą wartość:

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

gdzie $\oplus$ oznacza operację bitowego XOR.

Wypisz wartość tej sumy modulo $998\,244\,353$.

Wejście

Wejście zawiera wiele przypadków testowych.

Pierwszy wiersz zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 2000$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera trzy liczby całkowite $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), oznaczające liczbę wierzchołków po lewej stronie, liczbę wierzchołków po prawej stronie oraz liczbę krawędzi.

Każdy z kolejnych $m$ wierszy zawiera dwie liczby całkowite $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), oznaczające istnienie krawędzi między lewym wierzchołkiem $u$ a prawym wierzchołkiem $v$.

Gwarantuje się, że nie ma krawędzi wielokrotnych, a suma $n_1$ oraz suma $n_2$ nie przekraczają $5000$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający jedną liczbę całkowitą — szukaną sumę modulo $998\,244\,353$.

Przykład

Wejście

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

Wyjście

81
529
12
81