Well, in this problem you are given an \textbf{R}x\textbf{C} grid (\textbf{1} ≤ \textbf{R} ≤ \textbf{10^9} and \textbf{1} ≤ \textbf{C} ≤ \textbf{10}). There will be \textbf{B} blocks (\textbf{1} ≤ \textbf{B} ≤ \textbf{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 \textbf{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: \begin{enumerate} \item If there is a token in a cell (\textbf{r}, \textbf{c}) then you can move it to either (\textbf{r+1}, \textbf{c-1}) or (\textbf{r+1}, \textbf{c+1}). \item You cannot move a token to a cell occupied by blocks. \item You cannot move a token outside of the grid. \item You cannot move two or more tokens to the same cell. \item All the tokens should be moved to \textbf{i}^\{-th\} row before any token can be moved \textbf{(i + 1)}^\{-th\} row. \end{enumerate} Now let \textbf{S = \{(1},\textbf{ c_1), (1},\textbf{ c_2), ..., (1},\textbf{ c_M))} be the set of cells of where you placed \textbf{M} identical tokens and \textbf{W(S) = number} of ways you can move these tokens to last row. You have to find the sum of \textbf{W} for every possible \textbf{S}. For \textbf{R = 2}, \textbf{C = 2}, \textbf{M = 1} and \textbf{B = 0} the answer is \textbf{2}. \includegraphics{https://static.e-olymp.com/content/7e/7e20e4c513224a295227a8068e57e8631a9181f5.jpg} \InputFile First line contains number of test cases \textbf{1} ≤ \textbf{T} ≤ \textbf{500}. For each test case, the first line contains \textbf{1} ≤ \textbf{R} ≤ \textbf{10^9}, \textbf{1} ≤ \textbf{C} ≤ \textbf{10}and \textbf{0} ≤ \textbf{M} ≤ \textbf{C} respectively. The second line contains \textbf{0} ≤ \textbf{B} ≤ \textbf{100}, followed by \textbf{B} lines and each of those \textbf{B} lines contains two integers \textbf{r} and \textbf{c}, (\textbf{1} ≤ \textbf{r} ≤ \textbf{R} and \textbf{1} ≤ \textbf{c} ≤ \textbf{C}) indicating the cell position of each block. \OutputFile 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 \textbf{12345}.