归零

题目描述

Y 同学正在研究一种二进制串的变换操作。他定义了一种特殊的异或运算，作用于两个等长的二进制串（仅含 '0' 或 '1'），其规则为：对两个字符串的对应位进行异或运算，结果组成新的字符串。

现在，Y 同学有一个初始的二进制串 $S$。他希望通过若干次操作，将 $S$ 的每一位都变为 '0'。

每次操作，他都可以选择一个与 $S$ 等长、且所有 '1' 均构成单个连续块的二进制串 $P$，然后将 $S$ 更新为 $S \oplus P$（$S$ 与 $P$ 的异或结果）。

你的任务是，计算将初始字符串 $S$ 变为全零字符串，所需的最少操作次数。

输入格式

第一行输入一个正整数 $T$，表示测试数据的组数。

对于每组测试数据，输入一行，包含一个整数 $x$ 和一个长度为 $x$ 的二进制串 $S$。

输出格式

对于每组测试数据，输出一行一个整数，表示所需的最少异或操作次数。

样例

样例输入 #1

2
8 00011101
1 0

样例输出 #1

2
0

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T \le 100$
• $1 \le x \le 5 \times 10^4$