D. Cross Coloringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere 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.InputThe 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.OutputFor each testcase, print a single integer — the number of different colorings modulo 998\,244\,353.ExampleInput
2
1 1 3 2
1 1
1 1
2 2 2 3
2 1
1 1
2 2
Output
3
4

2
1 1 3 2
1 1
1 1
2 2 2 3
2 1
1 1
2 2

3 4 
['data structures', 'implementation', 'math', '*1700']