Коров'ячий котильйон

У коров'ячому котильйоні — химерному весняному танці — беруть участь корови (позначаються ">") і бики (позначаються "<"), які вклоняються один одному під час танцю. Схематично пара вклоняючихся тварин позначається як "> <". Іноді між вклоняючоюся парою може бути інша пара: "> > < <".

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

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

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

Приклади