Configurations

Well, in this problem you are given an RxC grid (1 ≤ R ≤ 10^9 and 1 ≤ C ≤ 10). There will be B blocks (1 ≤ B ≤ 100) in the grid. Each block will be placed in a cell of the grid. There can be more than one blocks in a cell.

Now you are given M identical tokens and you can place them in the first row as you like. A cell cannot contain more than one token and you also cannot place a token in a cell occupied by blocks. Now you can move a token but you have to follow following rules:

1. If there is a token in a cell (r, c) then you can move it to either (r+1, c-1) or (r+1, c+1).

2. You cannot move a token to a cell occupied by blocks.

3. You cannot move a token outside of the grid.

4. You cannot move two or more tokens to the same cell.

5. All the tokens should be moved to i^{-th} row before any token can be moved (i + 1)^{-th} row.

Now let S = {(1, c_1), (1, c_2), ..., (1, c_M)) be the set of cells of where you placed M identical tokens and W(S) = number of ways you can move these tokens to last row. You have to find the sum of W for every possible S.

For R = 2, C = 2, M = 1 and B = 0 the answer is 2.

Input

First line contains number of test cases 1 ≤ T ≤ 500. For each test case, the first line contains 1 ≤ R ≤ 10^9, 1 ≤ C ≤ 10and 0 ≤ M ≤ C respectively. The second line contains 0 ≤ B ≤ 100, followed by B lines and each of those B lines contains two integers r and c, (1 ≤ r ≤ R and 1 ≤ c ≤ C) indicating the cell position of each block.

Output

For each test case you have to output the answer in a single line as shown in the sample output. As the answer can be very large you have to mod the output with 12345.

Examples