Time Limit: 1000 MS    Memory Limit: 65536 K 


Description

As a former ACMer, "AC" is a special abbreviated word which can bring much pleasure to me. Sometimes it means everything. This problem is about "AC". One day, I write a long string S on the paper which contains "A" and "C". Now I want to find a lexicographic minimum string T satisfied that T is distinct with all substring of S.

Input

The first line of input file contains an integer T indicating the number of case. In each test case: Input is a string S consist of "A" and "C". The length of S is not large than 100.

Output

For each test case: You should output the string T meet the condition.

Sample Input

1 ACAC

Sample Output

AA