Longest Even Length Substring

You are given a string consisting of digits. Your task is to find the length of the longest even-length substring such that the sum of the digits in the first half is equal to the sum of the digits in the second half. For a substring of even length (2k), let the first half be (s[0 \ldots k-1]) and the second half be (s[k \ldots 2k-1]). The condition for a valid substring is:

[ \sum_{i=0}^{k-1} s[i] = \sum_{i=k}^{2k-1} s[i] ]

If no such substring exists, output 0. The input contains multiple test cases. For each test case, compute and print the maximum valid substring length.

inputFormat

Input is read from standard input (stdin). The first line contains an integer (T), the number of test cases. Each of the next (T) lines contains a string (s) consisting of digits.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest even-length substring where the sum of the first half is equal to the sum of the second half. If no such substring exists, output 0.## sample

2
1538023
123456

4
0