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

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

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

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

В первой строке дается количество тестов t (1 ≤ t ≤ 100).

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

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

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

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

Подзадачи

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