输入描述:

输入包含多组数据，第一行一个整数 ，表示数据组数，接下来  组数据，对于每组数据：

第一行两个整数 ，表示棋盘边长以及棋盘上的棋子数。

接下来  行，第  行一个长为  的字符串 ， 为 '#' 表示改位置上放有一枚棋子，为 '.' 表示该位置上没有棋子。

输出描述:

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