30927번 - 서바이벌 게임

문제

$n$ 명의 벚꽃소녀들이 $n$ 억원의 상금이 걸린 의문의 서바이벌에 참가하였다. 벚꽃소녀들이 참가할 서바이벌 게임은 폭탄 해체 게임 이다. 게임을 위해, $n$ 명의 벚꽃소녀들은 한 줄에 일렬로 서 있다. 벚꽃소녀들은 줄의 맨 앞부터 시작하여 1,ドル 2, \ldots, n$ 으로 번호가 붙어 있다.

각 벚꽃소녀들은 게임의 주최로부터 모자를 받아서 머리 위에 썼다. 어떤 모자들은 평범하지만, 어떤 다른 모자들은 폭탄이 붙어 있다. 폭탄이 붙지 않은 모자를 'R', 폭탄이 붙은 모자를 'B' 라고 하자. $i$ 번 벚꽃소녀는 자신의 앞에 있는 모든 벚꽃소녀의 모자를 볼 수 있다. 다시 말해, 1ドル \le j < i$ 를 만족하는 모든 $j$ 번 벚꽃소녀의 모자에 폭탄이 달려 있는 지를 볼 수 있다. 하지만, 자신의 모자, 그리고 자신의 뒤에 있는 벚꽃소녀의 모자는 볼 수 없다.

게임의 주최는 맨 처음 폭탄이 붙어 있는 모자의 개수를 모든 벚꽃소녀에게 알린다. 이후, 9999ドル^{9999^{9999}}$ 번의 라운드 를 진행한다. 각 라운드는 다음과 같다:

• 각 벚꽃소녀는 게임 전에 자신에게 주어진 리모콘을 통해서 자신의 모자에 폭탄이 붙어 있는지의 여부를 주최에게 알린다. 대답은 예, 아니오, 알 수 없음 의 세 종류 중 하나이다. 이 정보는 주최에게만 전해지며, 다른 벚꽃소녀가 염탐할 수 없다. 벚꽃소녀들은 잘못된 대답을 할 경우 즉시 탈락하기 때문에 폭탄 존재 여부가 확실할 때만 정확하게 대답할 것이며, 게임에서 빨리 탈출하고 싶기 때문에 폭탄 존재 여부가 확실해 지면 즉시 대답할 것이다. 모든 벚꽃소녀는 위 조건에 맞게 최적으로 행동하며, 모든 벚꽃소녀가 최적으로 행동한다는 사실이 모든 벚꽃소녀들에게 알려져 있다.
• 탈락한 벚꽃소녀가 없다면, 예나 아니오로 대답한 벚꽃소녀들은 줄에서 나가 게임에서 탈출한다. 이후, 전광판을 통해서 이번 라운드에 게임에서 탈출한 벚꽃소녀들의 번호가 모두 공개된다. 번호만 공개되는 것이지, 해당 벚꽃소녀의 모자에 폭탄이 있었는지 여부가 공개되지는 않는다.

모든 라운드가 끝난 이후에도 자신의 모자의 종류를 알지 못하는 벚꽃소녀들은 탈락한다.

당신은 모든 벚꽃소녀의 운명을 맞추어야 한다 - 모든 $n$ 명의 벚꽃소녀들에 대해서, 해당 벚꽃소녀가 이번 게임에서 탈출할 수 있는지를 판별하라.

이 문제는 $T$ 개의 테스트 케이스가 한 입력에 주어진다.

입력

첫 번째 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이후 다음과 같은 형태의 입력이 $T$ 개 주어진다.

첫 번째 줄에 정수 $n$ 이 주어진다.

두 번째 줄에 길이 $n$ 의 문자열이 주어진다. 문자열의 $i$ 번 문자는 $i$ 번 벚꽃소녀의 모자의 상태를 표현한다.

출력

$T$ 개의 줄에 걸쳐 각 테스트 케이스의 정답을 출력하라.

각 테스트 케이스에 대해, 길이 $n$ 의 문자열 하나를 출력하라. 문자열의 $i$ 번 문자는 $i$ 번 벚꽃소녀가 탈출할 수 있다면 1, 탈락한다면 0이다.

제한

• 1ドル \le T \le 100$
• 1ドル \le n \le 100$
• 주어지는 문자열은 'R', 'B' 로 이루어져 있다.

힌트