누가 영원히 살고 싶은가?

디지털 물리학은 계산 가능한 우주라는 개념을 중심으로 한 여러 아이디어와 가설의 모음입니다. 어쩌면 우리 우주도 튜링 기계 위에서 돌아가는 거대한 프로그램일지도 모릅니다. 우주의 상태는 유한할까요? 우주의 수명은 언젠가 끝날까요? 지금으로서는 그저 이론을 세워 볼 수 있을 뿐입니다.

디지털 물리학의 지식을 한 걸음 더 넓히기 위해, 우주의 특정한 장난감 모형 하나를 생각해 봅시다. 이 모형을 비트버스(Bitverse)라고 부르겠습니다. 그리고 이 우주의 생명이 끝나는지, 아니면 영원히 진화를 계속하는지 판정해 봅시다.

비트버스는 각각 $0$ 또는 $1$인 $n$개의 비트가 한 줄로 늘어선 것입니다. 이 우주는 어떤 하나의 비트 배열로 탄생하며(이 사건을 빅뱅, 즉 비트 뱅이라 부릅니다), 그 이후로는 이산적인 단계를 거쳐 진화합니다.

규칙은 간단합니다. $i$번째 비트의 다음 값을 구하려면, 현재 이웃한 위치 $i-1$과 $i+1$의 값을 봅니다(줄 밖으로 벗어나는 이웃은 $0$으로 간주합니다). 두 이웃 중 정확히 하나만 $1$이면 $i$번째 비트의 다음 값은 $1$이고, 그렇지 않으면 $0$입니다. 모든 비트는 동시에 갱신되므로, 다음 상태는 오직 이전 상태에만 의존합니다.

우주가 모두 $0$으로만 이루어지면 그 우주는 죽은 것으로 봅니다.

빅뱅 순간의 비트버스 상태가 주어질 때, 근본적인 질문에 답하세요. 비트버스는 영원히 살아남을까요, 아니면 언젠가 죽을까요?

첫째 줄에 테스트 케이스의 수 $T$가 주어집니다.

이어지는 $T$개의 줄에는 각각 하나의 테스트 케이스가 주어집니다. 각 테스트 케이스는 길이가 $1$ 이상 $200\,000$ 이하인 문자열이며, 각 문자는 0 또는 1로 비트버스의 초기 상태를 나타냅니다.

각 테스트 케이스마다 한 줄에 답을 출력합니다. 그 우주가 영원히 진화하면 LIVES를, 언젠가 모두 $0$이 되면 DIES를 출력합니다. 답은 입력에 주어진 순서대로 출력합니다.

첫 번째 예제 우주는 결코 모두 $0$이 되지 않고 계속 진동합니다: 01 → 10 → 01 → … . 두 번째 예제는 몇 단계 만에 죽습니다: 0010100 → 0100010 → 1010101 → 0000000. 세 번째 예제는 고정점이라 전혀 변하지 않습니다.