Jerry has some cheeses. The cheeses have many different tastes. We use different lowercase letters to indicate different tastes. Now, Jerry wants to eat each of them in some order. Besides, Jerry doesn’t want to eat two chesses with same taste continuously. Since there may be multiple solutions, Jerry wants to know the lexicographic smallest one. 

      There are multiple cases. The number of cases will be no more than 50. 

      Each case contains a non-empty string describing Jerry’s cheeses. Its length doesn’t exceed 10000 and only contains lowercase letters.

For each case, if there doesn’t exist any solution, print “QAQ”. Otherwise print cheeses in Jerry’s order.