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.*; 
//import javafx.util.*; 
import java.math.*;
//import java.lang.*;
public class Main 
{ 
    
   // static int n;
//  static HashSet<Integer> adj[];

   // static int dist[];
   // static int remove[];
//    static boolean isLeaf[];
  //   static Long dp[][];
   // static int arr[];
  //  static boolean ok;
    // static long arr[];
    // static long sum[];
  //  static boolean ok;
    static long mod=1000000007;
 //   static HashSet<Integer> adjacency[];
    static final long oo=(long)1e18;
    public static void main(String[] args) throws IOException { 
    //    Scanner sc=new Scanner(System.in);
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        br = new BufferedReader(new InputStreamReader(System.in));
        int test=nextInt();
     //  int test=1;
        
        outer: while(test--!=0){
            String s=next();
            int n=s.length();
            int count=0;          
            int zero=0;  
            for(int i=0;i<n;i++){
                if(s.charAt(i)=='0'){
                    zero++;
                }
                else{
                    count++;
                }
            }
            count=Math.min(zero,count);
         //   pw.println(count);
            if(count%2==0){
                pw.println("NET");
            }
            else{
                pw.println("DA");
            }

        }
           
        pw.close();
    }
    static class Pair implements Comparable<Pair>{
        int x;int y;
        Pair(int x,int y){
          //  this.index=index;
            this.x=x;
            this.y=y;
            //this.z=z;
        }   
        public int compareTo(Pair p){
            return x-p.x;
        }
    }
   static void update(long tree[],int idx,long val){
        //println(idx);
        while(idx<1000006){
            
            tree[idx]+=val;
            idx+=(idx)&(-idx);
        }
    }   
    static long sum(long tree[],int idx){
        long sum=0;
        while(idx>0){
           
            sum+=tree[idx];
            idx-=(idx)&(-idx);
        }
        return sum;
    }
    public static BufferedReader br;
    public static StringTokenizer st;
    public static String next() {
        while (st == null || !st.hasMoreTokens()) {
       try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
        return st.nextToken();
    }
 
    public static Integer nextInt() {
        return Integer.parseInt(next());
    }
    public static Long nextLong() {
        return Long.parseLong(next());
    }
 
    public static Double nextDouble() {
        return Double.parseDouble(next());
    }
    // static class Pair{
    //     int x;int y;
    //     Pair(int x,int y,int z){
    //         this.x=x;
    //         this.y=y;
    //        // this.z=z;
    //      //   this.z=z;
    //       //  this.i=i;
    //     }
    // }
    // static class sorting implements Comparator<Pair>{
    //     public int compare(Pair a,Pair b){
    //         //return (a.y)-(b.y);
    //         if(a.y==b.y){
    //             return -1*(a.z-b.z);
    //         }
    //         return (a.y-b.y);
    //     }
   // }

    static long ncr(long n,long r){
        
        if(r==0)
            return 1l;
        long val=ncr(n-1,r-1);
        val=(n*val);
        val=(val/r);
        return val;
    }

    public static int[] na(int n)throws IOException{
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = nextInt();
        return a;
    }
    static class query implements Comparable<query>{
        int l,r,idx,block;
        static int len;
        query(int l,int r,int i){
            this.l=l;
            this.r=r;
            this.idx=i;
            this.block=l/len;
        }   
        public int compareTo(query a){
            return block==a.block?r-a.r:block-a.block;
        }
    }
    
    // static class sorting implements Comparator<Pair>{  
    //     public int compare(Pair a1,Pair a2){  
    //         if(o1.a==o2.a)
    //             return (o1.b>o2.b)?1:-1;  
    //         else if(o1.a>o2.a)  
    //             return 1;  
    //         else  
    //             return -1;  
    //     }
    // }  
    static boolean isPrime(int n) { 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
        if (n % 2 == 0 ||  
            n % 3 == 0) 
            return false; 
      
        for (int i = 5; 
                 i * i <= n; i = i + 6) 
            if (n % i == 0 || 
                n % (i + 2) == 0) 
                return false; 
      
        return true; 
    } 
    static int gcd(int a, int b) { 
      if (b == 0) 
        return a; 
      return gcd(b, a % b);  
    }  
    // To compute x^y under modulo m 
    static long power(long x, long y, long m){ 
        if (y == 0) 
            return 1;      
        long p = power(x, y / 2, m) % m; 
        p = (p * p) % m; 
      
        if (y % 2 == 0) 
            return p; 
        else
            return (x * p) % m; 
    }
    static long fast_pow(long base,long n,long M){
        if(n==0)
           return 1;
        if(n==1)
        return base;
        long halfn=fast_pow(base,n/2,M);
        if(n%2==0)
            return ( halfn * halfn ) % M;
        else
            return ( ( ( halfn * halfn ) % M ) * base ) % M;
    }
       static long modInverse(long n,long M){
        return fast_pow(n,M-2,M);
    }
    // (1,1)   

    //     (3,2)   (3,5)

} 