#NC15029. 吐泡泡

吐泡泡

题目描述

小鱼儿会吐出两种泡泡:大泡泡 "O"\texttt{"O"},小泡泡 "o"\texttt{"o"};两种泡泡的变化规则如下:

∙ \bullet\,任意两个相邻的小泡泡会融合成一个大泡泡;

∙ \bullet\,任意两个相邻的大泡泡会相互爆炸,变成空白(即消失)。

上述合并与爆炸过程自左至右依次进行,直至无法再进行任何操作。

例如,对于初始泡泡序列 "ooOOoooO"\texttt{"ooOOoooO"},经过一段时间后会变成 "oO"\texttt{"oO"}。

题目插图

输入格式

第一行输入一个整数 T(1≤T≤10)T\left(1\leq T\leq 10\right) 代表数据组数。

接下来 TT 行,每行一个仅由 'O' 和 'o' 构成的字符串 ss,字符串长度不超过 10510^5。

输出格式

每组输出仅包含一行,输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。

样例 1

1
ooOOoooO
oO

来源

牛客原题