Cho một hàng có \(n\) ô vuông và mỗi ô vuông chỉ có thể được tô một trong hai màu là màu đỏ hoặc màu xanh.
Trong những ô vuông này, có một vài ô vuông đã được tô màu, còn lại thì vẫn là ô trống.
Ta có một định nghĩa như sau:

• Nếu hai ô kề nhau và được tô cùng một màu thì ta gọi là "không may mắn". Và "độ không may mắn" chính bằng số lượng cặp "không may mắn" tồn tại trong hàng gồm các ô vuông đã cho.
  Vì là đầu xuân năm mới nên nhiệm vụ của bạn bây giờ là hãy tô màu các ô vuông trống còn lại (hoặc màu xanh hoặc màu đỏ) sao cho "độ không may mắn" là nhỏ nhất có thể.
  Ví dụ: "độ không may mắn" của chuỗi BRBBBRR là \(3\) vì cặp "BB" xuất hiện \(2\) lần và "RR" xuất hiện \(1\) lần

Input

• Dòng đầu tiên chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase
• \(t\) block tiếp theo, mỗi block có dạng như sau:
  ++ Dòng đầu tiên chứa số nguyên dương \(n(1\le n\le 100)\) - Thể hiện độ dài của mảng
  ++ Dòng thứ hai chứa xâu \(s\) có độ dài \(n\) và chỉ chứa các kí tự \('?','B','R'\). Ở đây \('B'\) tượng trưng cho ô vuông màu xanh, \('R'\) tượng trưng cho ô vuông màu đỏ, '\(?\)' tượng trưng cho ô vuông trống

Output

• Ứng với mỗi testcase, in kết quả ra màn hình, nếu có nhiều đáp án thì in ra đáp án bất kỳ.

Example

2
7
?R???BR
10
?R??RB??B?

BRRBRBR
BRRBRBBRBR

Note

• Ở ví dụ đầu tiên, với cách tô như vậy (BRRBRBR), ta sẽ thu được "độ không may mắn" là 1, là giá trị nhỏ nhất mà ta có thể thu được.