FIFA 월드컵

이집트가 1990년 이후 처음으로 FIFA 월드컵에 진출했다.

월드컵에서는 팀을 4팀씩 조로 나눈다. 이 문제는 조의 팀 수를 N으로 일반화하고, 한 조의 경기를 시뮬레이션한다. 팀은 1번부터 N번까지 번호가 붙는다. 조별리그 규칙은 실제 규칙과 조금 다르며 다음과 같다.

1. 조는 N − 1라운드를 치르고, 라운드마다 N/2경기가 열린다. 이 문제에서 N은 항상 짝수다.
2. 각 팀은 라운드마다 한 경기를 치르고, 서로 다른 두 팀은 N − 1라운드 동안 정확히 한 번씩 대결한다.
3. 이긴 팀은 3점, 진 팀은 0점을 얻는다. 무승부면 두 팀 모두 1점을 얻는다.
4. N − 1라운드가 끝나면 각 팀의 승점을 합산한다. N이 4보다 커도 상위 2팀이 다음 단계에 진출한다.
5. 상위 2팀과 승점이 같은 팀도 진출한다. 득점은 고려하지 않는다. 모든 팀의 승점이 같다면 조 전체가 진출한다.

처음 N − 2라운드의 결과가 주어진다. 각 팀에 대해 남은 라운드의 결과와 관계없이 진출할 가능성이 남아 있는지, 아니면 반드시 탈락하는지 판단한다.

첫 줄에 테스트 케이스 수 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 팀 수 N(4 ≤ N ≤ 1,000)을 담은 줄로 시작한다. 이어서 처음 N − 2라운드의 경기 결과가 경기마다 한 줄씩, 총 (N − 2) × (N/2)줄 주어진다.

경기 줄은 정수 A와 B(1 ≤ A < B ≤ N)로 시작하고, 공백 뒤에 문자 하나가 온다. 'W'는 A 팀의 승리, 'L'은 B 팀의 승리, 'D'는 무승부다.

각 팀은 정확히 N − 2경기에 출전하며, 같은 두 팀이 두 번 이상 대결하지 않는다.

테스트 케이스마다 N글자 문자열을 한 줄에 출력한다. i번째 글자는 i번 팀에 대응한다. 다음 단계에 진출할 가능성이 남아 있으면 '1', 어떤 경우에도 탈락이 확정되면 '0'을 출력한다.

첫 번째 테스트 케이스에서 1번과 3번 팀은 지금까지 6점을, 2번과 4번 팀은 0점을 얻었다. 마지막 라운드의 결과와 관계없이 2번과 4번 팀은 상위 2팀에 들 수 없다.

두 번째 테스트 케이스에서는 모든 경기가 무승부로 끝났으므로 모든 팀에 진출 가능성이 남아 있다.