Хто хоче жити вічно?

Цифрова фізика — це набір ідей і гіпотез, що обертаються навколо концепції обчислюваного всесвіту. Можливо, наш всесвіт — це просто велика програма, що працює на машині Тюрінга? Чи є стан всесвіту кінцевим? Чи закінчиться життя всесвіту? Ми можемо лише теоретизувати.

Щоб допомогти просунути поточний стан знань з цифрової фізики, ми просимо вас розглянути конкретну модель всесвіту (яку ми будемо називати Бітверс) і визначити, чи підходить її життя до завершення або продовжує розвиватися вічно.

Бітверс складається з послідовності n бітів (нулів або одиниць). Всесвіт виникає як особлива послідовність, у події, що називається "Удар по бітах", і з того часу розвивається дискретними кроками. Правило просте — щоб визначити наступне значення i-го біта, подивіться на поточне значення бітів у позиціях i - 1 і i + 1 (якщо вони існують; в іншому випадку припустимо, що вони дорівнюють 0). Якщо ви бачите рівно одну 1, то наступне значення i-го біта 1, в іншому випадку 0. Усі біти змінюються одночасно, тому нові значення в наступному стані залежать тільки від значень у попередньому стані. Ми вважаємо всесвіт мертвим, якщо він містить лише нулі.

Беручи до уваги стан Всесвіту в момент "Біт-вибуху", дайте відповідь на наступне фундаментальне питання: чи буде "Бітверс" жити вічно чи він зрештою помре?

Вхідні дані

Перша рядок містить кількість тестів t. Опис тестів наведено нижче:

Кожен тест являє собою рядок довжиною не менше 1 і не більше 200000 символів 0 або 1.

Вихідні дані

Для кожного тесту виведіть LIVES якщо всесвіт буде жити вічно, і DIES інакше.

Приклади

Примітка

У першому прикладі всесвіт ніколи не стане послідовністю нулів (буде продовжуватися: 01, 10, 01, ...). У другому прикладі всесвіт помре через кілька кроків (0010100, 0100010, 1010101, 0000000). У третьому прикладі всесвіт не буде змінюватися.