Description

这天，小Q游历于花花世界，他发现有一排花长的特别独特，于是他把这一排花臆想成一串美妙的字符串，现在他好奇字符串中的字符都出现了多少次，最后希望你按照出现次数的大小对字符串重新进行排序。

（如果两个字符出现次数相同）请先输出小的字符；

（字符串中只包含小写字母）

Format

Input

共T组测试数据(1<=T<=10);

每一组输入一个字符串（多组输入）s(1<=s<=1000);

Output

按照题目要求输出字符串

Samples

2
coorr
aaabb

oorrc
aaabb

Hint