Solve the Mystery.

Note

There is partial marking for this question.

Input

The first line of each test file contains a single integer T. Then T lines follow. Each line contains a string of lowercase characters

Output

For each test case output the answer in a new line.

Constraints

1<= T <=50000

1<=length of string<=10000

The string consists of only lowercase characters

Problem Setter: Jayam Modi