특별한 지불

국제 올림피아드는 참가자들만 자신의 실력을 뽐내는 자리가 아니다. 새로운 나라의 별미를 맛보고 싶어 하는 말나르 씨에게도 그렇다. 값비싼 저녁 식사에 대비하려고, 말나르 씨는 여행 전에 가진 돈의 일부를 그 나라의 화폐로 바꾸기로 했다.

그 나라에서는 모든 금액이 자연수이고, 금액을 지불하는 데 쓰이는 서로 다른 동전 가치가 $n$개 있다: $c_1 < c_2 < \dots < c_n$. 말나르 씨의 지갑은 무한한 돈의 원천으로 생각할 수 있고, 그는 각 가치의 동전을 원하는 만큼 가지고 있다. 어떤 금액을 지불하려면 말나르 씨는 합이 정확히 그 금액이 되는 동전 개수를 고른다. 또한 $c_1 = 1$이므로 어떤 금액이든 지불할 수 있다.

말나르 씨는 동전 선택에 큰 고민을 하지 않고, 어떤 금액을 지불할 때 다음 탐욕 알고리즘을 쓴다. 지불할 금액을 넘지 않는 가장 큰 동전을 고르고, 남은 금액에 대해 전부 지불할 때까지 이 과정을 반복한다. 말나르 씨는 더러운 돈이 손에 닿는 느낌을 싫어하기 때문에, 가능한 모든 금액을 탐욕 알고리즘이 최소 개수의 동전으로 지불하면 이상적이라고 생각한다. 그는 이런 동전 체계를 특별하다고 본다.

말나르 씨는 지금까지 $t$개 나라에 가 봤고, 각 나라의 동전 체계를 알고 있다. 각 나라의 동전 체계가 특별한지에 따라 "DA" 또는 "NE"를 출력하라.

첫째 줄에는 문제에서 설명한 자연수 $t$가 주어진다. ($1 \le t \le 100$)

이어서 $t$개 나라의 설명이 주어지며, 각 나라는 두 줄로 이루어진다. 첫째 줄에는 자연수 $n$이 주어지고, ($1 \le n \le 10\ 000$) 둘째 줄에는 문제에서 설명한 자연수 $1 = c_1 < c_2 < \dots < c_n \le 10\ 000$이 주어진다. 모든 나라의 $n$ 값의 합은 $10\ 000$을 넘지 않는다.

$t$개 줄에 걸쳐 각 나라의 동전 체계가 특별한지에 대한 답을 출력한다.

예제에 대한 설명: 세 번째 나라에서 금액 6은 동전 두 개로 지불할 수 있지만($6 = 3 + 3$), 탐욕 알고리즘은 동전 세 개를 쓴다($6 = 4 + 1 + 1$).