You have to color an M x N two dimensional grid. You will be provided K different colors for this. You will also be provided a list of B blocked cells of this grid. You cannot color these blocked cells.

A cell can be described as (x, y), which points to the y^th cell from the left of the x^th row from the top.

While coloring the grid, you have to follow these rules:

1. You have to color each cell which is not blocked.
2. You cannot color a blocked cell.
3. You can choose exactly one color from K given colors to color a cell.
4. No two vertically adjacent cells can have the same color, i.e. cell (x, y) and cell (x + 1, y) shouldn't contain the same color.

You have to calculate the numbe of ways you can color this grid obeying all the rules provided.

Input starts with an integer T (≤ 600), denoting the number of test cases.

Each test case starts with a line containing four integers M N K B (1 ≤ M, N, K ≤ 10⁶, 0 ≤ B ≤ 500). Each of the next B lines will contain two integers x and y (1 ≤ x ≤ M, 1 ≤ y ≤ N), the row and column number of a blocked cell. Each of these B lines will contain distinct cells.

For each case, print the case number and the number of ways to color the grid modulo 10⁹.