Grammy 的生日快要来了，她从她的朋友那里获得了一个序列 作为礼物。序列由 ， 和 构成。Grammy 觉得这个序列太长了，所以她打算把 修改得短一些。
更正式地，Grammy 可以执行任意次操作。每次她可以执行以下三种操作之一：
求 Grammy 能得到的最短序列的长度。
有多组测试数据。第一行输入一个整数 表示测试数据组数。对于每组测试数据：
第一行输入一个长度为 的字符串（）。字符串由数字 ， 和 构成，表示初始序列 。
保证所有数据 之和不超过 。
每组数据输出一行一个整数，表示 Grammy 能得到的最短序列的长度。
5 0110101 01020102 0000021111 1012121010 0100202010
3 4 0 6 0
