有一张纸,可以用大小为 $$$n \times m$$$ 的网格表示:$$$n$$$ 行和 $$$m$$$ 列单元格。所有细胞最初都是白色的。
$$$q$$$ 操作已应用于工作表。其中第 $$$i$$$ 可以描述如下:
- $$$x_i$$$ $$$y_i$$$ — 选择 $$$k$$$ 非白色之一,并为整个行 $$$x_i$$$ 和整个列 $$$y_i$$$ 着色。新颜色将应用于每个单元格,无论单元格在操作前是否已着色。
应用所有 $$$q$$$ 操作后的工作表称为着色。如果存在至少一个具有不同颜色的细胞,则两种颜色是不同的。
有多少种不同的颜色?打印以 $$$998\,244\,353$$$ 为模的数字。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
测试用例的第一行包含四个整数 $$$n、m、k$$$ 和 $$$q$$$ ($$$1 \le n, m, k, q \le 2 \cdot 10^5$$$) — 纸张的大小、非白色的数量和操作的数量。
以下 $$$q$$$ 行中的第 $$$i$$$ 行包含第 $$$i$$$ 操作的说明 — 两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le m$$$) — 应用操作的行和列到。
所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 不同颜色的数量以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
2 1 1 3 2 1 1 1 1 2 2 2 3 2 1 1 1 2 2
输出 #1
3 4