Two strings can be shuffled by interspersing their letters to form a new string, much like two piles of cards can be shuffled to form a single pile.

For example, the strings HELLO and WORLD can be shuffled to form HWEOLRLLOD, or HEWORLLLDO, or perhaps simply HELLOWORLD. It is not a shuffle if the original order of letters is not preserved. For example, the D in WORLD cannot ever appear before the R after being shuffled. This means that EHLLOWRDLO, for instance, is not a shuffle of HELLO and WORLD, even though it contains all the original letters. A string is a shuffle of twins if it can be formed by shuffling two identical strings.

For example, ABACBDECDE is a shuffle of twins because it can be formed by shuffling ABCDE and ABCDE. DBEACBCADE is not a shuffle of twins because it cannot be formed by shuffling two identical strings.
All the strings will contains only UPPERCASE letters.

In case, no twins exist output “Twins don’t exist” (quotes only for clarity).

All strings will contain only UPPERCASE letters.

Input

The first line of the input will is integer T denoting the number of testcases.

Next T lines contain the shuffled string S. The input string can contain upto N letters.

Output

For every testcase, output a single line containing one of the two identical strings that make up the input string.

If the no such pair of identical strings exist, print "Twins don't exist". (quotes only for clarity).

Constraints

1

2 ⁶

Example

Input: 2 ABACBDECDE DBEACBCADE Output: ABCDE Twins don't exist