Hit of the Season

Byteotian Printing Factory (BPF) has received a large order for striped wallpaper. Striped wallpaper is the hit of the season in interior design. Each wallpaper has $n$ vertical stripes of equal width, and every stripe is red (R), green (G) or blue (B). The customer specifies the colour of some stripes and leaves the colour of the other stripes to the factory.

BPF prints with a matrix. A matrix prints several consecutive stripes at once, and each stripe of the matrix has a fixed colour. The matrix may be shorter than the whole wallpaper. With each application, the stripes of the matrix must lie exactly on stripes of the wallpaper, and the matrix must not extend beyond the wallpaper; then all stripes of the matrix are printed. The matrix can be applied many times and the applications may overlap, so a single wallpaper stripe can be printed over more than once. If a stripe is printed over with different colours, its final colour is a blend of those colours. The matrix prints in one orientation only and must not be rotated or flipped.

BPF wants the shortest matrix that allows printing the entire wallpaper. Every stripe whose colour the customer specified must receive pure colour, without any addition of another colour: for every application that covers such a stripe, the matrix stripe placed on it must have exactly the specified colour. A stripe whose colour was not specified may receive any colours. No stripe of the wallpaper may remain colourless.

The first line contains one integer $t$ ($1 \le t \le 10$), the number of test cases. Each of the next $t$ lines describes one test case: a string of upper-case letters R, G, B and asterisks (*) that specifies the desired wallpaper. A letter is the colour of that stripe, and an asterisk marks a stripe whose colour the customer did not specify. The string is not empty, has at most 3000 characters, and contains at most 19 asterisks.

For each test case print one line with a string of characters R, G, B: the shortest matrix that allows printing the desired wallpaper. If several shortest matrices exist, print the lexicographically smallest one, comparing characters in the order B < G < R.