#CF2266C. AND, OR, Sort!

AND, OR, Sort!

题目描述

给定一个长度为 nn 的二进制字符串∗^{\text{∗}} ss。

你可以执行以下操作任意次数(可以为零):

  • 选择一个整数 ii(1≤i≤n1 \le i \le n),将 sis_i 替换为 s1,s2,…,sis_1, s_2, \ldots, s_i 的按位与或按位或。

注意,单个元素的按位与或按位或等于该元素本身。

你的目标是使 ss 按非降序排列†^{\text{†}}。

求使 ss 按非降序排列所需的最少操作次数。

∗^{\text{∗}}二进制字符串仅包含字符 0\texttt{0} 和 1\texttt{1}。

†^{\text{†}}若 ss 按非降序排列,则 s1≤s2≤…≤sns_1 \leq s_2 \leq \ldots \leq s_n。

输入格式

第一行包含一个整数 tt(1≤t≤1041 \le t \le 10^4)— 测试用例的数量。

每个测试用例的第一行包含一个整数 nn(2≤n≤2⋅1052 \le n \le 2 \cdot 10^5)— 二进制字符串 ss 的长度。

每个测试用例的第二行包含长度为 nn 的二进制字符串 ss。ss 的每个字符要么是 0 要么是 1。

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5。

输出格式

对于每个测试用例,输出一个整数 — 使 ss 按非降序排列所需的最少操作次数。

样例

6
4
0011
4
1000
5
01000
8
01001101
7
0101010
7
0111101
0
3
1
2
3
1

说明

在第一个测试用例中,字符串已经有序,因此不需要任何操作。

在第二个测试用例中,可以使用按位或将最后三个字符变为 1,经过 33 次操作得到 1111。

来源

导入自 Codeforces — Codeforces Round 1122 (Div. 3)。