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

К доктору ТС поступил новый пациент по имени Гоблин. Он хочет проверить интеллект Гоблина, но ему надоели его стандартные тесты. Поэтому он решил сделать тест немного сложнее.

Сначала, он создает двоичную строку$$$^{\text{∗}}$$$ $$$s$$$ длиной $$$n$$$ символов. Затем, он создает $$$n$$$ двоичных строк $$$a_1, a_2, \ldots, a_n$$$. Известно, что $$$a_i$$$ создается путем копирования $$$s$$$, а затем инвертирования $$$i$$$-го символа ($$$\texttt{1}$$$ становится $$$\texttt{0}$$$ и наоборот). После создания всех $$$n$$$ строк, он размещает их в сетке $$$n \times n$$$ $$$g$$$, где $$$g_{i, j} = a_{i_j}$$$.

Множество $$$S$$$ размером $$$k$$$, содержащее различные пары целых чисел $$$\{(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)\}$$$, считается хорошим, если:

  • $$$1 \leq x_i, y_i \leq n$$$ для всех $$$1 \leq i \leq k$$$.
  • $$$g_{x_i, y_i} = \texttt{0}$$$ для всех $$$1 \leq i \leq k$$$.
  • Для любых двух целых чисел $$$i$$$ и $$$j$$$ ($$$1 \leq i, j \leq k$$$) координата $$$(x_i, y_i)$$$ достижима из координаты $$$(x_j, y_j)$$$, перемещаясь по соседним клеткам (которые имеют общую сторону), в каждой из которых записано значение $$$\texttt{0}$$$.

Задача Гоблина — найти максимальный возможный размер хорошего множества $$$S$$$. Поскольку доктор ТС щедр, на этот раз, он дал ему две секунды, чтобы найти ответ вместо одной. Гоблин известен своей хитростью, поэтому он попросил вас помочь обмануть доктора.

$$$^{\text{∗}}$$$Двоичная строка — это строка, состоящая только из символов $$$\texttt{1}$$$ и $$$\texttt{0}$$$.

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

Первая строка входных данных состоит из одного целого числа $$$t$$$ $$$(1 \le t \le 10^3)$$$ — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — длина двоичной строки $$$s$$$.

Вторая строка каждого набора содержит одну двоичную строку $$$s$$$ длиной $$$n$$$.

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

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

Для каждого набора входных данных выведите одно число — максимальный возможный размер хорошего множества ячеек из сетки.

Пример
Входные данные
6
3
000
4
0010
7
1011001
4
0001
2
11
1
0
Выходные данные
3
9
10
7
1
0
Примечание

В первом примере на доске записана следующая сетка:

$$$$$$ 1 0 0 $$$$$$ $$$$$$ 0 1 0 $$$$$$ $$$$$$ 0 0 1 $$$$$$

Множество, состоящее из ячеек $$$(1, 2)$$$ и $$$(1, 3)$$$, является хорошим. Множество, состоящее из ячеек $$$(1, 1)$$$ и $$$(1, 2)$$$, не является хорошим, так как значение ячейки $$$(1, 1)$$$ не равно $$$0$$$. Множество ячеек $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$ является хорошим и имеет максимальный размер $$$3$$$. Обратите внимание, что множество ячеек $$$(2, 1)$$$, $$$(3, 1)$$$ и $$$(3, 2)$$$ также является хорошим с максимальным размером $$$3$$$.

Во втором примере на доске записана следующая сетка:

$$$$$$ 1 0 1 0 $$$$$$ $$$$$$ 0 1 1 0 $$$$$$ $$$$$$ 0 0 0 0 $$$$$$ $$$$$$ 0 0 1 1 $$$$$$

И максимальный возможный размер хорошего множества равен $$$9$$$.