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

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

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

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

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

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

Первая строка содержит одно число n (1 ≤ n ≤ 1000). Каждая из следующих n строк содержит число и строку из K символов '>' and '<': Ki и Pi.

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

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