给定一个 n×n n \times n n×n 的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置 (x,y),(u,v) (x, y),(u, v) (x,y),(u,v) 能互相攻击当前仅当满足以下两个条件：
- x=u x = u x=u 或 y=v y = v y=v
- 对于 (x,y) (x, y) (x,y) 与 (u,v) (u, v) (u,v) 之间的所有位置，均不是障碍。
现在有 q q q 个询问，每个询问给定 ki k_i ki，要求从棋盘中选出 ki k_i ki 个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？