Problem Statement

You are given positive integers $N, K$, and an $N \times N$ matrix $C=(C_{i,j})$ $(1\leq i,j\leq N)$. It is guaranteed that $C_{i,i} = 0$ and $C_{i,j} = C_{j,i}$.

There is a weighted complete graph with $N$ vertices labeled $1,2,\dots,N$. For each pair of vertices $i$ and $j$ with $i\lt j$, the weight of the edge connecting vertices $i$ and $j$ is $C_{i,j}$.

You have $Q$ queries. In the $i$-th query, you are given a pair of distinct integers $s_i$ and $t_i$ (both between $K+1$ and $N$, inclusive), for which you must solve the following problem.

A good graph is a connected graph containing all of the vertices $1,2,\dots,K,s_i,t_i$ obtained by removing any number of edges and vertices (possibly zero) from the graph above.

The cost of a good graph is the sum of the weights of its edges.

Find the minimum possible cost of a good graph.

Constraints

• $3 \leq N \leq 80$
• $1\leq K\leq \min(N-2,\textcolor{red}{8})$
• $0 \leq C_{i,j} \leq 10^9 \ (1 \leq i,j \leq N, i \ne j)$
• $C_{i,j} = C_{j,i} \ (1 \leq i,j \leq N, i \ne j)$
• $C_{i,i} = 0 \ (1 \leq i \leq N)$
• $1 \leq Q \leq 5000$
• $K+1 \leq s_i, t_i \leq N \ (1 \leq i \leq Q)$
• $s_i \ne t_i \ (1 \leq i \leq Q)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
C_{1,1} C_{1,2} \dots C_{1,N}
C_{2,1} C_{2,2} \dots C_{2,N}
\vdots
C_{N,1} C_{N,2} \dots C_{N,N}
Q
s_1 t_1
s_2 t_2
\vdots
s_Q t_Q

Output

Print $Q$ lines.

The $i$-th line should contain the answer for the $i$-th query.