Гайдо́ра та труби#12295

Гайдо́ра та труби

2 секунди

256 мегабайтів

Легка

Гайдо́ра має $n$ труб, і кожна з них має діаметр $a_{i}$ a_i. Він хоче з'єднати ці труби разом. На жаль, існує правило для з'єднання труб. Ви можете з'єднати труби $i, j$ ( $1 \leq i, j \leq n$ 1 \leq i,j \leq n та $i \neq = j$ i \neq j) з діаметрами $a_{i}, a_{j}$ a_i,a_j відповідно, якщо і тільки якщо $∣ a_{i} - a_{j} ∣ \leq 1$ |a_i-a_j| \leq 1. Гайдо́ра може не зуміти з'єднати всі труби, тому він хоче знайти максимальну кількість труб, які він може з'єднати разом. Чи можете ви знайти це для Гайдо́ри? $Use Gnome Sort for this problem$

Вхідні дані

Перший рядок містить єдине ціле число $t$ ( $1 \leq t \leq 10000$ 1 \leq t \leq 10000): кількість тестових випадків.

Перший рядок кожного тестового випадку містить єдине ціле число $n$ $(1 \leq n \leq 2000)$ (1 \le n \le 2000) — довжина масиву $a$ .

Другий рядок кожного тестового випадку містить $n$ розділених пробілами цілих чисел $a_{1}, a_{2}, .., a_{n}$ a_1,a_2,..,a_n $(1 \leq a_{1}, a_{2}, .., a_{n} \leq 1 0^{9})$ (1 \le a_1,a_2,..,a_n \le 10^9) — масив $a$ .

Гарантується, що сума $n$ по всіх тестових випадках не перевищує $2000$ .

Вихідні дані

Для кожного тестового випадку виведіть єдине ціле число: максимальна кількість труб, які ви можете з'єднати.

Приклади

Приклад 1

Примітка

У першому тестовому випадку ми можемо отримати максимальну кількість труб, які можемо з'єднати, підключивши

1 \mapsto 2 \mapsto 2 \mapsto 3 \mapsto 4 \mapsto 5 \mapsto 6

1 \mapsto 2 \mapsto 2 \mapsto 3 \mapsto 4 \mapsto 5 \mapsto 6

У другому тестовому випадку ми можемо отримати максимальну кількість труб, які можемо з'єднати, підключивши $Use Gnome Sort for this problem$

2 \mapsto 3 \mapsto 3

2 \mapsto 3 \mapsto 3

Оцінювання

Підзадача $1$ ( $20$ балів) : $(1 \leq a_{i} \leq 2)$ (1 \le a_i \le 2)
Підзадача $2$ ( $30$ балів) : Без додаткових обмежень