statement.md

問題文

あなたはW国を訪問する計画を立てています。 W国は $N × N$ のグリッド $A$ で表され、上から $r$ 行目、左から $c$ 列目のマス目は $A_{(r,c)}$ と表されます。 $A_{(r,c)}$ には '#' , '.' のいずれかの文字が書かれています。

あなたは観光中に拠点とする場所を一つ決め、 $Q$ 個の場所 $A_{(r_1,c_1)},A_{(r_2,c_2)}, \ldots , A_{(r_Q,c_Q)}$ を訪れたいと思っています。 拠点とする場所を $A_{(s_r,s_c)}$ としたとき、観光に必要な費用は以下の様に定義されます。

• $\displaystyle \sum_{i=1}^{Q} dist(A_{(s_r,s_c)},A_{(r_i,c_i)})$

ここで $dist(A_{(a_r,a_c)},A_{(b_r,b_c)})$ は、場所 $A_{(a_r,a_c)}$ から場所 $A_{(b_r,b_c)}$ へ到達するために必要な移動回数の最小値を表します。

あなたは、一回の移動で '.' が書かれた上下左右のマスに移動することができます。
また、あなたは '.' が書かれたマスを一つ選び、拠点とすることができます。 観光に必要な費用の最小値を求めてください。

制約

共通

• 入力で与えられる数は全て整数
• $A_{(r,c)}=$ '#' または '.'
• ${{LARGE_MIN_Q}} \leq Q \leq \min({{LARGE_MAX_Q}},N^2)$
• $1 \leq r_i, c_i \leq N$
• $A_{(r_i,c_i)} =$ '.'
• $r_i \neq r_j$ または $c_i \neq c_j$ $(i \neq j)$
• 辺を共有する '.' が書かれたマスの間の移動を繰り返すことで、任意の '.'が書かれたマスから別の'.'が書かれたマスへ到達することができる。

Small

• $T = {{SMALL_T}}$
• $1 \leq N \leq 10$

large

• $T = {{LARGE_T}}$
• はじめの3ケースについては ${{LARGE_MIN_N}} \leq N \leq {{LARGE_MAX_N}}$ を満たします。
• 残りのケースについては ${{LARGE_MIN_N}} \leq N \leq {{LARGE_MED_N}}$ を満たします。

入力

1 つの入力ファイルは複数のテストケースからなります。 入力ファイルの最初の一行目にはテストケースの個数 $T$ が記されます。 2行目以降には、$T$ 個のテストケースが記述されており、各テストケースは次の形式で表されます。

$N$  
$A_{(1,1)}$ $A_{(1,2)}$ $\ldots$ $A_{(1,N)}$  
$A_{(2,1)}$ $A_{(2,2)}$ $\ldots$ $A_{(2,N)}$  
$\vdots$  
$A_{(N,1)}$ $A_{(N,2)}$ $\ldots$ $A_{(N,N)}$  
$Q$  
$r_1$ $c_1$  
$r_2$ $c_2$  
$\vdots$  
$r_Q$ $c_Q$  

出力

答えを1行に出力してください。

{{sample}}

拠点として最適な街は $A_{(2,1)},,A_{(2,2)},,A_{(3,2)},,A_{(4,1)},,A_{(4,2)}$ の5つであり、このとき必要な費用は4となります。
訪れたい地点を拠点とすることも可能な点に注意してください。