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

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

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

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

Фермер Джон скопировал данные о том, как $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" в зависимости от того, содержит ли соответствующая входная строка допустимую конфигурацию.

Примеры