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: 

  1. delete s_1 and s_2: 1011001 → 11001; 
  2. delete s_2 and s_3: 1011001 → 11001; 
  3. delete s_4 and s_5: 1011001 → 10101; 
  4. delete s_6 and s_7: 1011001 → 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 ≤ t ≤ 1000) — the number of test cases.

Only line of each test case contains one string s (1 ≤ |s| ≤ 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.
import java.util.*;

import javax.swing.text.AbstractDocument.BranchElement;

import java.io.*;

public class C {
	static PrintWriter pw;
	static BufferedReader br;
	static int inf = (int) 1e9;
	static long mod = (long) 1e9 + 7;
	static int[][] memo;
	static boolean[] vis;
	static boolean[][] ok;
	static int[] a;
	static int n, m;
	static ArrayList<Integer>[] adj;
	static ArrayList<Integer> primes;
	static int[] isComposite;

	static void sieve(int N) // O(N log log N)
	{
		isComposite = new int[N + 1];
		isComposite[0] = isComposite[1] = 1; // 0 indicates a prime number
		primes = new ArrayList<Integer>();

		for (int i = 2; i <= N; ++i) // can loop till i*i <= N if primes array is not needed O(N log log sqrt(N))
			if (isComposite[i] == 0) // can loop in 2 and odd integers for slightly better performance
			{
				primes.add(i);
				if (1l * i * i <= N)
					for (int j = i * i; j <= N; j += i) // j = i * 2 will not affect performance too much, may alter in
														// modified sieve
						isComposite[j] = 1;
			}
	}

	static ArrayList<Integer> primeFactors(int N) // O(sqrt(N) / ln sqrt(N))
	{
		ArrayList<Integer> factors = new ArrayList<Integer>(); // take abs(N) in case of -ve integers
		int idx = 0, p = primes.get(idx);

		while (p * p <= N) {
			while (N % p == 0) {
				factors.add(p);
				N /= p;
			}
			p = primes.get(++idx);
		}

		if (N != 1) // last prime factor may be > sqrt(N)
			factors.add(N); // for integers whose largest prime factor has a power of 1
		return factors;
	}

	static int maxFactor(int N) // O(sqrt(N) / ln sqrt(N))
	{ // take abs(N) in case of -ve integers
		int idx = 0, p = primes.get(idx);
		int ans = -1;
		while (p * p <= N) {
			while (N % p == 0) {
				N /= p;
				ans = p;
			}
			p = primes.get(++idx);
		}

		if (N != 1) // last prime factor may be > sqrt(N)
			return N; // for integers whose largest prime factor has a power of 1
		return ans;
	}

	public static void main(String[] args) throws NumberFormatException, IOException, InterruptedException {
		br = new BufferedReader(new InputStreamReader(System.in));
		pw = new PrintWriter(System.out);

		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			char[] a = br.readLine().toCharArray();
			int c = 0;
			for (int i = 0; i < a.length; i++) {
				if (a[i] == '0')
					c++;
			}
			int min=Math.min(c, a.length-c);
			if (min%2==0)
				pw.println("NET");
			else
				pw.println("DA");

		}

		pw.flush();
	}

	static ArrayList<Integer> ans;

	static void bfs(int n) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(n);
		vis[n] = true;
		int id = 1;
		while (!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				int u = q.remove();
				if (id % 3 == 0)
					ans.add(u + 1);
				for (int v : adj[u])
					if (!vis[v]) {
						vis[v] = true;
						q.add(v);
					}
			}
			id++;
		}
	}

	static boolean valid(int x, int y) {
		return x > -1 && x < n && y > -1 && y < m;
	}

	static class pair implements Comparable<pair> {
		int x;
		int y;

		public pair(int d, int u) {
			x = d;
			y = u;
		}

		public int compareTo(pair o) {
			if (x == o.x)
				return y - o.y;
			return x - o.x;
		}

	}

	static class pair2 implements Comparable<pair2> {
		int x;
		int y;

		public pair2(int d, int u) {
			x = d;
			y = u;
		}

		public int compareTo(pair2 o) {
			return y - o.y;
		}

	}

	static int[] nxtarr() throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] a = new int[st.countTokens()];
		for (int i = 0; i < a.length; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		return a;
	}

	static long pow(long a, long e) // O(log e)
	{
		long res = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				res *= a;
			a *= a;
			e >>= 1;
		}
		return res;
	}

	static int gcd(int a, int b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}
}
