#3305. 破坏正方形 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

下图左侧显示了一个用24根火柴棍构成的完整3×3网格。

所有火柴的长度都是1。

您可以在网格中找到许多不同大小的正方形。

在左图所示的网格中,有9个边长为1的正方形,4个边长为2的正方形和1个边长为3的正方形。

组成完整网格的每一根火柴都有唯一编号,该编号从上到下,从左到右,从1开始按顺序分配。

如果你将一些火柴棍从完整网格中取出,形成一个不完整的网格,则一部分正方形将被破坏。

右图为移除编号12,17和23的三个火柴棍后的不完整的3×3网格。

这次移除破坏了5个边长为1的正方形,3个边长为2的正方形和1个边长为3的正方形。

此时,网格不具有边长为3的正方形,但仍然具有4个边长为1的正方形和1个边长为2的正方形。

line

现在给定一个(完整或不完整)的n×n(n不大于5)网格,求至少再去掉多少跟火柴棒,可以使得网格内不再含有任何尺寸的正方形。

输入格式

输入包含T组测试用例。

测试用例的数量T在输入文件的第一行中给出。

每个测试用例由两行组成:

第一行包含一个整数n,表示网格的规模大小。

第二行以非负整数k开头,表示所给网格相较完整的n×n网格所缺少的火柴杆数量,后跟k个整数表示所有缺少的火柴杆的具体编号。

注意,如果k等于零,则表示输入网格是完整的n×n网格。

输出格式

每个测试用例输出一个结果,表示破坏所有正方形,所需的去掉火柴棒的最小数量。

每个结果占一行。

样例

样例输入

2
2
0
3
3 12 17 23

样例输出

3
3

数据范围与提示

POJ 1084