Alica 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.

Difficulty: interview

Starter code:

Solutions:
t = int(input())

for _ in range(t):
    s = [int(i) for i in input()]
    ct0 = 0
    ct1 = 0
    
    for i in s:
        if i == 1:
            ct1 += 1
        else:
            ct0 += 1
            
    ct = min(ct0, ct1)
    if ct%2:
        print("DA")
    else:
        print("NET")

from collections import deque
from sys import stdin, stdout  
import math
input = stdin.readline
#print = stdout.write

for _ in range(int(input())):
    x = input()
    first = x.count('1')
    second = x.count('0')
    print('DA' if min(first, second) % 2 else 'NET')


for _ in range(int(input())):
    ar = list(input())
    x, y = ar.count('0'), ar.count('1')
    if min(x, y) % 2 == 1:
        print('DA')
    else:
        print('NET')

t=int(input())
for _ in range(t):
    s=input()
    n=len(s)
    count0=0
    count1=0
    for i in range(n):
        if s[i]=='0':
            count0+=1
        else:
            count1+=1
    if min(count0,count1)%2==0:
        print('NET')
    else:
        print('DA')

for _ in range(int(input())):
    # a, b, c = map(int, input().split())
    # n = int(input())
    # arr = list(map(int, input().split()))
    s = input()
    a = s.count('1')
    b = s.count('0')
    x = min(a, b)
    if x % 2 == 0:
        print('NET')
    else:
        print('DA')


for _ in range(int(input())):
    s = input()
    o = 0
    z = 0
    for i in range(len(s)):
        if s[i] == '0':
            z += 1
        else:
            o += 1
    if min(o, z) % 2 == 1:
        print('DA')
    else:
        print('NET')

for _ in range(int(input())):
    tekst = input()
    i_zer, i_jeden = tekst.count("0"), 0
    i_jeden = len(tekst) - i_zer
    mniejsze = min(i_zer, i_jeden) 
    if mniejsze % 2 == 0:
        print("NET")
    else:
        print("DA")

def solve():
    s = input()
    u = min(s.count('0'), s.count('1'))
    if u % 2 == 1:
        print('DA')
    else:
        print('NET')
t = int(input())
for _ in range(t):
    solve()

def solve():
    s = input()
    z = 0
    o = 0
    for i in s:
        if i == "1":
            o += 1
        else:
            z += 1
    c = min(o,z)
    if c%2 == 0:
        print("NET")
    else:
        print("DA")
for i in range(int(input())):
    solve()

ans = []
for _ in range(int(input())):
    u = list(map(int, list(input())))
    a1 = sum(u)
    a0 = len(u) - a1
    d = min(a0, a1)
    if d % 2 == 1:
        ans.append('DA')
    else:
        ans.append('NET')
print('\n'.join(ans))


z=input

"""

n=int(z())

for i in range(n):

x=int(z())

l=list(map(int,z().split()))

a,b=map(int,z().split())

x=z()

"""
n=int(z())
for i in range(n):
        x=z()
        one=x.count('1')
        ze=x.count('0')
        p=min(one,ze)
        if p%2!=0:
                print('DA')
        else:
                print('NET')


t = int(input())
for _ in range(t):
    s = input()
    cnt1 = 0
    cnt2 = 0
    for i in s:
        if i == '1':
            cnt1+=1
        else:
            cnt2 += 1
    if min(cnt1, cnt2) % 2 == 1:
        print("DA")
    else:
        print("NET")

from sys import exit,stdin,stderr
def rl():
    return [int(w) for w in stdin.readline().split()]

T, = rl()
for _ in range(T):
    s = input().rstrip()
    c0 = len([c for c in s if c == '0'])
    c1 = len([c for c in s if c == '1'])
    print(['NET', 'DA'][min(c0, c1) & 1])


def sol():
    s=input()
    on=0
    zr=0
    tot=0
    for n in s:
        if n=='1':
            if zr==0:
                on+=1
            else:
                zr-=1
                tot+=1
        else:
            if on==0:
                zr+=1
            else:
                on-=1
                tot+=1
    if tot%2:
        print('DA')
    else:
        print('NET')

for n in range(int(input())):
    sol()

import sys
# input = sys.stdin.buffer.readline
def I(): return(list(map(int,input().split())))
def sieve(n):
	a=[1]*n
	for i in range(2,n):
	    if a[i]:
	        for j in range(i*i,n,i):
	            a[j]=0
	return a

for __ in range(int(input())):
	# n=int(input())
	s=input()
	if min(s.count("0"),s.count("1"))%2==0:
		print("NET")
	else:
		print("DA")
		




import math
for _ in range(int(input())):
    a = list(input())
    c1 = a.count('0')
    c2 = a.count('1')
    if min(c1,c2)%2==1:
        print('DA')
    else:
        print('NET')

for _ in range (int(input())):
    s=input()
    one = s.count('1')
    zero=s.count('0')
    total = min(one,zero)
    if total%2==1:
        print('DA')
    else:
        print('NET')


tt = int(input())

for loop in range(tt):

    z = 0
    o = 0

    s = input()
    for i in s:
        if i == "0":
            z += 1
        else:
            o += 1

    if min(z,o) % 2 == 0:
        print ("NET")
    else:
        print ("DA")


import sys
INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br


"""
Facts and Data representation
Constructive? Top bottom up down
"""
def solve():
  s = input()
  stack = []
  cnt = 0
  for i in range(len(s)):
    if stack and stack[-1] != s[i]:
      cnt += 1
      stack.pop()
      continue
    stack.append(s[i])
  if cnt % 2:
    print('DA')
  else:
    print('NET')

t, = I()
while t:
  t -= 1
  solve()

for _ in range(int(input())):
    s=input()
    a=s.count("1")
    b=s.count("0")
    x=min(a,b)
    if x%2==1:
        print("DA")
    else:
        print("NET")


for test_i in range(int(input())):
    s = input()
    print('DA' if min(s.count('0'), s.count('1')) % 2 else 'NET')

t =  int(input())
while(t>0):
    s= input()
    s0 = s.count('0')
    s1 = s.count('1')
    mini = min(s0,s1)
    if mini%2==0:
        print('NET')
    else:
        print('DA')
    t-=1

for _ in range(int(input())):
    s = input()
    ch0 = 0
    ch1 = 0
    for i in s:
        if i == '1':
            ch1 += 1
        else:
            ch0 += 1
    ans = min(ch0, ch1)
    if ans % 2 == 0:
        print('NET')
    else:
        print('DA')