Симетричні візерунки

У місцях імовірної посадки іншопланетних космічних кораблів іноді знахо­дять симетричні візерунки, відомі як "кола на полях". Інколи такі візерунки підробляють жартівники. Звичайно, люди не можуть досягти того рівня симетрії, який мають справжні "кола на полях". Тому підробку можна викрити. На одному полі було помічено два візерунки. Для перевірки їхньої справжності ці візерунки сфотографували. На знімку через центри візерунків провели пряму, а на цій прямій відмітили точки, що належать візерункам. Достеменно не відомо, які точки належать якому візерунку. Але можна бути певним, що на проведеній прямій усі точки одного візерунка лежать по один бік від усіх точок іншого візерунка.

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

Вхідні дані

У першому рядку вхідного файлу вказана кількість тестів T, яка дорівнює 1 або 2. Кожен тест описаний у окремому рядку. На початку кожного рядка стоїть ціле число N (1 ≤ N ≤ 100000) — кількість точок на прямій для даного тесту. Далі йдуть N різних цілих чисел x_1, x_2, ..., x_N — координати точок на прямій.

Відомо, що 0 ≤ x_1 < x_2 < ... < x_N ≤ 2·10^9. Числа у рядку розділено пропусками.

Вихідні дані

Для кожного з T тестів виведіть відповідь в окремому рядку. Якщо в даному тесті множину точок можна розбити на дві непорожні симетричні множини так, що всі точки однієї множини лежать по один бік від усіх точок іншої, виведіть кількість точок у множині з меншими координатами. Якщо можливі кілька відповідей, виведіть найменшу натуральну з можливих. Якщо розбиття не існує, виведіть 0.

Приклади