Who Wants to Live Forever?

Digital physics is a collection of ideas and hypotheses built around the notion of a computable universe. Perhaps our universe is just a large program running on a Turing machine? Is the state of the universe finite? Will the universe eventually end? For now we can only theorize.

To push the frontier of digital physics a little further, consider a specific toy model of the universe — we will call it Bitverse — and decide whether its life comes to an end or it keeps evolving forever.

Bitverse is a single row of $n$ bits, each either $0$ or $1$. The universe comes into being as one particular row of bits — an event we call the Bit Bang — and from then on it evolves in discrete steps.

The rule is simple. To compute the next value of the $i$-th bit, look at the current values of its neighbours at positions $i-1$ and $i+1$ (a neighbour that falls outside the row is treated as $0$). If exactly one of the two neighbours is $1$, the next value of the $i$-th bit is $1$; otherwise it is $0$. Every bit is updated simultaneously, so the next state depends only on the previous state.

The universe is dead once it consists solely of zeros.

Given the state of Bitverse at the Bit Bang, answer the fundamental question: will Bitverse live forever, or will it eventually die?

The first line contains the number of test cases $T$.

Each of the following $T$ lines contains one test case: a string of between $1$ and $200\,000$ characters, each either 0 or 1, describing the initial state of a Bitverse.

For each test case print a single line: LIVES if that universe evolves forever, or DIES if it eventually becomes all zeros. Print the answers in the same order as the input.

The first sample universe never becomes all zeros; it keeps oscillating: 01 → 10 → 01 → … . The second one dies after a few steps: 0010100 → 0100010 → 1010101 → 0000000. The third one is a fixed point and never changes.