When Alice is given a binary m x n matrix (a matrix with 0s and 1s with m rows and n columns), she tries to make it all zero using 2x2 flip operation. In this operation, she selects a 2x2 sub-matrix and flips the digits in it from 0 to 1 or 1 to 0.

Now it’s none other than Bob who gives Alice the matrix to make it zero. However, Bob is not as smart as Alice, so the matrix Bob hands over to Alice might not be one that can be converted to all zeros using the 2x2 flip operations. So Alice is also permitted to perform at most K additional 1x1 flip operations before she performs the 2x2 operations. She can flip a certain 1x1 cell as many times as she wishes (as long as the total number of 1x1 flip is at most K).

For a given matrix, find the number of ways Alice can perform 1x1 flip operation at most K times so that after these operations she can make the entire matrix zero using 2x2 flip operations. Two sequences of flipping are different if they are of different length or the i’th cell in one sequence is different from the other sequence.

For example, for the following matrix:

$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{bmatrix}$$

Alice could not convert the initial matrix to zero using only 2x2 flips. But she can do the following:

Input begins with the number of test cases T. Each case begins with 4 integers: m, n, K, b. Here, b is the number of 1s in the matrix. Then follow b pairs of integers: r_i, c_i, denoting the places of 1s.

Constraints

• 1 ≤ T ≤ 150
• Across all test cases
  • Sum of n, Sum of m ≤ 1,000,000
  • Sum of K ≤ 10,000
  • Sum of b ≤ 100,000
• 1 ≤ n, m ≤ 1,000,000
• 0 ≤ K ≤ 10,000
• 0 ≤ b ≤ mn
• 1 ≤ ri ≤ m, 1 ≤ ci ≤ n
• (r_i, c_i) are unique.

Output case number followed by the answer. Since the number can be big, output the answer in modulo 998244353.