Вам задано двочастковий граф. Ліва частка містить $n_1$ вершин, пронумерованих від 1 до $n_1$, а права частка містить $n_2$ вершин, пронумерованих від 1 до $n_2$. У графі є $m$ ребер, кожне з яких з'єднує одну вершину зліва з однією вершиною справа.

Для кожного відрізка $[l, r]$ у правій частці (де $1 \le l \le r \le n_2$) розглянемо підграф, отриманий таким чином:

• залишаємо всі вершини лівої частки $1, 2, \dots, n_1$;
• залишаємо лише вершини правої частки з номерами в $[l, r]$;
• залишаємо лише ті ребра, обидва кінці яких залишилися.

У цьому підграфі обчислимо розмір максимального паросполучення (максимальну кількість попарно неперетинних ребер). Позначимо це значення через $f(l, r)$.

Вам потрібно обчислити таке значення:

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

де $\oplus$ позначає операцію побітового виключного АБО (XOR).

Виведіть значення цієї суми за модулем $998\,244\,353$.

Вхідні дані

Вхідні дані містять кілька тестових випадків.

Перший рядок містить одне ціле число $T$ ($1 \le T \le 2000$) — кількість тестових випадків.

Для кожного тестового випадку перший рядок містить три цілі числа $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), що позначають кількість вершин у лівій частці, кількість вершин у правій частці та кількість ребер.

Кожен із наступних $m$ рядків містить два цілі числа $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), що означають наявність ребра між лівою вершиною $u$ та правою вершиною $v$.

Гарантується, що кратних ребер немає, а сума $n_1$ і сума $n_2$ не перевищують $5000$.

Вихідні дані

Для кожного тестового випадку виведіть один рядок, що містить одне ціле число — шукану суму за модулем $998\,244\,353$.

Приклад

Вхідні дані

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

Вихідні дані

81
529
12
81