U360475 01 串的分割（暂无 Subtask 4 数据）

LT 是一个可爱的女孩子，她很喜欢数字 $\texttt1$，每当她看见一个有很多的 $\texttt1$ 的东西，她都想要据为己有。 对于每一个东西，她都有一个接受度 $d=\frac{\texttt{1的个数}}{\texttt{所有数字的个数}}\times100\%$，当且仅当 $d>50\%$ 时，LT 才会开心地收下这个东西。

一天，她得到了 $T$ 个长长的（巨长无比!）的 $\texttt{01}$ 串 $s$，她数了整整两秒，得出了每个 $\texttt{01}$ 串的长度为 $n$ $!$（假设她的数数速度与序列长度成反比）。 她有一种神奇的能力，可以把一个 $\texttt{01}$ 串分裂成任意段，但是她不能分裂数字，她只会留下她喜欢的子串。但是现在她发愁了，对于每一个数列，她都想要留下最多的 $\texttt1$，但是还有十分钟学校就要上课了，她到教室恰好需要九分五十九秒，她将这宝贵的一秒钟留给你，让你告诉她每一个序列最多可以留下多少个数字。 由于对于短短的串 LT 都可以在 $0.99999\cdots$ 秒内完成，所以这些问题她都只会给你一分安慰你。

**本题有多组数据**。 第一行一个整数 $T$，表示数据组数。 对于每组数据： 第一行一个整数 $n$。 第二行给出这个 $\texttt{01}$ 串。

对于每组数据，输出一个整数，表示她最多能留下的数字个数。

**本题采用捆绑测试**。 - Subtask 1（1 points）：$|s| \le 10,T\le3$。 - Subtask 2（1 points）：$|s| \le 150\sum |s|\le500$。 - Subtask 3（1 points）：$|s| \le 1000,\sum |s|\le10^4$。 - Subtask 4（97 points）：无特殊限制。 对于 $100\%$ 的数据，$|s|\le2\times10^5,\sum |s|\le5\times10^6,T\le\sum |s|$。 注：非比赛题，部分分仅用于测试代码是否能够通过相应复杂度，对应分数没有实际意义。 [一个 $O((n!)^2)$ 简单 DP 代码](https://www.luogu.com.cn/paste/g4h31500)