Background

Thanks to

Cosmic rays change things all the time /fn.

Problem Description

Given a binary string $s$ of length $n$, you need to find the longest substring whose length is even and whose first half is exactly the same as its second half.

However, due to cosmic ray attacks on this string, the values at some positions have become unknown.

You may treat each unknown value as either $0$ or $1$. Under this condition, find the length of the longest such substring.

This problem has multiple test cases.

Input Format

The first line contains a positive integer $t$, the number of test cases.

The next $2t$ lines describe the test cases, where every two lines form one test case. For each test case, the first line contains a positive integer $n$, the length of the string, and the next line contains a string $s$ of length $n$.

Output Format

Output $t$ lines. Each line contains a non-negative integer, the answer for the $i$-th test case. Since the length of the substring must be even, you only need to output the result of dividing its length by $2$.

2
10
0110011010
6
01?0?0

4
3

Hint

This problem uses bundled tests.

$A$: It is guaranteed that $s$ contains no character ?.

It is guaranteed that the string consists only of the three characters 0, 1, and ?, and that $1\le n\le 10^5$.

Translated by ChatGPT 5