#654. Round 2 A

Round 2 A

题目描述

你是一个由n个学生组成的小组的教练。第 ii 名学生具有编程技能 aia_i。所有学生都有不同的编程技能。您希望将他们划分为小组,方法如下:

  • 小组内没有两个学生 iijj 使得 aiaj=1|a_i - a_j| = 1 即 组内任意两名学生的技能之差大于技能差异严格地大于 11
  • 分出来的小组的数量尽可能的少

输入格式

第一行一个 TT (T100)(T \leq 100) 代表有 TT 组测试数据

查询的第一行包含一个整数 nn (n100)(n \leq 100) ,表示每组查询中学生的总数,查询的第二行包含 nn 个整数 a1a2.....a_1 a_2..... (1ai1001 \leq a_i \leq 100,所有的 aia_i 都是不同的),其中aia_i 是第 ii 个学生的编程技能。

输出格式

对于每个查询输出一个答案,代表 nn 名学生最少分成多少组才能满足上述分组条件

样例

样例输入:

4
4
2 10 1 20
2
3 6
5
2 3 4 99 100
1
42

样例输出

2
1
2
1

数据范围与提示

在示例的第一个查询中,有 n=4n = 4 个学生具有技能 a=[210120]a=[2,10,1,20] 。这里只有一个限制:第 11 名和第 33 名学生不能在同一个团队中(因为a1a3=21=1|a_1 − a_3| = |2−1| = 1)。可以将他们分成两个小组:例如,学生 121,244 在第一队,学生 33 在第二队。