给定一个二分图。左部包含 $n_1$ 个顶点，编号从 $1$ 到 $n_1$；右部包含 $n_2$ 个顶点，编号从 $1$ 到 $n_2$。共有 $m$ 条边，每条边连接左部的一个顶点和右部的一个顶点。

对于右部的每个区间 $[\ell, r]$（其中 $1 \le \ell \le r \le n_2$），考虑通过以下方式得到的子图：

• 保留所有左部顶点 $1, 2, \dots, n_1$；
• 仅保留编号在 $[\ell, r]$ 内的右部顶点；
• 仅保留两个端点均被保留的边。

在这个子图中，计算最大匹配的大小（两两不相交的边的最大数量）。设该值为 $f(\ell, r)$。

你需要计算以下值：

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

其中 $\oplus$ 表示按位异或运算。

输出该求和式对 $998 244 353$ 取模后的值。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 2000$），表示测试用例的数量。对于每个测试用例：

第一行包含三个整数：$n_1$、$n_2$ 和 $m$（$1 \le n_1, n_2 \le 5000$，$1 \le m \le 10^4$），分别表示左部顶点的数量、右部顶点的数量以及边的数量。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u \le n_1$，$1 \le v \le n_2$），描述了一条连接左部顶点 $u$ 和右部顶点 $v$ 的边。

图中没有重边。所有测试用例中 $n_1$ 的总和不超过 $5000$。$n_2$ 的总和也不超过 $5000$。

输出格式

对于每个测试用例，输出一行一个整数，表示所求的求和式对 $998 244 353$ 取模后的值。

样例

输入 1

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

输出 1

81
529
12
81