#include 
#include 

int fibonaciev(int broj, int a, int b){
    if(broj == a || broj == b){
        return 1;
    }
    int c = a + b;
    if(c == broj){
        return 1;
    }
    if (c > broj){
        return 0;
    }
    fibonaciev(broj, b, c);
}



int main()
{
    int n, i;
    scanf("%d", &n);

    int niza[n];
    for(i = 0; i < n; i++){
        scanf("%d ", &niza[i]);
    }
    for(i = 0; i < n; i++){
        int f = fibonaciev(niza[i], 1, 1);

        if(f == 1){
            printf("DA ");
        }
        else if(f == 0){
            printf("NE ");
        }

    }
    return 0;
}