Extraordinary Payment

International olympiads are not only a chance for contestants to show their knowledge. They are also a chance for Mr. Malnar, who eagerly looks forward to trying the specialties of a new country. To be ready to pay for expensive dinners, he decided to convert part of his money into the currency of the country he is about to visit.

In that country all amounts are positive integers, and there are $n$ different coin values $c_1 < c_2 < \dots < c_n$ used to pay amounts. Mr. Malnar's wallet can be thought of as an infinite source of money, where he has arbitrarily many coins of each value at his disposal. To pay an amount, Mr. Malnar chooses some number of coins whose sum is exactly that amount. In addition, $c_1 = 1$, which guarantees that every amount can be paid.

Mr. Malnar does not bother much with choosing coins, so he uses the following greedy algorithm to pay an amount: he picks the largest coin that does not exceed the amount to be paid, and repeats this procedure on the remaining amount until he has paid it in full. Since Mr. Malnar dislikes the feel of dirty money in his hands, it would be ideal for him if his greedy algorithm paid every possible amount using the minimum number of coins. He considers such a coin system extraordinary.

Mr. Malnar has so far visited $t$ countries, and he knows the coin system of each of them. For each country, print "DA" or "NE" depending on whether the coin system of that country is extraordinary.

The first line contains the positive integer $t$ from the statement. ($1 \le t \le 100$)

What follows are $t$ descriptions of countries, each described by two lines. The first line contains the positive integer $n$, ($1 \le n \le 10\ 000$) and the second line contains the positive integers $1 = c_1 < c_2 < \dots < c_n \le 10\ 000$ from the statement. The sum of all values of $n$ over all countries does not exceed $10\ 000$.

Print $t$ lines, the answer for each country to the question of whether its coin system is extraordinary.

Explanation of the sample: in the third country, the amount 6 can be paid using two coins ($6 = 3 + 3$), but the greedy algorithm uses three coins ($6 = 4 + 1 + 1$).