问题描述

Ivan 和 Joan 刚刚下完了一盘棋，现在他们要整理棋盘。在这张 $n\times n$ 的棋盘上共有 $m$ 枚棋子，Ivan 和 Joan 可以执行若干次操作，每次操作可以选择一枚棋子，将其向上/下/左/右移动一格，即：整理好这些棋子需要将所有棋子全部移动到位于边界的方格上，Ivan 和 Joan 想知道他们最少需要操作几次，才能整理好棋盘。

输入

输入包含多组数据，第一行一个整数 $t(1\le t\le 5)$，表示数据组数，接下来 $t$ 组数据，对于每组数据：

第一行两个整数 $n(1\le n\le 200),\ m(0\le m\le n^2)$，表示棋盘边长以及棋盘上的棋子数。

接下来 $n$ 行，第 $i$ 行一个长为 $n$ 的字符串 $s_i$，$s_{i,j}$ 为 '#' 表示改位置上放有一枚棋子，为 '.' 表示该位置上没有棋子。

输出

对于每组数据，输出一个整数表示最少操作次数，如果不能整理好棋盘，输出 $-1$。

3
3 8
##.
###
###
4 16
####
####
####
####
2 0
..
..

2
-1
0