Who wants to live forever?

Time Limit: 5 Seconds    Memory Limit: 131072 KB

Digital physics is a set of ideas and hypotheses that revolve around the concept of computable universe. Maybe our universe is just a big program running on a Turing machine? Is the state of the universe finite? Will the life of the universe end? We can only theorize.

In order to help advance the current state of knowledge on digital physics, we ask you to consider a particular model of the universe (which we shall call Bitverse) and determine whether its life comes to a conclusion or continues evolving forever.

Bitverse consists of a single sequence of n bits (zeros or ones). The universe emerges as a particular sequence, in an event called the “Bit Bang”, and since then evolves in discrete steps. The rule is simple—to determine the next value of the i-th bit, look at the current value of the bits at positions i−1 and i+1 (if they exist; otherwise assume them to be 0). If you see exactly one 1, then the next value of the i-th bit is 1, otherwise it is 0. All the bits change at once, so the new values in the next state depend only on the values in the previous state. We consider the universe dead if it contains only zeros.

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

Input

The first line of the input contains the number of test cases T. The descriptions of the test cases follow:

Each test case is a string of at least 1 and at most 200 000 characters 0 or 1.

Output

Print the answers to the test cases in the order in which they appear in the input. For each test case, print LIVES if the universe lives forever, and DIES otherwise.

Sample Input

3
01
0010100
11011

Sample Output

LIVES
DIES
LIVES

Submit

Source: Central European Regional Contest 2012