题目描述

有两层房间，每层 $n$ 个，我们用数对 $(a, b)$ 来表示每个房子，其中 $a$ 表示第几层，$b$ 表示从左向右数第几个

对于房子 $(1, i)$ 或 $(2, i)$，都与 $(1, i - 1), (1, i + 1)$ 或 $(2, i - 1), (2, i + 1)$ 相连

而在若干个或个位置中，又有一个双向的梯子，具体来说，若在 $i$ 的位置有一个梯子，则 $(1, i), (2, i)$ 是相连的

求不重复经过同一个房间的情况下，最多能走过多少个房间

输入格式

第一行给出测试数据组数

对于每组测试数据：

第一行给出 $n$，意义如上

第二行给出一个长度为 $n$ 的 $01$ 串，若在 $i$ 位为 $1$，代表在位置 $i$ 有个梯子

输出格式

不重复经过同一个房间的情况下，最多能走过多少个房间

样例

4
5
00100
8
00000000
5
11111
3
110

6
8
10
6