UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4505. [AMPPZ2014]Hit of the Season

Statistics 下载数据

Description

给定一个仅包含RGB*的字符串S,RGB分别表示三种颜色,*表示这个位置的颜色没有要求(但是必须被染色)。
请找到最短的一个模板串T,使得T可以印刷出S,如果一个位置被多种颜色印刷,那么将显示混合色。

Input

第一行包含一个正整数t(1<=t<=10),表示测试数据的组数。
接下来t行,每行一个字符串S(1<=|S|<=3000),表示带染色的串S,数据保证*的个数不超过19个。

Output

输出t行。第i行输出第i组数据的答案,输出一个仅包含RGB的字符串T,如有多组解,输出任意一组。

Sample Input

1
RRG*R*BRR**B

Sample Output

RRGB

Hint

Source