### 问题描述 大衣有一个长度为 $N$ 的二进制字符串 $S$。 你需要构造一个长度为 $N$ 的字符串 $X$： - 对于每一个索引 $i(1\le i\le N)$，有 $X_{(i+1)}=X_i\oplus S_i$，其中 $\oplus$ 表示按位异或。 - 字符串 $X​$ 中字符 $1​$ 的个数最多。 请找出字符串 $X$ 中 $1$ 的最多个数。 ### 输入格式 第一行输入一个正整数 $T​$ 表示测试数据的组数。 接下来 $T$ 组测试数据每组输入两行： - 第一行输入一个正整数 $N$ 表示字符串 $S$ 的长度。 - 第二行输入一个长度为 $N$ 个二进制字符串 $S$。 ### 输出格式 对于每组测试数据，输出一个整数表示字符串 $X$ 中 $1​$ 的最多个数，并换行。 ### 样例输入1 ```text 3 4 0011 4 1100 4 1010 ``` ### 样例输出1 ```text 3 3 2 ``` ### 说明 样例 $1$：考虑字符串 $X=1110$，其中 $X_2=X_1\oplus S_1=1\oplus0,X_3=X_2\oplus S_2=1\oplus0,X_4=X_3\oplus S_3=1\oplus1$，字符串包含 $3$ 个 $1$，可以证明没有更多的构造方案。 样例 $2​$：考虑字符串 $X=1011​$，其中 $X_2=X_1\oplus S_1=1\oplus1,X_3=X_2\oplus S_2=0\oplus1,X_4=X_3\oplus S_3=1\oplus0​$，字符串包含 $3​$ 个 $1​$，可以证明没有更多的构造方案。 样例 $3$：考虑字符串 $X=0110$，字符串包含 $2$ 个 $1$，可以证明没有更多的构造方案。 ### 评测数据规模 对于所有的评测数据，$1\le T\le 20$，$1\le N\le 10^4$，$S_i$ 为 $0$ 或 $1$。