Степан судить гру під назвою «Зламаний телефон». Всього в грі беруть участь \(N\) гравців. Вони всі сидять шеренгою. На початку гри перший гравець отримує секретне повідомлення, написане на аркуші паперу. Потім вони продовжують надсилати повідомлення, шепочучи його гравцеві, який сидить безпосередньо біля нього, і так далі, поки воно не дійде до останньої людини. Нарешті, повідомлення, отримане останнім гравцем, порівнюється з повідомленням, сказаним першим гравцем. Якщо ці повідомлення не однакові, це означає, що хтось неправильно почув повідомлення або неправильно прошепотів його наступному гравцеві. Якщо кількість повідомлень рівна, то гравці виграють і отримують смачний шоколад. Зверніть увагу, що перший гравець отримує повідомлення на аркуші паперу, тому він не може його неправильно зрозуміти. Оскільки Степан хоче бути впевненим, що кожен гравець виконав свою роль у грі, тому він просить усіх озвучити отримані повідомлення після закінчення гри.

Вам надано масив \(A\) з \(N\) цілих чисел, що позначають повідомлення, отримані кожною особою. Будь ласка, допоможіть Степану знайти кількість гравців, які могли неправильно почути повідомлення або прошепотіти його неправильно.

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

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

Перший рядок тесту містить ціле число \(N\).

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

Числа у рядках розділяються пропуском.

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

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

Обмеження

• 1 ≤ T ≤ 5

• 1 ≤ \(A_i\) ≤ \(10^9\)

• 2 ≤ N ≤ \(10^5\)

Примітка

До тесту 1:

3-й, 4-й, 6-й і 7-й гравці могли неправильно зрозуміти повідомлення або прошепотіти його неправильно.

До тесту 2:

Перші 3 гравці могли неправильно розчути повідомлення або прошепотіти його неправильно.

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

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

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

4
3
0