题目描述

给定一个 $ n \times n $ 的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置 $ (x, y),(u, v) $ 能互相攻击当前仅当满足以下两个条件：

• $ x = u $ 或 $ y = v $
• 对于 $ (x, y) $ 与 $ (u, v) $ 之间的所有位置，均不是障碍。

现在有 $ q $ 个询问，每个询问给定 $ k_i $，要求从棋盘中选出 $ k_i $ 个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？

输入格式

第一行一个整数 $ n $。
接下来输入一个 $ n \times n $ 的字符矩阵，一个位置若为 .，则表示这是一个空位置，若为 #，则为障碍。
第 $ n + 2 $ 行输入一个整数 $ q $ 代表询问个数。
接下来 $ q $ 行，每行一个整数 $ k $，代表要放的棋子个数。

输出格式

输出共 $ q $ 行，每行代表对应询问的最少的互相能攻击到的棋子对数。

样例

input

4
..#.
####
..#.
..#.
1
7

output

2

数据范围与提示

对于 $ 20\% $ 的数据，$ n \leq 5 $；
对于 $ 40\% $ 的数据，$ n \leq 10 $；
另外有 $ 20\% $ 的数据，$ q = 1 $；
对于 $ 100\% $ 的数据，$ n \leq 50; q \leq 10000; k \leq $ 棋盘中空位置数量。