P10920 Cosmic Rays

Thanks to @[jason_sun](https://www.luogu.com.cn/user/399762) for strengthening the testdata. Cosmic rays change things all the time /fn.

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.

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 $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$.

**This problem uses bundled tests.** | $\text{Subtask}$ | Score | $n,t$ | Special Property | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $n\le 10,t=500$ | No special constraints | | $2$ | $10$ | $n\le1000,t=1$ | No special constraints | | $3$ | $10$ | $n\le 1000,t=1000$ | $A$ | | $4$ | $10$ | $n\le 1000,t=1000$ | No special constraints | | $5$ | $10$ | $n\le 10^4,t=10$ | No special constraints | | $6$ | $10$ | $n\le 10^4,t=50$ | No special constraints | | $7$ | $20$ | $n\le 5\times 10^4,t=2$ | No special constraints | | $8$ | $15$ | $n\le 10^5,t=1$ | No special constraints | | $9$ | $5$ | $n\le 10^5,t=5$ | No special constraints | $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