Longest Even Substring with Matching Halves

Given a binary string s of length n which may have some characters become unknown due to cosmic ray attacks, your task is to find the length of the longest even-length substring such that its first half and second half can be made identical. Unknown characters are represented by ? and can be interpreted as either 0 or 1 arbitrarily.

Formally, for a substring of even length L = 2m taken from s, let the first half be s[i ... i+m-1] and the second half be s[i+m ... i+2m-1]. The two halves are considered identical if for every j (0 ≤ j < m), either the characters are the same or at least one of them is unknown (i.e. ?), so that an appropriate assignment can make them equal.

This problem contains multiple test cases.

inputFormat

The first line contains an integer T denoting the number of test cases.

For each test case, the input consists of two lines:

1. The first line contains an integer n representing the length of the binary string.
2. The second line contains the binary string s of length n, where unknown characters are represented by ?.

outputFormat

For each test case, output a single integer in a new line denoting the length of the longest even-length substring such that its first half and the second half can be made identical by assigning values to the unknown characters.

sample

3
4
?0?0
5
?1001
6
1??0?1

4
2
4