← 返回题目列表

Codeforces · 1373/B

B. 01 游戏

中文机器翻译题面 查看原题

艾丽卡和鲍勃正在玩游戏。

最初它们有一个仅由字符 0 和 1 组成的二进制字符串 $$$s$$$。

Alice 和 Bob 交替着棋:Alice 迈出第一步,Bob 迈出第二步,Alice 迈出第三步,以此类推。在每次移动过程中,当前玩家必须选择字符串 $$$s$$$ 中两个不同的相邻字符并将其删除。例如,如果 $$$s = 1011001$$$ 则可以进行以下移动:

1、删除$$$s_1$$$和$$$s_2$$$:$$$\textbf{10}11001 \rightarrow 11001$$$;
2、删除$$$s_2$$$和$$$s_3$$$:$$$1\textbf{01}1001 \rightarrow 11001$$$;
3、删除$$$s_4$$$和$$$s_5$$$:$$$101\textbf{10}01\rightarrow 10101$$$;
4.删除$$$s_6$$$和$$$s_7$$$:$$$10110\textbf{01}\rightarrow 10110$$$。

如果玩家无法采取任何行动,他们就输了。两名球员都发挥最佳。你必须确定爱丽丝是否能获胜。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例只有一行包含一个字符串 $$$s$$$ ($$$1 \le |s| \le 100$$$),仅由字符 0 和 1 组成。

输出

对于每个测试用例,在单行中打印答案。

如果 Alice 可以在任何寄存器中赢得打印 DA(俄语为“是”)。否则在任何寄存器中打印 NET(俄语为“NO”)。

示例

输入 #1

3
01
1111
0011

输出 #1

DA
NET
NET

注意

在 Alice 的移动字符串 $$$s$$$ 变空且 Bob 无法进行任何移动后的第一个测试用例中。

在第二个测试用例中,Alice 最初无法做出任何动作。

在 Alice 的移动字符串 $$$s$$$ 变成 $$$01$$$ 之后的第三个测试用例中。然后,在 Bob 的移动字符串 $$$s$$$ 变空之后,Alice 无法进行任何移动。