There are pigeons standing one after another in a straight line. There are two kinds of pigeons: white pigeon () and black pigeon (). We can represent the ordering of pigeons by string (). For example, means a white pigeon is standing in the first position, another white pigeon is standing in the second position and a black pigeon is standing in the third position.
Now you are given some extra pigeons, let's say black pigeons and white pigeons. You have to place the extra pigeons in the original string such that the new order will not have any adjacent pigeons with the same color. If it's possible then print , otherwise print .
The first line consists of a single Integer T (1 ≤ T ≤ 5) — the number of test cases.
For every test cases there will be following four lines:
For every case print a single line containing either or as a string.
4 7 BBWBBWW 4 2 2 BB 1 0 2 WW 0 2 5 WWBBB 1 1
YES YES YES NO
Explanation of first case: The new series is: WBWBWBWBWBWBW
Explanation of second case: The new series is BWB
Explanation of third case: The new series is BWBW
Explanation of fourth case: There is no way you can place the extra pigeons such that it fulfills the requirement.
The bold letters indicate the extra pigeons.