Longest Proper Prefix-Suffix

Given a non-empty string s, find its longest proper prefix which is also a suffix. A proper prefix is defined as a prefix that is not equal to the entire string. In other words, if k is the length of such a prefix, then it satisfies the condition $$s[0:k] = s[n-k:n]$$ with $$0 < k < n$$, where n is the length of s.

For example:

• For s = "level", the longest proper prefix-suffix is "l".
• For s = "ababab", the answer is "abab".
• For s = "abcabc", the answer is "abc".
• For s = "abcd", there is no proper prefix which is also a suffix, so the answer is an empty string.

inputFormat

The input is given via standard input (stdin) and starts with an integer T representing the number of test cases. Then, T lines follow, each containing one string s.

outputFormat

For each test case, print the longest proper prefix of the string that is also a suffix. If no such prefix exists, print an empty line.

## sample

4
level
ababab
abcabc
abcd

l
abab
abc

</p>