Problem Statement

You are given an N-by-N matrix A=(a_{i,j}), where $a_{i,j} \in$ {0,1}.
We have the following directed graph.

• The graph has NK vertices numbered $1,2,\ldots,NK$.
• The edges correspond to the NK-by-NK matrix X=(x_{i,j}) obtained by arranging K^2 copies of A in K rows and K columns (see Sample Input/Output 1 for an example). If x_{i,j}=1, there is a directed edge from vertex i to vertex j; if x_{i,j}=0, that edge does not exist.

Answer the following question for $i=1,2,\ldots,Q$.

• Find the shortest length (number of edges) of a path from vertex s_i to vertex t_i. If there is no such path, print -1 instead.

Input

The input is given from Standard Input in the following format:
N K
$a_{1,1} \ldots a_{1,N}$
$\vdots$
$a_{N,1} \ldots a_{N,N}$
Q
s_1 t_1
$\vdots$
s_Q t_Q

Output

Print Q lines. The x-th line should contain the answer to the question for i=x.

Constraints

• $1 \leq N \leq 100$
• $1 \leq K \leq 10^9$
• $a_{i,j} \in$ {0,1}
• $1 \leq Q \leq 100$
• $1 \leq s_i,t_i \leq$ NK
• $s_i \neq t_i$
• All values in the input are integers.

Sample Input 1

3 2
1 1 1
1 1 0
0 1 0
4
1 2
1 4
1 6
6 3

Sample Output 1

1
1
1
3

Below is the matrix X representing the edges.
1 1 1 1 1 1
1 1 0 1 1 0
0 1 0 0 1 0
1 1 1 1 1 1
1 1 0 1 1 0
0 1 0 0 1 0

Sample Input 2

4 1000000000
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1
1 4000000000

Sample Output 2

-1

There is no edge.

见题面 Input 部分

见题面 Output 部分