Chef has a binary string S of length N. Chef wants to find two disjoint substrings of equal length, such that their [bitwise XOR] is maximised.

Formally, Chef wants to find L_{1}, R_{1}, L_{2}, and R_{2} such that:
1 ≤ L_{1} ≤ R_{1} < L_{2} ≤ R_{2} ≤ N, that is, the substrings are disjoint (have no common elements);
|R_{1} - L_{1} + 1| = |R_{2} - L_{2} + 1|, that is, the substrings have equal length;
S_{L_{1} \dots R_{1}} \oplus S_{L_{2} \dots R_{2}} is maximised, where \oplus is the bitwise XOR operation.

Output the maximum XOR value in decimal notation. Since the value can be large, output it module 10^{9}+7.

Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N denoting the length of string S.
- The second line of each test case contains a binary string S of length N containing 0s and 1s only.

------ Output Format ------ 

For each test case, output the maximum XOR value in decimal notation. Since the value can be large, output it module 10^{9}+7.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 5000$
$S$ contains $0$ and $1$ only.
- The sum of $N^{2}$ over all test cases won't exceed $2.5 \cdot 10^{7}$.

----- Sample Input 1 ------ 
3
4
1001
5
11111
3
011

----- Sample Output 1 ------ 
3
0
1

----- explanation 1 ------ 
Test case $1$: We can choose $L_{1} = 1, R_{1} = 2, L_{2} = 3,$ and $R_{2} = 4$. Thus, the chosen substrings are $10$ and $01$. The XOR of these substrings is $11$ whose decimal equivalent is $3$.

Test case $2$: We can choose $L_{1} = 2, R_{1} = 2, L_{2} = 4,$ and $R_{2} = 4$. Thus, the chosen substrings are $1$ and $1$. The XOR of these substrings is $0$ whose decimal equivalent is $0$.

Test case $3$: We can choose $L_{1} = 1, R_{1} = 1, L_{2} = 3,$ and $R_{2} = 3$. Thus, the chosen substrings are $0$ and $1$. The XOR of these substrings is $1$ whose decimal equivalent is $1$.

Difficulty: VERY_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right
mo = 1000000007
for _ in range(int(input())):
	n = int(input())
	st = input().strip()
	z = []
	o = []
	for i in range(n):
		if st[i] == '0':
			z.append(i)
		else:
			o.append(i)
	for l in range(n // 2, 0, -1):
		flag = False
		for s in range(n - 2 * l + 1):
			if st[s] == '0':
				ind = bisect_left(o, s + l)
				if ind != len(o) and o[ind] <= n - l:
					flag = True
					break
			else:
				ind = bisect_left(z, s + l)
				if ind != len(z) and z[ind] <= n - l:
					flag = True
					break
		if flag:
			break
	else:
		print(0)
		continue
	ans = '0' * l
	for s in range(n - 2 * l + 1):
		for e in range(s + l, n - l + 1):
			if st[s] != st[e]:
				tans = ''
				for i in range(l):
					if st[s + i] != st[e + i]:
						tans += '1'
					else:
						tans += '0'
				if tans > ans:
					ans = tans
	nu = 0
	for i in range(l):
		nu *= 2
		nu += ord(ans[i]) - ord('0')
		nu %= mo
	print(nu)