給定一個二分圖。左部包含 $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