eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Коровий котильон

Коровий котильон

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

В коровьем котильоне — причудливом танце весны - участвуют коровы (обозначаются ">") и быки (обозначаются "<"), они кланяются друг другу во время танца. Схематически обозначим пару кланяющихся животных следующим образом: "> <". Иногда вторая пара скота может находиться между кланяющейся парой: "> > < <".

Иногда и большее количество коров и быков встречается на танцевальной площадке: "> > < < > <" (имеется вторая пара кланяющихся коров справа). Сложные аранжировки могут быть совершенно легальными танцевальными образованиями:

Фермер Джон замечает, что бездомная корова иногда пробирается в группу и разбалансирует ее: "> > < < < <". Это строго запрещено; Фермер Джон хочет наказать нарушителей.

Фермер Джон скопировал данные о том, как 500 коров участвуют в танцевальной линии, и задался вопросом, правильно ли уравновешена танцевальная линия (то есть весь скот может быть спарен как минимум одним способом чтобы правильно кланяться друг другу). Он скопировал только направление, в котором кланялась каждая корова, без каких-либо лишних пробелов, чтобы можно было определить, какая корова какому быку кланяется. Строки похожи на пример из предыдущего абзаца: "> > < < < <". Фермер Джон хочет чтобы Вы написали программу, определяющую правильность танцевальной линии.

Фермер Джон имеет n записей танца p_i состоящих из символов '>' и '<' различной длины k_i~(1 \le k_i \le 200). Выведите "legal" для тех строк, которые содержат правильные пары кланяющихся коров и "illegal иначе.

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

Первая строка содержит одно число n~(1 \le n \le 1000). Каждая из следующих n строк содержит число и строку из k символов '>' и '<': k_i и p_i.

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

Выведите в каждой строке "legal" или "illegal" в зависимости от того, содержит ли соответствующая входная строка допустимую конфигурацию.

Пример

Входные данные #1
2
6 >><<><
4 ><<>
Выходные данные #1
legal
illegal
Источник 2011 USACO Февраль, Бронза