Longest Proper Prefix-Suffix

Given a string \( S \), find the length of the longest proper prefix of \( S \) that is also a suffix. A proper prefix is defined as a prefix which is not equal to the entire string. Formally, for a string of length \( n \), determine the maximum integer \( L \) (with \( 0 \le L < n \)) such that the first \( L \) characters and the last \( L \) characters of \( S \) are identical.

You may use an efficient approach based on the Knuth-Morris-Pratt (KMP) algorithm. In this approach, you construct a longest prefix-suffix (LPS) array where each element \( lps[i] \) represents the length of the longest proper prefix of \( S[0\ldots i] \) that is also a suffix of \( S[0\ldots i] \). The final answer for \( S \) is \( lps[n-1] \).

Note: The entire string is not considered as a proper prefix.

inputFormat

The first line of input contains an integer \( T \) denoting the number of test cases. Each of the following \( T \) lines contains a string \( S \). The string \( S \) may be empty.

Example:

3
abcdabc
aaaaa
abcab

outputFormat

For each test case, output a single integer representing the length of the longest proper prefix of \( S \) that is also a suffix. Each result should be printed on a new line.

Example:

3
4
2

## sample

3
abcdabc
aaaaa
abcab

3
4
2

</p>