您是由 $$$n$$$ 学生组成的团体的教练。第 $$$i$$$ 个学生具有编程技能 $$$a_i$$$。所有学生都有独特的编程技能。您希望通过以下方式将他们分成团队:
- 没有两个学生 $$$i$$$ 和 $$$j$$$ 使得 $$$|a_i - a_j| = 1$$$ 属于同一团队(即同一团队中每对学生的技能差异严格大于$$$1$$$);
- 团队数量是尽可能少的。
您必须回答 $$$q$$$ 独立查询。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 100$$$) — 查询数。然后是 $$$q$$$ 查询。
查询的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 查询中的学生人数。查询的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$,所有 $$$a_i$$$ 都是不同的),其中 $$$a_i$$$ 是第 $$$i$$$ 个学生的编程技能。
输出
对于每个查询,请在其上打印答案 - 如果没有两个学生 $$$i$$$ 和 $$$j$$$ 使得 $$$|a_i - a_j| 成立,则可以组建的最小团队数量= 1$$$ 可能属于同一团队(即同一团队中每对学生的技能差异严格大于$$$1$$$)
示例
输入 #1
4 4 2 10 1 20 2 3 6 5 2 3 4 99 100 1 42
输出 #1
2 1 2 1
注意
在示例的第一个查询中,有 $$$n=4$$$ 名学生,其技能为 $$$a=[2, 10, 1, 20]$$$。这里只有一个限制:第 $$$1$$$-st 和第 $$$3$$$-th 学生不能在同一个团队中(因为 $$$|a_1 - a_3|=|2-1|=1$$$)。可以将他们分成 $$$2$$$ 队:例如,学生 $$$1$$$、$$$2$$$ 和 $$$4$$$ 属于第一队,学生 $$$3$$$ 属于第二队。
在示例的第二个查询中,有 $$$n=2$$$ 名学生具有技能 $$$a=[3, 6]$$$。可以只组成一个由两名学生组成的团队。