리버시

시간 제한1초메모리 제한512 MB

요약

N행 M열 보드에서 2x1 돌을 두는 선수와 1x1 돌을 두는 후공이 최선을 다할 때 후공의 승, 패, 무승부를 판정합니다.

문제

리버와 스캐럽의 수를 과소평가해 집과 집 안의 전 재산을 잃은 동호는 빚더미에 앉게 되었다. 동호는 빚을 갚기 위해 게임을 잘하는 시이를 「세계 리버시 대회」에 출전시켜 시이의 상금 일부를 받으려고 한다.

리버시는 오델로라고도 불리는 게임이다. 흑과 백이 번갈아 돌을 놓고, 게임이 끝났을 때 돌이 더 많은 쪽이 이긴다. 이 문제와는 관련이 적으므로 자세한 규칙은 생략한다.

이 대회에서 하는 리버시는 일반적인 리버시와 다르다. 돌을 뒤집을 수 없다.

돌을 뒤집는 것이 게임의 핵심인데 뒤집지 못하면 게임이 매우 재미없어진다. 그래서 대회에서는 다음 규칙을 사용한다.

보드는 $N$ 행 $M$ 열의 격자이다.
선공은 $2 \times 1$ 크기의 돌을, 후공은 $1 \times 1$ 크기의 돌을 쓴다. 돌은 그대로 놓거나 90도 회전시켜 놓을 수 있다.
선공부터 번갈아 가며 보드에 자신의 돌을 하나씩 놓는다. 한 칸에는 최대 하나의 돌만 위치할 수 있다.
둘 중 한 명이 돌을 더 이상 놓을 수 없으면, 남은 한 명이 남은 공간을 자신의 돌로 최대한 많이 채운 뒤 게임이 끝난다.
게임이 끝나면 보드에서 자신의 돌이 차지한 공간이 더 많은 플레이어가 이긴다. 공간이 같으면 무승부이다.

출전자들은 모두 뛰어난 실력을 갖추고 있어서 이기기 위해 항상 최선의 수를 둔다. 시이는 동전 던지기에서 이길 운이 없으므로 항상 후공을 잡는다.

시이가 대회에서 좋은 성적을 거둬 동호가 빚을 모두 갚을 수 있을지 알아보자.

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이후 $T$ 개의 줄에 공백으로 구분된 $N$ 과 $M$ 이 주어진다.

각 테스트 케이스마다 시이가 이기면 W, 지면 L, 무승부이면 D를 공백이나 줄바꿈 없이 이어서 출력한다.