Mariya Petrovna Universitetdə müəllim işləyir. Semestr ortasında o tələbələrinə çətinlik dərəcəsinə görə artan ardıcıllıqda sıralanmış \textbf{n} məsələdən ibarət yoxlama yazı işi verdi. Mariya Petrovna bilir ki, onun tələbələrindən hər biri üç kateqoriyadan birinə aiddir: \begin{itemize} \item \textit{Zəhmətkeş} tələbə yoxlama işində məsələləri ən sadədən başlayaraq və yoxlama işinə ayrılmış vaxt sona çatana qədər heç bir məsələni buraxmadan çətinlik dərəcəsinin artma ardıcıllığında həll edir. \item \textit{Ağıllı} tələbə yoxlama işində məsələləri ən çətindən başlayaraq və yoxlama işinə ayrılmış vaxt sona çatana qədər heç bir məsələni buraxmadan çətinlik dərəcəsinin azalma ardıcıllığında həll edir. \item \textit{Pis} tələbə hər hansı bir zəhmətkeş və ya ağıllı tələbədən yalnız bir məsələni köçürür. Bu zaman iki pis tələbə eyni bir məsələni eyni bir tələbədən köçürə bilməz. \end{itemize} Zəhmətkeş və ağıllı tələbələr çatdıra bildikləri bütün məsələləri həmişə doğru həll edirlər. Mariya Petrovna köçürən tələbələri heç sevmir. Buna görə də o, əgər bilsə ki, kim isə kimdən isə köçürürsə, hər iki tələbənin bu məsələlərini hesaba almır. Yoxlama işinin nəticələrinə görə Mariya Petrovna hər bir tələbə üçün cədvələ yoxlanılmış qiymətləri daxil etdi və hər bir məsələ üçün bu məsələnin neçə tələbə üçün qəbul etdiyini hesabladı. Belə ki, imtahanlar yaxınlaşır, Mariya Petrovna imtahanın yenidən verilməsi vaxtını planlaşdırmaq üçün qrupdakı pis tələbələrin sayını qiymətləndirmək qərarına gəldi. Təəssüf ki, o qiymətlərin yazıldığı cədvəli itirmişdir və hər bir məsələ üçün bu məsələnin neçə tələbə üçün qəbul edildiyi qeyd edilmiş vərəqi saxlamışdır. Mariya Petrovna qrupda ola biləcək pis tələbələrin minimal sayını bilmək istəyir. Bunu müəyyənləşdirməkdə ona kömək edin. \InputFile Giriş faylı bir neçə testi ehtiva edir. Giriş faylının ilk sətrində testlərin sayını ehtiva edən \textbf{T} tam ədədi verilir. Sonra testlərin təsviri verilir. Hər bir testin təsviri iki sətirdən ibarətdir. Təsvirin birinci sətrində yoxlama işindəki məsələlərin sayını ifadə edən \textbf{n} tam ədədi verilir. Sonra isə hər bir məslə üçün mürəkkəblik dərəcəsinə görə artma ardıcıllığında uyğun məsələnin qəbil edildiyi tələbələrin sayını ifadə edən \textbf{a_i} (\textbf{0} ≤ \textbf{a_i} ≤ \textbf{10^9}) ədədi verilir. Bütün testlərdəki, məsələlərin ümumi sayının \textbf{10^5}-i aşmadığına, həmçinin, yoxlama işində heç olmazsa bir məsələnin olduğuna zəmanət verilir. \OutputFile Hər bir test üçün pis tələbələrin mümkün cari minimal sayını ifadə edən yeganə ədədi verin. \textbf{Misalın şərhi} Birinci testdə Mariya Petrovnanın üç zəhmətkeş tələbəsi ola bilər ki, onlardan da ikisinin hər biri iki məsələ həll etmişdilər, biri isə yalnız bir məsələni həll etmişdir, daha bir ağıllı tələbə isə ən mürəkkəb məsələni həll etmişdir (lakin bundan başqa məsələ həll edə bilməmişdir). İkinci testdə Mariya Perovnanın son iki məsələni həll etmiş bir ağıllı tələbəsi, hər biri ilk iki məsələni həll etmiş dörd zəhmətkeş tələbəsi və hər bir zəhmətkeş tələbədən birinci məsələni köçürmüş üç pis tələbəsi ola bilər. Nəticədə birinci məsələnin yeddi həllindən altısı ləğv edilmiş, bu məsələ yalnız o zəhmətkeş tələbə üçün qəbul edilmişdir ki, ondan heç kim köçürməmişdir.