问题 3878 --最多捕获

3878: 最多捕获★★

时间限制: 1 Sec  内存限制: 256 MB
提交: 59  解决: 10
[提交][状态][命题人:]

题目描述

暑假快结束啦!弓长马也同学马上就要去上学啦!可是他还想最后再好好玩一次。于是他就让小小潘出个主意。由于这段时间弓长马也同学很喜欢何士奇,所以小小潘就制定了一个游戏规则:

给你一个由0~3组成的字符串:

0表示这一时刻什么都没有;

1表示这一时刻有一只乔子王;

2表示这一时刻有一只何士奇;

3表示这一时刻有一只乔子王和一只何士奇;

在每一个时刻,弓长马也同学可以做以下几个操作之一:

1. 如果当前时刻有一只乔子王,那么你可以用这只乔子王做一包诱饵,在下一时刻或更久以后你可以用一包诱饵来抓到一只何士奇。

2. 如果当前时刻只有一只何士奇,那么你就可以不用耗费任何诱饵抓到他(毕竟比较傻)

3. 如果当前时刻没有何士奇但是你有至少一包诱饵,那么你可以消耗一包诱饵来捕获一只何士奇

4. 什么都不干

弓长马也同学想抓到尽可能多的何士奇。

但是就在小小潘给弓长马也同学描述完规则时,弓长马也同学突然想起他暑假作业还没有做完,于是他就将这个艰巨的任务交给了你。


输入

一行输入一个数t(1≤t≤2.5*10^5),表示测试用例的数量。
每组测试用例有两行,第一行是一个数n(1≤n≤2*10^6),表示字符串的长度,第二行是一个只包含0~3的一个字符串。

所有的n之和不超过2*10^6


输出

对于每一个测试用例,输出弓长马也同学最多能捕获到多少何士奇。

样例输入
Copy
2
4
0103
1
1
样例输出
Copy
2
0

提示

来源

[提交][状态]