C. Левые и правые дома
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В деревне Летово есть $$$n$$$ домов. Жители деревни решили построить большую дорогу, которая разделит деревню на левую и правую стороны. Житель каждого дома хочет жить либо на правой, либо на левой стороне улицы. Можно описать предпочтения в виде последовательности $$$a_1, a_2, \dots, a_n$$$, где $$$a_j = 0$$$, если житель $$$j$$$-го дома хочет жить на левой стороне улицы, иначе $$$a_j = 1$$$.

Дорога будет проходить между двумя домами, и дома слева от нее будут левыми, дома справа — правыми. Более формально, пусть дорога проходит между домами $$$i$$$ и $$$i+1$$$. Тогда дома на позициях от $$$1$$$ до $$$i$$$ будут на левой стороне улицы, а на позициях $$$i+1$$$ до $$$n$$$ на правой стороне. Дорога также может проходить перед первым или после последнего дома, в таком случае вся деревня объявляется правой или левой стороной соответственно.

Чтобы всё было честно, было решено спроектировать дорогу так, чтобы не менее половины жителей каждой из сторон деревни в отдельности остались довольны выбором. То есть среди $$$x$$$ жителей одной стороны, хотя бы $$$\lceil\frac{x}{2}\rceil$$$ должны хотеть жить именно на этой стороне, где $$$\lceil x \rceil$$$ означает округление вверх вещественного числа $$$x$$$.

Слева от дороги будет $$$i$$$ домов, среди соответствующих $$$a_j$$$ должно быть не меньше $$$\lceil\frac{i}{2}\rceil$$$ нулей. Справа от дороги будет $$$n-i$$$ домов, среди соответствующих $$$a_j$$$ должно быть не меньше $$$\lceil\frac{n-i}{2}\rceil$$$ единиц.

Определите, после какого дома $$$i$$$ стоит проложить дорогу, чтобы выполнялось описанное условие и она была как можно ближе к середине деревни. Формально, среди всех подходящих позиций $$$i$$$ минимизируйте $$$\left|\frac{n}{2} - i\right|$$$.

Если подходящих позиций $$$i$$$ с минимальным $$$\left|\frac{n}{2} - i\right|$$$ несколько, выведите меньшую из них.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

Первая строка каждого набора входных данных содержит одно число $$$n$$$ ($$$3 \le n \le 3\cdot 10^5$$$) — количество домов.

Следующая строка входных данных состоит из строки $$$a$$$ из $$$n$$$ символов, каждый символ равен либо $$$0$$$, либо $$$1$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$.

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

Для каждого набора входных данных, выведите одно число $$$i$$$ — позицию такого дома, после которого надо проложить дорогу (если ее надо проложить перед первым домом, выведите $$$0$$$). Можно показать, что ответ всегда существует.

Пример
Входные данные
7
3
101
6
010111
6
011001
3
000
3
110
3
001
4
1100
Выходные данные
2
3
2
3
0
1
0
Примечание

Рассмотрим первый пример входных данных.

Если проложить дорогу после первого дома, на левой стороне улицы будет расположен один дом $$$a_1 = 1$$$, житель которого хотел бы жить на правой стороне улицы. Тогда $$$0$$$ из $$$1$$$ жителей левой стороны останутся довольны выбором, значит, после дома $$$1$$$ дорогу проложить нельзя.

Если проложить дорогу после второго дома, $$$1$$$ из $$$2$$$ жителей левой стороны (с пожеланиями $$$a_1 = 1$$$, $$$a_2 = 0$$$) и $$$1$$$ из $$$1$$$ жителя правой стороны (с пожеланием $$$a_3 = 1$$$) останутся довольны выбором. Более половины жителей каждой стороны довольны выбором, значит, после дома $$$2$$$ дорогу проложить разрешено. Можно показать, что это оптимальный ответ.