Anda diberikan sebuah graf bipartit. Bagian kiri memuat $n_1$ simpul yang dinomori dari 1 hingga $n_1$, dan bagian kanan memuat $n_2$ simpul yang dinomori dari 1 hingga $n_2$. Terdapat $m$ sisi, masing-masing menghubungkan satu simpul di sebelah kiri ke satu simpul di sebelah kanan.

Untuk setiap interval $[l, r]$ di sisi kanan (dengan $1 \le l \le r \le n_2$), tinjau subgraf yang diperoleh dengan:

• mempertahankan semua simpul kiri $1, 2, \dots, n_1$;
• mempertahankan hanya simpul-simpul kanan dengan indeks di dalam $[l, r]$;
• mempertahankan hanya sisi-sisi yang kedua titik ujungnya dipertahankan.

Pada subgraf ini, hitung ukuran maximum matching (banyaknya sisi maksimum yang saling lepas berpasangan). Misalkan nilai ini dinyatakan dengan $f(l, r)$.

Anda perlu menghitung nilai berikut:

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

dengan $\oplus$ menyatakan operasi XOR bitwise.

Keluarkan nilai dari jumlah ini modulo $998\,244\,353$.

Masukan

Masukan terdiri dari beberapa kasus uji.

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 2000$), yaitu banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi tiga bilangan bulat $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), yang menyatakan banyaknya simpul di sebelah kiri, banyaknya simpul di sebelah kanan, dan banyaknya sisi.

Masing-masing dari $m$ baris berikutnya berisi dua bilangan bulat $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), yang menyatakan bahwa terdapat sisi antara simpul kiri $u$ dan simpul kanan $v$.

Dijamin tidak ada sisi ganda, serta jumlah dari $n_1$ maupun jumlah dari $n_2$ tidak melebihi $5000$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi satu bilangan bulat — jumlah yang diminta modulo $998\,244\,353$.

Contoh

Masukan

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

Keluaran

81
529
12
81