给定一个 n×n n \times n n×n 的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置 (x,y),(u,v) (x, y),(u, v) (x,y),(u,v) 能互相攻击当前仅当满足以下两个条件：
现在有 q q q 个询问，每个询问给定 ki k_i ki，要求从棋盘中选出 ki k_i ki 个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？
第一行一个整数 n n n。接下来输入一个 n×n n \times n n×n 的字符矩阵，一个位置若为 .，则表示这是一个空位置，若为 #，则为障碍。第 n+2 n + 2 n+2 行输入一个整数 q q q 代表询问个数。接下来 q q q 行，每行一个整数 k k k，代表要放的棋子个数。
.
#
输出共 q q q 行，每行代表对应询问的最少的互相能攻击到的棋子对数。
4 ..#. #### ..#. ..#. 1 7
2
对于 20% 20\% 20% 的数据，n≤5 n \leq 5 n≤5；对于 40% 40\% 40% 的数据，n≤10 n \leq 10 n≤10；另外有 20% 20\% 20% 的数据，q=1 q = 1 q=1；对于 100% 100\% 100% 的数据，n≤50;q≤10000;k≤ n \leq 50; q \leq 10000; k \leq n≤50;q≤10000;k≤ 棋盘中空位置数量。