A. Donuts and Cupcakes
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bira's cooking skills have made him famous across the country, earning him an invitation to compete in the prestigious MasterChef: Pastry Edition! For the Halloween episode, he has prepared a mouthwatering tray of donuts and cupcakes. The $$$n$$$ treats are arranged in a single row, represented by a string $$$s$$$: each D represents a donut and each C represents a cupcake.

Just as he finishes, Bira remembers that the judges also care about presentation! This time, they require every segment of five consecutive treats to contain exactly one donut and four cupcakes.

Bira must hurry to rearrange his tray. He may reorder the treats however he likes, but must use every treat he has made, without adding, removing, or changing any of them. Help him find an arrangement that meets the judges' requirement, or determine that it is impossible.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^{5}$$$), the number of test cases.

Each test case consists of two lines. The first contains an integer $$$n$$$ ($$$5 \leq n \leq 2 \times 10^{5}$$$), the number of treats. The second contains a string $$$s$$$ of length $$$n$$$, consisting only of D and C, describing their initial arrangement.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^{5}$$$.

Output

For each test case, print -1 on a single line if no arrangement of Bira's treats meets the requirement.

Otherwise, print a string of length $$$n$$$ representing a valid arrangement. It must contain the same number of each character as $$$s$$$. If several valid answers exist, print any of them.

Example
Input
5
10
DDCCCCCCCC
6
CCCCDC
6
DDCCCC
5
DDCCC
11
DCCCCCCCCCC
Output
DCCCCDCCCC
CCCCDC
DCCCCD
-1
-1