Коробки

В одному ряду розташовані n білих і чорних коробок. Коробки пронумеровані зліва направо від 1 до n. Барыш дратується, коли бачить білу коробку одразу після чорної. Тому він просить вас поміняти місцями коробки у всіх послідовних парах {чорний, білий}.

За один прохід ви спочатку визначаєте всі пари коробок {чорний, білий}, а потім міняєте місцями коробки у всіх знайдених парах. Після одного проходу в ряді все ще можуть залишатися послідовні пари {чорний, білий}. У такому випадку необхідно повторити описаний процес.

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

Вхідні дані

У першому рядку надано кількість тестів t (1 ≤ t ≤ 100).

У кожному з наступних t тестів, у першому рядку надано число n (1 ≤ n ≤ 10^4), а в другому рядку n чисел p[i].

p[i] вказує на колір i-ї коробки: p[i] = 1 означає чорний колір, а p[i] = 0 означає білий колір.

Вихідні дані

Для кожного тесту в окремому рядку виведіть одне число – кількість проходів.

Підзадачі

Це завдання складається з 2 підзадач:

Приклади