Зменшення Масиву Нассером

Вхідні дані

Перший рядок містить одне ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — кількість тестів.

Перший рядок кожного тесту містить одне ціле число $n$ $(1 \leq n \leq 1 0^{6})$ (1 \le n \le 10^6) — довжина масиву.

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

Гарантується, що сума всіх $n$ по всіх тестах не перевищує $1 0^{6}$ 10^6.

Вихідні дані

Для кожного тесту виведіть одне ціле число — мінімальний можливий розмір масиву після виконання не більше двох операцій.

Приклади

Приклад 1

Loading

Примітка

У другому тесті, $n = 6$ n=6, $a = [1, 2, 2, 1, 5, 5]$ a=[1,2,2,1,5,5]

Операція $1$ : Видалити $[2, 2]$ (позиції $2, 3$ )
Масив стає $[1, 1, 5, 5]$ [1,1,5,5]
Операція $2$ : Видалити $[1, 1]$ (позиції $1, 2$ )
Масив стає $[5, 5]$
Остаточний розмір: $2$

Оцінювання

Підзадача $1$ ( $10$ балів): $(1 \leq \sum n \leq 10)$ (1 \le \sum n \le 10)
Підзадача $2$ ( $15$ балів): $(1 \leq \sum n \leq 50)$ (1 \le \sum n \le 50)
Підзадача $3$ ( $25$ балів): $(1 \leq \sum n \leq 3000)$ (1 \le \sum n \le 3000)
Підзадача $4$ ( $100$ балів): Немає додаткових обмежень.