Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. 01 Game

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlica and Bob are playing a game.

Initially they have a binary string $$$s$$$ consisting of only characters 0 and 1.

Alice and Bob make alternating moves: Alice makes the first move, Bob makes the second move, Alice makes the third one, and so on. During each move, the current player must choose two different adjacent characters of string $$$s$$$ and delete them. For example, if $$$s = 1011001$$$ then the following moves are possible:

- delete $$$s_1$$$ and $$$s_2$$$: $$$\textbf{10}11001 \rightarrow 11001$$$;
- delete $$$s_2$$$ and $$$s_3$$$: $$$1\textbf{01}1001 \rightarrow 11001$$$;
- delete $$$s_4$$$ and $$$s_5$$$: $$$101\textbf{10}01 \rightarrow 10101$$$;
- delete $$$s_6$$$ and $$$s_7$$$: $$$10110\textbf{01} \rightarrow 10110$$$.

If a player can't make any move, they lose. Both players play optimally. You have to determine if Alice can win.

Input

First line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Only line of each test case contains one string $$$s$$$ ($$$1 \le |s| \le 100$$$), consisting of only characters 0 and 1.

Output

For each test case print answer in the single line.

If Alice can win print DA (YES in Russian) in any register. Otherwise print NET (NO in Russian) in any register.

Example

Input

3 01 1111 0011

Output

DA NET NET

Note

In the first test case after Alice's move string $$$s$$$ become empty and Bob can not make any move.

In the second test case Alice can not make any move initially.

In the third test case after Alice's move string $$$s$$$ turn into $$$01$$$. Then, after Bob's move string $$$s$$$ become empty and Alice can not make any move.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/09/2020 17:19:26 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|