随着他们的故事被揭开,一个永恒的故事再次被讲述......
Shirahime 是 Mocha 的朋友,热衷于玩音乐游戏 Arcaea 并分享 Mocha 需要解决的有趣谜题。这一天,白姬想出了一个新的简单谜题,并希望摩卡能够解决它们。然而,这些谜题对摩卡来说太容易解决,所以她希望你解决它们并告诉她答案。谜题描述如下。
有 $$$n$$$ 个方块排成一排,每个方块都可以涂成红色或蓝色。
这些方格中,有的已经被绘制,有的则是空白。您可以决定在每个空白方块上绘制哪种颜色。
一些相邻的方块对可能具有相同的颜色,这是不完美的。我们将缺陷定义为共享相同颜色的相邻方块对的数量。
例如,“BRRRBBR”的不完美性是$$$3$$$,其中“BB”出现了一次,“RR”出现了两次。
您的目标是最大程度地减少缺陷并在绘画后打印出正方形的颜色。
输入
每个测试包含多个测试用例。
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。每个测试用例由两行组成。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 100$$$) — 方块行的长度。
每个测试用例的第二行包含一个字符串$$$s$$$,长度为$$$n$$$,包含字符“B”、“R”和“?”。这里“B”代表蓝色方块,“R”代表红色方块,“?”对于一个空白的正方形。
输出
对于每个测试用例,打印一行,其中包含仅包含“B”和“R”的字符串,即绘制后方块的颜色,从而最大限度地减少缺陷。如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
5 7 ?R???BR 7 ???R??? 1 ? 1 B 10 ?R??RB??B?
输出 #1
BRRBRBR BRBRBRB B B BRRBRBBRBR
注意
在第一个测试用例中,如果方块被涂成“BRRBRBR”,则缺陷为 $$$1$$$ (因为方块 $$$2$$$ 和 $$$3$$$ 具有相同的颜色),这是可能的最小缺陷。