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

Sample Output

Hint

Source