Щёлк

В книге Мартина Гарднера «Математические новеллы» описана игра «Щелк!». Цитируем по русскому переводу (издательство «Мир», 1974).

Для игры в «Щелк!» необходимо запастись фишками (если фишек нет, можно играть на бумаге в клеточку, ставя и зачеркивая нолики). Фишки выстраивают в форме прямоугольника. Играют в «Щелк!» вдвоем, игроки делают ходы по очереди.

Каждый ход состоит в следующем. Игрок выбирает любую фишку, мысленно проводит через ее центр два взаимно перпендикулярных луча: один горизонтальный на восток от центра фишки и один вертикальный на север от него. Все фишки, оказавшиеся внутри прямого угла, образованного лучами, игрок снимает. Таки образом, игроки по очереди как бы откусывают прямоугольные куски от прямоугольного же крекера, вгрызаясь в него с северо-востока (щелканье их «челюстей» звучит в названии игры). Выигрывает тот, кто заставит противника взять «отравленную» фишку, стоящую в левом нижнем углу.

Рис 1. Пример партии в "Щелк!". В исходной позиции фишки расставлены в виде прямоугольника 5х6

Таковы правила. А теперь представьте себе ситуацию. Двое начали играть в «Щелк!» на поле 10x10. Вы видите промежуточную позицию, создавшуюся по прошествии некоторого времени после начала игры. Противники в глубокой задумчивости. Чем закончится игра – непонятно, все-таки живые люди играют, а не машины… Кстати, о компьютерах. Напишите программу, которая для каждой позиции выдавала бы вердикт, имеет ли в ней игрок, чья сейчас очередь хода, возможность выиграть при любой (даже наилучшей) игре противника.

Входные данные

На входе в программу поступает несколько позиций, для каждой из которых нужно указать исход игры при наилучшей игре обоих партнеров. Первая строка входного файла содержит общее количество M тестов. Затем идут M строк, в каждой из которых находится описание одной позиции. Каждая из них представляет из себя десять чисел, разделенных пробелами, которые указывают, сколько фишек находится в каждом столбце (столбцы перенумерованы слева направо).

Выходные данные

Программа должна выдавать на выходе M строк, каждая из которых содержит либо букву W, если игрок, чья сейчас очередь хода, имеет возможность выигрыша при любой игре противника, либо букву L, если противник может добиться выигрыша для себя.

Пример

Input:
3
2 2 0 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0 0 0
10 10 10 10 10 10 10 10 10 10

Output:
W
L
W

Автор задачи: Филимоненков Д.О.