数字物理学是一系列围绕可计算宇宙概念的观点和假设。也许我们的宇宙只是运行在图灵机上的一个大型程序？宇宙的状态是有限的吗？宇宙的生命会终结吗？我们只能进行理论推测。

为了帮助推进数字物理学知识的现状，我们请你考虑一种特定的宇宙模型（我们称之为 Bitverse），并确定它的生命是会走向终结，还是会永远演化下去。

Bitverse 由一个包含 $n$ 个位（0 或 1）的序列组成。宇宙在一次被称为“位大爆炸”（Bit Bang）的事件中以特定的序列形式诞生，并从此开始离散演化。规则很简单：要确定第 $i$ 位在下一时刻的值，请查看当前时刻位置 $i-1$ 和 $i+1$ 上的位值（如果存在；否则假设它们为 0）。如果你看到恰好有一个 1，那么第 $i$ 位在下一时刻的值为 1，否则为 0。所有的位同时发生变化，因此下一状态的新值仅取决于上一状态的值。如果宇宙中只包含 0，我们认为该宇宙已经死亡。

给定“位大爆炸”时宇宙的状态，回答以下根本问题：Bitverse 会永远存活，还是最终会死亡？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各个测试用例的描述：

每个测试用例是一个长度至少为 1 且最多为 200 000 的字符串，由字符 0 或 1 组成。

输出格式

按输入中出现的顺序打印每个测试用例的答案。对于每个测试用例，如果宇宙永远存活，打印 LIVES，否则打印 DIES。

样例

输入格式 1

3
01
0010100
11011

输出格式 1

LIVES
DIES
LIVES

说明

第一个样例宇宙永远不会变成全 0 序列（它会持续翻转：01 -> 10 -> 01 ...）。第二个样例宇宙会在几步之内死亡（0010100 -> 0100010 -> 1010101 -> 0000000）。第三个样例宇宙不会发生变化。