In a double word every letter of the word occurs exactly twice in the word. For example, couscous is a double word because it contains twice the letter c, twice the letter o, twice the letter u, and twice the letter s.

Input

The first line of the input contains an integer $$n \in \mathbb{N}$$. This is followed by $$n$$ lines in which each line contains exactly one word. You may assume that this word contains only letters and no numbers or special characters. In determining whether a word is a double word or not, no distinction should be made between uppercase and lowercase letters. This means the word Caucasus is also a double word.

Output

Write each double word from the input on a separate line to the output.

Example

Input:

3
rice
couscous
spaghetti

Output:

couscous