Николай живет в двухэтажном доме. На каждом этаже расположено по \(n\) комнат. Комнаты на каждом этаже расположены в ряд и пронумерованы слева направо целыми числами, начиная с единицы. Таким образом, каждая комната характеризуется номером этажа, на котором она находится, а также своим порядковым номером на этаже (это целое число от \(1\) до \(n\)).
Если Николай находится в какой-то комнате, он может перейти из нее в любую из двух соседних комнат на том же этаже (если таковые есть). Комнаты, с порядковыми номерами \(i\) и \(i+1\) на любом из этажей являются соседними, для всех \(1 \leq i \leq n - 1\). Также известно, что между некоторыми парами комнат, которые расположены на разных этажах, но имеют одинаковые порядковые номера, есть лестницы. Если между комнатой с номером \(x\) на первом этаже и комнатой с номером \(x\) на втором этаже есть лестница, то Николай может перейти по лестнице из одной комнаты в другую.
На картинке показан пример дома для случая \(n = 4\). Лестницы есть между комнатой номер \(2\) на первом этаже и комнатой номер \(2\) на втором этаже, а также между комнатой номер \(4\) на первом этаже и комнатой номер \(4\) на втором этаже. Стрелками указаны направления, по которым Николай может перемещаться между комнатами. Эта картинка соответствует строке «0101» во входных данных. Николай хочет обойти комнаты в своем доме. Для этого он может выбрать любую комнату для начала обхода. Далее Николай будет переходить между комнатами, учитывая описанные выше правила. Если Николай уже был в какой-то комнате, то повторно возвращаться в эту комнату он не будет.
Определите максимальное количество комнат, которые Николай может обойти, если:
- начать свой путь он может в любой комнате на любом этаже,
- и не будет переходить в те комнаты, в которых он уже был.
Выходные данные
Для каждого теста выведите максимальное количество комнат, которые Николай может обойти, если начать свой путь он может в произвольной комнате и не будет переходить в те комнаты, в которых он уже был.
Примечание
В первом наборе входных данных примера Николай может начать обход на первом этаже в первой комнате. Затем он может перейти во вторую комнату на первом этаже, а затем в третью комнату на первом этаже. После этого он может подняться по лестнице на второй этаж в третью комнату. Затем он может перейти в четвертую комнату на втором этаже, а после этого в пятую комнату на втором этаже. Таким образом, он посетит \(6\) комнат.
Во втором наборе входных данных нет ни одной лестницы, поэтому Николай может лишь обойти все комнаты на каком-то из этажей, начав либо в первой комнате на любом из этажей, либо в восьмой комнате на любом из этажей.
В третьем наборе входных данных Николай может обойти все комнаты в доме. Если он начнет обход в первой комнате на первом этаже, его путь может выглядеть следующим образом: первый этаж, первая комната \(\rightarrow\) второй этаж, первая комната \(\rightarrow\) второй этаж, вторая комната \(\rightarrow\) первый этаж, вторая комната \(\rightarrow\) первый этаж, третья комната \(\rightarrow\) второй этаж, третья комната \(\rightarrow\) второй этаж, четвертая комната \(\rightarrow\) первый этаж, четвертая комната \(\rightarrow\) первый этаж, пятая комната \(\rightarrow\) второй этаж, пятая комната.
В четвертом наборе входных данных Николай также может обойти все комнаты. Один из возможных вариантов: второй этаж, третья комната \(\rightarrow\) второй этаж, вторая комната \(\rightarrow\) второй этаж, первая комната \(\rightarrow\) первый этаж, первая комната \(\rightarrow\) первый этаж, вторая комната \(\rightarrow\) первый этаж, третья комната.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
00100
8
00000000
5
11111
3
110
|
6
8
10
6
|