A13048 | $Yet Another Dividing into Teams$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You are a coach of a group consisting of $n$ students. The $i$ -th student has programming skill $a_i$ . All students have distinct programming skills. You want to divide them into teams in such a way that: - No two students $i$ and $j$ such that $|a_i - a_j| = 1$ belong to the same team (i.e. skills of each pair of students in the same team have the difference strictly greater than $1$ ); - the number of teams is the minimum possible. You have to answer $q$ independent queries.

The first line of the input contains one integer $q$ ( $1 \le q \le 100$ ) — the number of queries. Then $q$ queries follow. The first line of the query contains one integer $n$ ( $1 \le n \le 100$ ) — the number of students in the query. The second line of the query contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 100$ , all $a_i$ are distinct), where $a_i$ is the programming skill of the $i$ -th student.

For each query, print the answer on it — the minimum number of teams you can form if no two students $i$ and $j$ such that $|a_i - a_j| = 1$ may belong to the same team (i.e. skills of each pair of students in the same team has the difference strictly greater than $1$ )

输入 #1

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

输出 #1

C++ 编辑器

输入

输出