2975. One Shot

【限制】1000ms, 256M

【友情提示】

这个题意很复杂,请认真读题!如果你不确认自己的题意,请随便举手质问出题人。如果你没读完就确认了自己的题意,请不要轻易确认自己的题意。别那么着急,你想,你要是读错了题,写了个假题,那不是更浪费时间。所以慢慢读,比较快,是吧。

【问题描述】

Niko已经接近了真相,但是突然他的面前出现了一个谜题。

这是一个方形的网格,对于每个空白的格子,踩上去会把这个格子涂上颜色,再踩一次这个格子又会变成空白的,再踩一次就又会涂上颜色……像这样,Niko需要在上面踩出指定的图案。



oneshot.gif



现在我们的问题有一些不一样,是一个1*n的网格。接下来请仔细看下面这段描述,不要只看图:

这个网格的上下两边被奇怪的墙封闭住,只有左右两个出入口。但是只是网格被封闭了,你仍然可以从网格下面来到任何一个出入口。

也就是说,每次你走下网格,你可以自由的选择左右任意一个出入口再次踏上网格




Wall.gif



那么问题来了,初始的网格是空白的,给出你需要踩出的图案,你最少需要在网格上走多少步呢?(踏上网格跟离开网格的那一步都计算在内


【输入形式】

首先输入数据组数T(0<T<=5)

对于每组数据:

第一行输入n(0<n<=1000)

第二行一个长度为n的01串代表你要踩出的图案(0代表空白,1代表涂色)

【输出形式】

输出最小的步数。

【样例输入】

1
5
00010

【样例输出】

4


难度等级: 0
总通过次数: 7
总提交次数: 109