Maximize The Sum
题号：NC313664
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小苯有一个长度为 n 的数组 a_1, a_2, \dots, a_n，其中每个元素是 0 或 1。
\hspace{15pt}小苯可以进行以下操作：选择三个连续的位置 i, i+1, i+2 \left(1 \leqq i \leqq n-2 \right)，设它们的值为 x, y, z，然后将它们同时替换为：
\hspace{23pt}\bullet\ x' = x \oplus y；
\hspace{23pt}\bullet\ y' = y \oplus z；
\hspace{23pt}\bullet\ z' = z \oplus x。
\hspace{15pt}小苯想知道，经过若干次（可以是零次）操作后，数组所有元素之和的最大可能值是多少？

【名词解释】
\hspace{15pt}\oplus：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1 \leqq T \leqq 10^4 \right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行输入一个整数 n\left(3 \leqq n \leqq 5 \times 10^5 \right)。
\hspace{15pt}第二行输入一个长度为 n，仅由字符 \texttt{`0'} 和 \texttt{`1'} 组成的字符串 a_1a_2\dots a_n，表示数组。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 5 \times 10^5。

输出描述:

\hspace{15pt}对于每一组测试数据，新起一行输出一个整数，表示所有元素的最大可能总和。
示例1

输入

复制 
2
4
0010
3
111

输出

复制 
3
3