题目背景

感谢

宇宙射线天天乱改东西/fn。

题目描述

有一个长度为 $n$ 的二进制串 $s$，你需要找到一个最长的长度为偶数的子串，使得它的前半部分和后半部分完全相同。

但是因为宇宙射线攻击了这个串，有一些位置的值变得未知了。

你可以把未知的值视为 $0$ 和 $1$ 的任意一个数，求出在这种情况下这个最长子串的长度。

本题有多组测试。

输入格式

第一行一个正整数 $t$，表示测试组数。

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

输出格式

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

2
10
0110011010
6
01?0?0

4
3

提示

本题采用捆绑测试。

$A$：保证 $s$ 中不存在字符 ?。

保证字符串只由 0,1,? 三种字符组成，$1\le n\le 10^5$。