宇宙射线

感谢 @[jason_sun](https://www.luogu.com.cn/user/399762) 加强数据。 宇宙射线天天乱改东西/fn。

有一个长度为 $n$ 的二进制串 $s$，你需要找到一个最长的长度为偶数的子串，使得它的前半部分和后半部分完全相同。 但是因为宇宙射线攻击了这个串，有一些位置的值变得未知了。 你可以把未知的值视为 $0$ 和 $1$ 的任意一个数，求出在这种情况下这个最长子串的长度。 本题有多组测试。

第一行一个正整数 $t$，表示测试组数。 接下来 $2t$ 行，每两行表示一组测试数据，每组测试数据第一行一个正整数 $n$，表示字符串的长度，接下来一行一个长度为 $n$ 的字符串 $s$。

$t$ 行，每行一个非负整数，表示第 $i$ 组测试的答案，由于这个串长一定是偶数，所以你只用输出它的长度除以 $2$ 的结果。

2
10
0110011010
6
01?0?0

4
3

**本题采用捆绑测试。** | $\text{Subtask}$ | 分数 | $n,t$ | 特殊性质 | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $n\le 10,t=500$ | 无特殊限制 | | $2$ | $10$ | $n\le1000,t=1$ | 无特殊限制 | | $3$ | $10$ | $n\le 1000,t=1000$ | $A$ | | $4$ | $10$ | $n\le 1000,t=1000$ | 无特殊限制 | | $5$ | $10$ | $n\le 10^4,t=10$ | 无特殊限制 | | $6$ | $10$ | $n\le 10^4,t=50$ | 无特殊限制 | | $7$ | $20$ | $n\le 5\times 10^4,t=2$ | 无特殊限制 | | $8$ | $15$ | $n\le 10^5,t=1$ | 无特殊限制 | | $9$ | $5$ | $n\le 10^5,t=5$ | 无特殊限制 | $A$：保证 $s$ 中不存在字符 `?`。 保证字符串只由 `0,1,?` 三种字符组成，$1\le n\le 10^5$。