Сувлакити и Каламакити снова играют в игру.
Все целые числа от $$$1$$$ до $$$n$$$ распределены между игроками. Это распределение можно представить в виде бинарной строки $$$s$$$ длины $$$n$$$, где $$$s_i = 1$$$, если целое число $$$i$$$ досталось Сувлакити, и $$$s_i = 0$$$, если оно досталось Каламакити. Гарантируется, что изначально у Сувлакити есть хотя бы одно целое число (существует хотя бы один символ $$$1$$$ в $$$s$$$).
Игра продлится $$$10^{100}$$$ ходов. Игроки ходят по очереди, первым ходит Сувлакити.
Во время своего хода игрок должен выбрать ровно одно принадлежащее ему целое число и отдать его другому игроку. Можно доказать, что при данных ограничениях игры это всегда возможно.
После того как завершатся все $$$10^{100}$$$ ходов, Сувлакити вычислит свой результат как размах принадлежащих ему целых чисел (то есть его результат равен $$$\max(S) - \min(S)$$$, где $$$S$$$ — множество принадлежащих ему целых чисел). Можно доказать, что к концу игры у Сувлакити будет хотя бы одно целое число.
Сувлакити хочет максимизировать свой результат, а Каламакити хочет минимизировать результат Сувлакити. Каким будет итоговый результат Сувлакити, если оба игрока действуют оптимально?
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 100$$$).
Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$. Гарантируется, что существует хотя бы один символ $$$\mathtt{1}$$$ в $$$s$$$.
Для каждого набора входных данных в отдельной строке выведите одно целое число — итоговый результат Сувлакити после окончания игры, если оба игрока действуют оптимально.
6201311141100511111610101071101001
021446
В первом наборе входных данных изначально Сувлакити принадлежит только целое число $$$2$$$. За каждую пару последовательных ходов (сначала ход Сувлакити, затем ход Каламакити) Сувлакити отдаёт одно целое число и получает одно целое число, поэтому после каждого хода Каламакити у него ровно столько же целых чисел, сколько было изначально. Поскольку число ходов чётное, последний ход делает Каламакити, поэтому в конце игры у Сувлакити ровно одно целое число, а его результат равен $$$0$$$.
Во втором наборе входных данных изначально Сувлакити принадлежат все три целых числа. По тем же рассуждениям в конце игры ему принадлежат три целых числа, то есть все числа, поэтому его результат равен $$$3 - 1 = 2$$$.
