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 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 200000 characters 0 or 1.

Output

For each test case, print LIVES if the universe lives forever, and DIES otherwise.

Explanation

The first example universe will never become a sequence of zeros (it will continue flipping: 01, 10, 01, ...). The second one will die in a few steps (0010100, 0100010, 1010101, 0000000). The third one does not change.