Степан записав відео, в якому пояснив розв'язок задачі. Однак розмір відео завеликий для завантаження в Інтернет. Він хоче стиснути відео, щоб воно мало мінімальний можливий розмір.

Відео Степана спочатку має \(N\) кадрів. Значення \(i\)-го кадру - \(A_i\)​. Степан може виконувати такі операції будь-яку кількість разів:

• Вибрати індекс  \(i\) (\(1 \le i \le N\)), щоб значення \(i\)-го кадру дорівнює значенню будь-якого з його сусідів і видаляє \(i\)-й кадр.

Знайдіть мінімальну кількість кадрів, яку залишить Степан.

Формат вхідних даних

Перший рядок містить ціле число \(T\) (\(1 \le T \le 1000\)) - кількість тестів.

Перший рядок тесту містить ціле число \(N\) (\(1 \le N \le 10^5\))

Наступний рядок тесту містить \(N\) цілих чисел \(A_i\) (\(1 \le A_i \le 10^6\))

Сума \(N\) за всіма тестами не перевищує \(2 \cdot 10^5\).

Формат вихідних даних

У вихідний потік вивести для кожного тесту в окремому рядку мінімальну кількість кадрів, яку залишить Степан.

Приклад вхідних даних

4
1
5
2
1 1
3
1 2 3
4
2 1 2 2

Приклад вихідних даних

1
1
3
3