思路解析

1. 对于任何要变为回文的位置对 $(i,n+1-i)$，若 $s_i=s_{n+1-i}$，则无需处理；若 $s_i\neq s_{n+1-i}$，则称这一对为“不匹配”。
2. 只需关心左半区间 $i=1,2,\dots,\lfloor \tfrac n2\rfloor$，定义不匹配数组

3. 一次翻转操作可以选择将一段连续的 $s$ 区间翻转，从而影响一段连续的 $a_i$ 中的所有 $1$（可以将它们变为 $0$）。
4. 因此，需要的最少操作次数，即为数组 $a$ 中“连续 1 的段”的个数。

题目内容

在小红书$App$首页的两列$Plog$中，小红薯独爱第一列。她将第一列每条$Plog$的点赞状态从上到下用一个二进制字符串$s=(s_1,s_2,...s_n)$表示，其中:

• 字符$s_i$='$1$'表示用户已点赞第$i$条$Plog$;
• 字符$s_i$='$0$'表示用户未点赞第$i$条$Plog$。

小红薯定义一轮点赞行为如下:

• 选择索引对$1≤l≤r≤n$;
• 从第$l$条$Plog$ 开始，到第$r$条$Plog$结束，进行一次重复点赞行为。这会使得原本未点赞的$Plog$变为已点赞，原本已点赞的$Plog$变为未点赞。

小红薯希望使得这一列$Plog$ 的点赞状态调整为一个回文串，即第一条和最后一条$Plog$的点赞状态相同，第二条和倒数第二条$Plog$的点赞状态相同，以此类推。

请计算她最少需要进行的点赞行为轮数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤10^4)$代表数据组数，每组测试数据描述如下:

第一行输入一个整数$n(1≤n≤2*10^5)$，表示$Plog$数量;

第二行输入一个长度为$n$、由字符'$0$'和'$1$'构成的字符串$s$，表示点赞状态。

除此之外，保证单个测试文件的$n$之和不超过$2*10^5$。

输出描述

对于每一组测试数据，新起一行，输出一个整数，代表使字符串s成为回文串所需的最少点赞行为轮数。

样例1

输入

2
2
01
3
010

输出

1
0