Кто хочет жить вечно?

Цифровая физика - это набор идей и гипотез, которые вращаются вокруг концепции вычислимой вселенной. Может быть, наша вселенная - это просто большая программа, работающая на машине Тьюринга? Является ли состояние вселенной конечным? Закончится ли жизнь вселенной? Мы можем только теоретизировать.

Чтобы помочь продвинуть текущее состояние знаний по цифровой физике, мы просим Вас рассмотреть конкретную модель вселенной (которую мы будем называть Битверс) и определить, подходит ли ее жизнь к завершению или продолжает развиваться вечно.

Битверс состоит из последовательности 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). В третьем примере вселенная не будет изменяться.