Problem Description

You are given a string s consisting of lowercase letters.

Find a string t satisfying all the following requirements:

1. t is a prefix of s.
2. t is a suffix of s.
3. t appears somewhere in the middle of s (as a substring that is neither a prefix nor a suffix).
4. The length of t should be as large as possible.

Input Format
The first line contains an integer T, the number of test cases.
Each of the next T lines contains a string s.

Output Format
For each test case, output the string t if it exists, otherwise output "not exist".

Data Range
The first 3 test cases satisfy 1 ≤ |s| ≤ 20.
All test cases satisfy 1 ≤ T ≤ 10, 1 ≤ |s| ≤ 10⁶.
The total length of all input strings s in a test point does not exceed 10⁶.

Input Sample:

2
fixprefixsuffix
abcdabc

Output Sample:

fix
not exist