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.io.*;
import java.util.*;

public class solution {
    static class sort implements Comparator<ArrayList<Integer>> {

        @Override
        public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
            int c = o2.get(1).compareTo(o1.get(1));
            return c;
        }
    }

    public static void merge(long arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        long L[] = new long[n1];
        long R[] = new long[n2];
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void sort(long arr[], int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(arr, l, m);
            sort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        } else return gcd(b, a % b);
    }

    public static long lcm(long a, long b) {
        long gcd = gcd(a, b);
        long pord = a * b;
        return pord / gcd;
    }

    static class graphs {
        private int V;
        private ArrayList<Integer> adj[];

        graphs(int v) {
            V = v;
            adj = new ArrayList[v];
            for (int i = 0; i < v; i++) {
                adj[i] = new ArrayList<>();
            }
        }

        void addedge(int u, int v) {
            adj[u].add(v);
        }

        void BFS(int v) {
            boolean visited[] = new boolean[V];
            Queue<Integer> Q = new LinkedList<>();
            visited[v] = true;
            Q.add(v);
            while (!Q.isEmpty()) {
                int temp = Q.peek();
                System.out.print(temp + " ");
                Q.remove();
                Iterator<Integer> it = adj[temp].listIterator();
                while (it.hasNext()) {
                    int n = it.next();
                    if (!visited[n]) {
                        visited[n] = true;
                        Q.add(n);
                    }
                }
            }
        }

        void DFSUtil(int v, boolean visited[]) {
            visited[v] = true;
            System.out.print(v + " ");
            Iterator<Integer> it = adj[v].listIterator();
            while (it.hasNext()) {
                int n = it.next();
                if (!visited[n]) {
                    DFSUtil(n, visited);
                }
            }
        }

        void DFS(int v) {
            boolean visited[] = new boolean[V];
            DFSUtil(v, visited);
        }
    }

    public static int Binaraysearch(long a[], int low, int high, long key) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] == key) {
                return mid;
            } else if (a[mid] < key) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return -1;
    }

    public static void seive(boolean prime[]) {
        Arrays.fill(prime, true);
        int n = prime.length - 1;
        for (int p = 2; p * p <= n; p++) {
            if (prime[p] == true) {
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
    }

    public static boolean random(long a, long b) {
        return a < b;
    }

    public static int subArraySum(int arr[], int n, int sum) {
        int curr_sum = arr[0], start = 0, i;
        for (i = 1; i <= n; i++) {
            // If curr_sum exceeds the sum, then remove the starting elements
            while (curr_sum > sum && start < i - 1) {
                curr_sum = curr_sum - arr[start];
                start++;
            }

            // If curr_sum becomes equal to sum, then return true
            if (curr_sum == sum) {
                int p = i - 1;
                if (p != start)
                    return 1;
            }

            // Add this element to curr_sum
            if (i < n)
                curr_sum = curr_sum + arr[i];

        }
        return 0;
    }

    static class pair {
        int x;
        int dis;

        public pair(int x, int dis) {
            this.x = x;
            this.dis = dis;
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int ii = 0; ii < t; ii++) {
            String s = br.readLine();
            int cnt1 = 0;
            int cnt0 = 0;
            for(int i=0;i<s.length();i++){
                if(s.charAt(i) == '1') {
                    cnt1++;
                }
            }
            cnt0 = s.length()-cnt1;
            int min = Math.min(cnt0,cnt1);
            if(min%2 == 0){
                System.out.println("NET");
            }
            else{
                System.out.println("DA");
            }
        }
    }
}