В один ряд стоят n белых и черных коробок. Коробки пронумерованы слева на право от 1-го до n. Просматривая коробки Барыш раздражается, когда видит белую коробку сразу после черной. Поэтому он просит вас поменять местами коробки во всех последовательных парах {черный, белый}.

За один проход Вы сначала определяете все пары коробок {черный, белый}, а после этого меняете местами коробки во всех найденных парах. После одного прохода в ряду все еще могут оставаться последовательные пары {черный,белый}. В этом случае необходимо повторить описанный процесс.

Сколько проходов нужно совершить, чтобы в ряду не осталось ни одной последовательной пары {черный, белый}?

Входные данные

В первой строке дается число t - количество тестов.

В каждом из следующих далее t тестов, в первой строке дается число n, а во второй n чисел pi.

pi показывает цвет i-ой коробки: pi = 1 черный цвет, а pi = 0 белый цвет.

Выходные данные

Для каждого из тестов в отдельной строке выведите одно число – количество проходов.

Ограничения

• 1 ≤ t ≤ 100
• 1 ≤ n ≤ 104
• pi = 0, 1

Подзадачи

Эта задача состоит из 2-х подзадач: