CF1644D Cross Coloring

There is a sheet of paper that can be represented with a grid of size $ n \times m $ : $ n $ rows and $ m $ columns of cells. All cells are colored in white initially. $ q $ operations have been applied to the sheet. The $ i $ -th of them can be described as follows: - $ x_i $ $ y_i $ — choose one of $ k $ non-white colors and color the entire row $ x_i $ and the entire column $ y_i $ in it. The new color is applied to each cell, regardless of whether the cell was colored before the operation. The sheet after applying all $ q $ operations is called a coloring. Two colorings are different if there exists at least one cell that is colored in different colors. How many different colorings are there? Print the number modulo $ 998\,244\,353 $ .

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of the testcase contains four integers $ n, m, k $ and $ q $ ( $ 1 \le n, m, k, q \le 2 \cdot 10^5 $ ) — the size of the sheet, the number of non-white colors and the number of operations. The $ i $ -th of the following $ q $ lines contains a description of the $ i $ -th operation — two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i \le n $ ; $ 1 \le y_i \le m $ ) — the row and the column the operation is applied to. The sum of $ q $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

For each testcase, print a single integer — the number of different colorings modulo $ 998\,244\,353 $ .