Марія Петрівна працює викладачем в університеті. В середині семестру вона дала своїм студентам контрольну роботу, у якій було \textbf{n} завдань, упорядкованих за зростанням складності. Марія Петрівна знає, що кожен з її студентів відноситься до однієї з трьох категорій: \begin{itemize} \item \textit{Трудолюбивий} студент розв'язує на контрольній задачі у порядку збільшення складності, починаючи з самої легкої, і не пропускаючи жодної задачі, доки не закінчиться час контрольної. \item \textit{Розумний} студент розв'язує на контрольній задачі у порядку зменшення складності, починаючи з самої складної, і не пропускаючи жодної задачі, також доки не завершиться час контрольної. \item \textit{Поганий} студент списує рівно одну задачу у якогось трудолюбивого чи розумного студента. При цьому, два поганих студенти не можуть списати одну і ту же задачу у однієї і тієї ж людини. \end{itemize} Трудолюбиві та розумні студенти завжди правильно розв'язують усі задачі, які встигають. Марія Петрівна дуже не любить студентів, які списують. Тому, якщо вона взнає, що хтось у когось списав, то обом студентам вона цю задачу не зараховує. За результатами контрольної Марія Петрівна внесла у відомість зараховані задачі для кожного студента і для кожної задачі порахувала, скільком студентам вона її зарахувала. Оскільки наближаються екзамени, Марія Петрівна вирішила оцінити число поганих студентів у групі, щоб спланувати час на перездачі. На жаль, вона втратила відомість з зарахованими задачами і зберігла лише листочок, у якому записано для кожної задачі, якому числу студентів ця задача зарахована. Марія Петрівна цікавиться, яке мінімальне число поганих студентів може бути у групі. Допоможіть їй це вияснити. \InputFile Вхідний файл містить декілька тестів. У першому рядку вхідного файла міститься ціле число \textbf{T} --- кількість тестів. Далі йдуть описи тестів. Опис кожного тесту складається з двох рядків. У першому рядку опису задано ціле число \textbf{n} --- кількість завдань у контрольній роботі. Далі для кожного завдання, у порядку зростання складності, вказано число \textbf{a_i} --- кількість студентів, яким зарахована відповідна задача (\textbf{0} ≤ \textbf{a_i} ≤ \textbf{10^9}). Гарантується, що сумарне число завдань у всіх тестах не перевищуєт \textbf{10^5}, а також те, що в контрольній була хоча б одна задача. \OutputFile Для кожного тесту виведіть єдине число --- шукане мінімально можливе число поганих студентів. \textbf{Пояснення до прикладів} В першому тесті у Марії Петрівни могло бути три трудолюбивих студенти, два з яких розв'зали по дві задачі, а один --- лише одну, і ще один розумний студент, який розв'язав саму складну задачу (але нічего більше розв'зати не встиг). У другому тесті у Марії Петрівни міг бути один розумний студент, який зробив дві останніх задачі, чотири трудолюбивих студенти, які розв'зали по дві перші задачі і три поганих студенти, які списали першу задачу, кожен у одного з трудолюбивих студентів. У результаті з семи розв'зків першої задачі шість було анульовано, зарахованим це завдання залишилось лише у трудолюбивого студента, у якого ніхто не списав.