100%的数据，N<=50，T<=25

 真坑啊。。被数据范围骗了。。差点写了深搜。

然而事实是：

对于任意一个点A，这个地方放上皇后，A所能覆盖的点放上皇后也能覆盖A。

而A覆盖不了的点放上皇后怎么也覆盖不了A。

所以最优的方案就是，先在这些覆盖不了的点上全都放上皇后，最后就会只剩一个A没有覆盖，再怎么放A都要被覆盖了。

如下图

对于任意的A，红圈再加上随便一个位置就是要放的地方。

可以证明这个A取四个角的时候不能覆盖点最多。即答案最大。

所以答案就是n*n-n*3+3了。

代码简直智障。

1 #include<cstdio>
2 int main(){
3     int t;scanf("%d",&t);
4     while(t--){
5         int n;scanf("%d",&n);
6         printf("%d\n",n*(n-3)+3);
7     }
8 }

 写这个题解主要是网上没有，怕这破题坑人啊哈