% Origin: Зимняя олимпиада по информатике, Болгария, Велико Тарново
% 10-11 февраля 2012 года
% Группа A, 11-12 класс
% Автор: Стоян Капралов
\begin{problem}{Ход конём}
{\textsl{стандартный ввод}}{\textsl{стандартный вывод}}
{2 секунды}{256 мебибайт}{}

Дана прямоугольная доска, состоящая из $m$ строк и $n$ столбцов.
Клетки пронумерованы целыми числами от $1$ до $m \cdot n$: клетки
первой строки пронумерованы от $1$ до $n$ слева направо, клетки второй "---
номера от $n + 1$ до $2 n$ слева направо, и так далее.

Сколько существует способов попасть из клетки $x$ в клетку $y$,
сделав ровно $k$ ходов шахматного коня?
Выходить за пределы доски не разрешается.

\InputFile

В первой строке входного файла заданы через пробел три целых числа
$m$, $n$ и $k$: размеры доски и требуемое количество ходов
($3 \le m \le 10$, $3 \le n \le 10$, $1 \le k \le 1000$).
Во второй строке задано целое число $t$ "--- количество пар клеток,
для которых необходимо решить задачу ($1 \le t \le 10$).
В каждой из следующих $t$ строк содержится по два числа через пробел:
номера начальной и конечной клетки,
($1 \le x \le m \cdot n$, $1 \le y \le m \cdot n$).

\OutputFile

Для каждого теста выведите на отдельной строке количество способов
попасть из клетки $x$ в клетку $y$.
Поскольку это число может быть очень большим,
выведите остаток от деления его на $10\,000$.

\Examples

\begin{example}%
\exmp{
3 7 5
4
2 17
8 21
3 8
4 16
}{
49
21
48
0
}%
\exmp{
7 3 5
4
2 17
8 21
3 8
4 16
}{
22
19
37
0
}%
\end{example}

\Explanations

Далее представлена нумерация клеток на доске $3 \times 7$
и на доске $7 \times 3$, а также возможные ходы коня,
стоящего в центре доски $5 \times 5$.

\begin{center}
\begin{tabular}{c c c}
\begin{minipage}{0.5\thelinewidth}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
 1 &  2 &  3 &  4 &  5 &  6 &  7 \\
\hline
 8 &  9 & 10 & 11 & 12 & 13 & 14 \\
\hline
15 & 16 & 17 & 18 & 19 & 20 & 21 \\
\hline
\end{tabular}
\end{minipage}
&
\begin{minipage}{0.18\thelinewidth}
\begin{tabular}{|c|c|c|}
\hline
 1 &  2 &  3 \\
\hline
 4 &  5 &  6 \\
\hline
 7 &  8 &  9 \\
\hline
10 & 11 & 12 \\
\hline
13 & 14 & 15 \\
\hline
16 & 17 & 18 \\
\hline
19 & 20 & 21 \\
\hline
\end{tabular}
\end{minipage}
&
\begin{minipage}{0.3\thelinewidth}
\begin{tabular}{|c|c|c|c|c|}
\hline
~ & x & ~ & x & ~ \\
\hline
x & ~ & ~ & ~ & x \\
\hline
~ & ~ & K & ~ & ~ \\
\hline
x & ~ & ~ & ~ & x \\
\hline
~ & x & ~ & x & ~ \\
\hline
\end{tabular}
\end{minipage}
\\
\end{tabular}
\end{center}

\end{problem}
