B. Комнаты и лестницы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Николай живет в двухэтажном доме. На каждом этаже расположено по $$$n$$$ комнат. Комнаты на каждом этаже расположены в ряд и пронумерованы слева направо целыми числами, начиная с единицы. Таким образом, каждая комната характеризуется номером этажа, на котором она находится, а также своим порядковым номером на этаже (это целое число от $$$1$$$ до $$$n$$$).

Если Николай находится в какой-то комнате, он может перейти из нее в любую из двух соседних комнат на том же этаже (если таковые есть). Комнаты, с порядковыми номерами $$$i$$$ и $$$i+1$$$ на любом из этажей являются соседними, для всех $$$1 \leq i \leq n - 1$$$. Также известно, что между некоторыми парами комнат, которые расположены на разных этажах, но имеют одинаковые порядковые номера, есть лестницы. Если между комнатой с номером $$$x$$$ на первом этаже и комнатой с номером $$$x$$$ на втором этаже есть лестница, то Николай может перейти по лестнице из одной комнаты в другую.

На картинке показан пример дома для случая $$$n = 4$$$. Лестницы есть между комнатой номер $$$2$$$ на первом этаже и комнатой номер $$$2$$$ на втором этаже, а также между комнатой номер $$$4$$$ на первом этаже и комнатой номер $$$4$$$ на втором этаже. Стрелками указаны направления, по которым Николай может перемещаться между комнатами. Эта картинка соответствует строке «0101» во входных данных.

Николай хочет обойти комнаты в своем доме. Для этого он может выбрать любую комнату для начала обхода. Далее Николай будет переходить между комнатами, учитывая описанные выше правила. Если Николай уже был в какой-то комнате, то повторно возвращаться в эту комнату он не будет.

Определите максимальное количество комнат, которые Николай может обойти, если:

  • начать свой путь он может в любой комнате на любом этаже,
  • и не будет переходить в те комнаты, в которых он уже был.
Входные данные

В первой строке следует целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных в тесте. Затем следуют сами наборы входных данных. Каждый набор состоит из двух строк.

В первой строке следует целое число $$$n$$$ $$$(1 \le n \le 1\,000)$$$ — количество комнат на каждом из двух этажей в доме Николая.

Во второй строке следует строка длины $$$n$$$, состоящая из нулей и единиц. Если $$$i$$$-й символ строки равен '1', то между комнатой номер $$$i$$$ на первом этаже и комнатой номер $$$i$$$ на втором этаже есть лестница. Если $$$i$$$-й символ строки равен '0', то между комнатой номер $$$i$$$ на первом этаже и комнатой номер $$$i$$$ на втором этаже нет лестницы.

Во взломах разрешается использовать только один набор входных данных, то есть $$$t = 1$$$ должно быть выполнено.

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

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

Пример
Входные данные
4
5
00100
8
00000000
5
11111
3
110
Выходные данные
6
8
10
6
Примечание

В первом наборе входных данных примера Николай может начать обход на первом этаже в первой комнате. Затем он может перейти во вторую комнату на первом этаже, а затем в третью комнату на первом этаже. После этого он может подняться по лестнице на второй этаж в третью комнату. Затем он может перейти в четвертую комнату на втором этаже, а после этого в пятую комнату на втором этаже. Таким образом, он посетит $$$6$$$ комнат.

Во втором наборе входных данных нет ни одной лестницы, поэтому Николай может лишь обойти все комнаты на каком-то из этажей, начав либо в первой комнате на любом из этажей, либо в восьмой комнате на любом из этажей.

В третьем наборе входных данных Николай может обойти все комнаты в доме. Если он начнет обход в первой комнате на первом этаже, его путь может выглядеть следующим образом: первый этаж, первая комната $$$\rightarrow$$$ второй этаж, первая комната $$$\rightarrow$$$ второй этаж, вторая комната $$$\rightarrow$$$ первый этаж, вторая комната $$$\rightarrow$$$ первый этаж, третья комната $$$\rightarrow$$$ второй этаж, третья комната $$$\rightarrow$$$ второй этаж, четвертая комната $$$\rightarrow$$$ первый этаж, четвертая комната $$$\rightarrow$$$ первый этаж, пятая комната $$$\rightarrow$$$ второй этаж, пятая комната.

В четвертом наборе входных данных Николай также может обойти все комнаты. Один из возможных вариантов: второй этаж, третья комната $$$\rightarrow$$$ второй этаж, вторая комната $$$\rightarrow$$$ второй этаж, первая комната $$$\rightarrow$$$ первый этаж, первая комната $$$\rightarrow$$$ первый этаж, вторая комната $$$\rightarrow$$$ первый этаж, третья комната.