给你一个二进制字符串 s，长度为 n。

您可以执行以下操作任意次数（可能为零）：

选择一个整数 i（1 ≤ i ≤ n），并用 s1, s2, …, si 的 bitwise AND 或 bitwise OR 替换 si。

注意，单个元素的 bitwise AND 或 bitwise OR 等于元素本身。

您的目标是使 s 按非递减顺序排序。

求按非递减顺序对 s 排序所需的最少操作数。

• bitwise AND = 按位与。对二进制位逐位做“与”运算：只有两个位都是 1 时结果才是 1，否则是 0。
• bitwise OR = 按位或。对二进制位逐位做“或”运算：只要有一个位是 1，结果就是 1；两个都是 0 才是 0。

输入

第一行包含一个整数 t（1 ≤ t ≤ 10^4）——测试用例数。

每个测试用例的第一行包含一个整数 n（2 ≤ n ≤ 2·10^5）——二进制字符串 s 的长度。

第二行包含长度为 n 的二进制字符串 s。s 中的每个字符不是 0 就是 1。

保证所有测试用例中 n 的总和不超过 2·10^5。

输出

对于每个测试用例，打印一个整数——将 s 按非递减顺序排序所需的最少操作数。

样例

输入

6
4
0011
4
1000
5
01000
8
01001101
7
0101010
7
0111101

输出

0
3
1
2
3
1

注

在第一个测试用例中，字符串已经排序，因此无需进行任何操作。

在第二个测试用例中，我们可以使用位操作 OR 将最后三个字符改为 1，在 3 次操作中得到 1111。

注释

• 一个二进制字符串只包含字符 0 和 1。 † 如果 s 是非递减排序，那么 s1 ≤ s2 ≤ … ≤ sn。