畀一個二分圖你。左邊部分包含 $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