Bạn được cho một đồ thị hai phía. Phần bên trái gồm $n_1$ đỉnh được đánh số từ 1 đến $n_1$, và phần bên phải gồm $n_2$ đỉnh được đánh số từ 1 đến $n_2$. Có $m$ cạnh, mỗi cạnh nối một đỉnh ở bên trái với một đỉnh ở bên phải.

Với mỗi đoạn $[l, r]$ ở phía bên phải (trong đó $1 \le l \le r \le n_2$), xét đồ thị con thu được bằng cách:

• giữ lại tất cả các đỉnh bên trái $1, 2, \dots, n_1$;
• chỉ giữ lại các đỉnh bên phải có chỉ số thuộc $[l, r]$;
• chỉ giữ lại các cạnh có cả hai đầu mút đều được giữ lại.

Trong đồ thị con này, hãy tính kích thước của cặp ghép cực đại (số lượng lớn nhất các cạnh đôi một không chung đỉnh). Ký hiệu giá trị này là $f(l, r)$.

Bạn cần tính giá trị sau:

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

trong đó $\oplus$ biểu thị phép toán XOR bit.

Hãy in ra giá trị của tổng này theo modulo $998\,244\,353$.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test.

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 2000$), là số lượng bộ test.

Với mỗi bộ test, dòng đầu tiên chứa ba số nguyên $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$), lần lượt biểu thị số lượng đỉnh ở bên trái, số lượng đỉnh ở bên phải và số lượng cạnh.

Mỗi dòng trong $m$ dòng tiếp theo chứa hai số nguyên $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$), biểu thị có một cạnh nối giữa đỉnh bên trái $u$ và đỉnh bên phải $v$.

Dữ liệu đảm bảo không có cạnh bội, tổng của $n_1$ và tổng của $n_2$ đều không vượt quá $5000$.

Kết quả

Với mỗi bộ test, in ra một dòng duy nhất chứa một số nguyên — tổng cần tìm theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào

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

Kết quả

81
529
12
81