Description

IOI是一个回文串，并且是一个最小回文串。所谓“最小回文串”，就是指重组字母的排列顺序后能够得到的字典顺序最前的回文串。例如BAAB是一个回文串，重组字母的排列之后可以得到另一个回文串ABBA，并且ABBA按照字典顺序应该排在BAAB的前面。

给出一个字符串，如果不能组合成回文串，则输出“Sorry”；否则输出最小回文串。

Input

第一行的正整数N（1<=N<=10）表示有N组测试数据。其后N行，每行都有一个字符串。字符串只由大写字母A-Z组成，并且字符串的长度不超过80

Output

输出数据有N行，每行对应一组测试数据。

Sample

Input

1
IOI

Output

IOI