CF1244B.Rooms and Staircases

Nikolay lives in a two-storied house. There are $n$ rooms on each floor, arranged in a row and numbered from one from left to right. So each room can be represented by the number of the floor and the number of the room on this floor (room number is an integer between $1$ and $n$).

If Nikolay is currently in some room, he can move to any of the neighbouring rooms (if they exist). Rooms with numbers $i$ and $i+1$ on each floor are neighbouring, for all $1 \leq i \leq n - 1$. There may also be staircases that connect two rooms from different floors having the same numbers. If there is a staircase connecting the room $x$ on the first floor and the room $x$ on the second floor, then Nikolay can use it to move from one room to another.

The picture illustrates a house with $n = 4$. There is a staircase between the room $2$ on the first floor and the room $2$ on the second floor, and another staircase between the room $4$ on the first floor and the room $4$ on the second floor. The arrows denote possible directions in which Nikolay can move. The picture corresponds to the string "0101" in the input.

Nikolay wants to move through some rooms in his house. To do this, he firstly chooses any room where he starts. Then Nikolay moves between rooms according to the aforementioned rules. Nikolay never visits the same room twice (he won't enter a room where he has already been).

Calculate the maximum number of rooms Nikolay can visit during his tour, if:

• he can start in any room on any floor of his choice,
• and he won't visit the same room twice.

尼古拉住在一栋两层的房子里。每层楼有 $n$ 个房间，沿一条直线排列，从左到右依次编号为 $1$ 到 $n$。因此，每个房间可用其所在楼层号以及该楼层上的房间号（一个介于 $1$ 到 $n$ 之间的整数）来表示。

若尼古拉当前位于某个房间中，则他可以移动到任意一个相邻的房间（如果该相邻房间存在）。在每一层楼中，房间编号为 $i$ 和 $i+1$ 的房间是相邻的，其中 $1 \leq i \leq n - 1$。此外，还可能存在连接不同楼层上编号相同的两个房间的楼梯。若存在一条连接第一层第 $x$ 号房间与第二层第 $x$ 号房间的楼梯，则尼古拉可利用该楼梯在两个房间之间移动。

图中展示了一栋 $n = 4$ 的房子。第一层第 $2$ 号房间与第二层第 $2$ 号房间之间有一段楼梯，第一层第 $4$ 号房间与第二层第 $4$ 号房间之间也有一段楼梯。箭头表示尼古拉可能的移动方向。该图对应输入中的字符串 "0101"。

尼古拉希望在他家的若干房间中进行一次游历。为此，他首先任选一个房间作为起点；然后，他根据上述规则在房间之间移动。尼古拉绝不会重复访问同一个房间（即他不会进入一个自己已经到过的房间）。

请计算：在满足以下条件的前提下，尼古拉一次游历最多能访问多少个房间？

• 他可以从任意一层的任意一个房间出发；
• 他不会重复访问任何一个房间。

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases in the input. Then test cases follow. Each test case consists of two lines.

The first line contains one integer $n$ $(1 \le n \le 1\,000)$ — the number of rooms on each floor.

The second line contains one string consisting of $n$ characters, each character is either a '0' or a '1'. If the $i$-th character is a '1', then there is a staircase between the room $i$ on the first floor and the room $i$ on the second floor. If the $i$-th character is a '0', then there is no staircase between the room $i$ on the first floor and the room $i$ on the second floor.

In hacks it is allowed to use only one test case in the input, so $t = 1$ should be satisfied.

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示输入中测试用例的数量。随后是若干测试用例。每个测试用例由两行组成。

第一行包含一个整数 $n$（$1 \le n \le 1\,000$），表示每层楼的房间数量。

第二行包含一个长度为 $n$ 的字符串，其中每个字符为 '0' 或 '1'。若第 $i$ 个字符为 '1'，则表示第一层楼的第 $i$ 个房间与第二层楼的第 $i$ 个房间之间存在楼梯；若第 $i$ 个字符为 '0'，则表示第一层楼的第 $i$ 个房间与第二层楼的第 $i$ 个房间之间不存在楼梯。

在 hack 中，输入中只允许使用一个测试用例，因此必须满足 $t = 1$。

For each test case print one integer — the maximum number of rooms Nikolay can visit during his tour, if he can start in any room on any floor, and he won't visit the same room twice.

对于每个测试用例，输出一个整数——Nikolay 在其游览过程中最多可以访问的房间数量（他可以从任意楼层的任意房间开始，且不会重复访问同一房间）。

In the first test case Nikolay may start in the first room of the first floor. Then he moves to the second room on the first floor, and then — to the third room on the first floor. Then he uses a staircase to get to the third room on the second floor. Then he goes to the fourth room on the second floor, and then — to the fifth room on the second floor. So, Nikolay visits $6$ rooms.

There are no staircases in the second test case, so Nikolay can only visit all rooms on the same floor (if he starts in the leftmost or in the rightmost room).

In the third test case it is possible to visit all rooms: first floor, first room $\rightarrow$ second floor, first room $\rightarrow$ second floor, second room $\rightarrow$ first floor, second room $\rightarrow$ first floor, third room $\rightarrow$ second floor, third room $\rightarrow$ second floor, fourth room $\rightarrow$ first floor, fourth room $\rightarrow$ first floor, fifth room $\rightarrow$ second floor, fifth room.

In the fourth test case it is also possible to visit all rooms: second floor, third room $\rightarrow$ second floor, second room $\rightarrow$ second floor, first room $\rightarrow$ first floor, first room $\rightarrow$ first floor, second room $\rightarrow$ first floor, third room.

在第一个测试用例中，尼古拉可以起始于第一层的第一间房间。接着他移动到第一层的第二间房间，然后——移动到第一层的第三间房间。随后他使用楼梯到达第二层的第三间房间。接着他前往第二层的第四间房间，然后——到达第二层的第五间房间。因此，尼古拉共访问了 $6$ 间房间。

第二个测试用例中没有楼梯，因此尼古拉只能访问同一楼层的所有房间（前提是他在最左侧或最右侧的房间开始）。

在第三个测试用例中，有可能访问所有房间：第一层第一间房间 $\rightarrow$ 第二层第一间房间 $\rightarrow$ 第二层第二间房间 $\rightarrow$ 第一层第二间房间 $\rightarrow$ 第一层第三间房间 $\rightarrow$ 第二层第三间房间 $\rightarrow$ 第二层第四间房间 $\rightarrow$ 第一层第四间房间 $\rightarrow$ 第一层第五间房间 $\rightarrow$ 第二层第五间房间。

在第四个测试用例中，同样有可能访问所有房间：第二层第三间房间 $\rightarrow$ 第二层第二间房间 $\rightarrow$ 第二层第一间房间 $\rightarrow$ 第一层第一间房间 $\rightarrow$ 第一层第二间房间 $\rightarrow$ 第一层第三间房间。