Byteotian Printing Factory (BPF) 收到了一份关于条纹壁纸的大型生产订单。条纹壁纸是本季室内设计的流行趋势。每张壁纸都有 $n$ 条等宽的垂直条纹，颜色分别为红色、绿色和蓝色。BPF 负责壁纸的设计和印刷。客户会指定壁纸中某些条纹的颜色，对于其他条纹的颜色，客户允许 BPF 自由决定。

BPF 使用矩阵来印刷壁纸上一定数量的连续条纹。矩阵中每一条条纹都有特定的颜色。矩阵的长度可以短于整张壁纸。每次使用矩阵时，矩阵的条纹必须与壁纸上的条纹对齐并覆盖，然后进行印刷。通过这种方式，同一条壁纸条纹可以被多次印刷。如果某条条纹被不同颜色的矩阵条纹覆盖，最终颜色将是这些颜色的混合。矩阵只能以一种方向印刷，且不能以任何方式旋转。

BPF 的员工们希望设计出最短的矩阵，以实现整张壁纸的印刷。他们必须注意，对于客户指定的条纹，必须使用纯色，不能添加任何其他颜色。换句话说，对于每次印刷覆盖了此类单色条纹的矩阵应用，矩阵条纹的颜色必须与客户定义的完全一致。壁纸上的任何条纹都不能保持无色。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10$)，表示测试用例的数量。接下来的 $t$ 行，每行描述一个测试用例，包含一个由大写字母 'R'、'G'、'B' 和星号 ('*') 组成的字符串，指定了所需的壁纸外观。字母表示条纹的颜色，星号表示客户未指定颜色的条纹。字符串非空，长度不超过 3000，且最多包含 19 个星号。

输出格式

对于每个测试用例，输出一行包含 'R'、'G'、'B' 字符的字符串：能够印刷出所需壁纸的最短矩阵。如果对于给定的测试用例存在多个正确的解决方案，输出其中任意一个即可。

样例

输入 1

1
RRG*R*BRR**B

输出 1

RRGB