CF 1373B 01 Game

Description

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 s1 and s2: 1011001→11001;

  2.delete s2 and s3: 1011001→11001;

  3.delete s4 and s5: 1011001→10101;

  4.delete s6 and s7: 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.

Solution

  思路：

判断01对数，奇数则DA，反之。

效率: 法1<法2

  方法1(模拟):

先从字符串头开始遍历，如果当前值与下一个值不一致则删除当前与下一个字符，并且统计+1，更改下标返回字符串头。特别注意字符串长度在0~2容易出错，所以需要注意循环条件。

#include<iostream>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;

int main(){
    ll t;
    cin>>t;

    while(t--){
        string temp;
        cin>>temp;
        int cnt = 0;
        for(int i = 0;i<=temp.length()-2&&temp.length()>=2;i++){
            if(temp[i]!=temp[i+1]) {
                temp.erase(i,2);
                i = -1;
                cnt++;
            }
        }
        cnt&1? cout<<"DA\n":cout<<"NET\n";
    }

    return 0;
}

  方法2(统计):

遍历统计0和1个数，数量最小的即可删除的最大值。

#include<iostream>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;

int main(){
    ll t;
    cin>>t;

    while(t--){
        string temp;
        cin>>temp;
        int c0 = 0,c1=0;
        for(int i = 0;i<temp.length();i++){
            if(temp[i]=='0') c0++;
            else c1++;
        }
        (min(c0,c1)&1)? cout<<"DA\n":cout<<"NET\n";
    }

    return 0;
}