Задачи
Коровий котильон
Коровий котильон
В коровьем котильоне --- причудливом танце весны - участвуют коровы (обозначаются ">") и быки (обозначаются "<"), они кланяются друг другу во время танца. Схематически обозначим пару кланяющихся животных следующим образом: "> <". Иногда вторая пара скота может находиться между кланяющейся парой: "> > < <".
Иногда и большее количество коров и быков встречается на танцевальной площадке: "> > < < > <" (имеется вторая пара кланяющихся коров справа). Сложные аранжировки могут быть совершенно легальными танцевальными образованиями:
\includegraphics{https://static.eolymp.com/content/6c/6c28f907d30704f203a66289f6c73749bd534cea.gif}
Фермер Джон замечает, что бездомная корова иногда пробирается в группу и разбалансирует ее: "> > < < < <". Это строго запрещено; Фермер Джон хочет наказать нарушителей.
Фермер Джон скопировал данные о том, как $500$ коров участвуют в танцевальной линии, и задался вопросом, правильно ли уравновешена танцевальная линия (то есть весь скот может быть спарен как минимум одним способом чтобы правильно кланяться друг другу). Он скопировал только направление, в котором кланялась каждая корова, без каких-либо лишних пробелов, чтобы можно было определить, какая корова какому быку кланяется. Строки похожи на пример из предыдущего абзаца: "> > < < < <". Фермер Джон хочет чтобы Вы написали программу, определяющую правильность танцевальной линии.
Фермер Джон имеет $n$ записей танца $p_i$ состоящих из символов '>' и '<' различной длины $k_i~(1 \le k_i \le 200)$. Выведите "\textbf{legal}" для тех строк, которые содержат правильные пары кланяющихся коров и "\textbf{illegal} иначе.
\InputFile
Первая строка содержит одно число $n~(1 \le n \le 1000)$. Каждая из следующих $n$ строк содержит число и строку из $k$ символов '>' и '<': $k_i$ и $p_i$.
\OutputFile
Выведите в каждой строке "\textbf{legal}" или "\textbf{illegal}" в зависимости от того, содержит ли соответствующая входная строка допустимую конфигурацию.
Входные данные #1
2 6 >><<>< 4 ><<>
Выходные данные #1
legal illegal