International Olympiads are not just an opportunity for contestants to demonstrate their knowledge, but also for Mr. Malnar, who eagerly looks forward to trying specialties in a new country. To be prepared to pay for expensive dinners, he decided to convert some money into the currency of the upcoming country before his trip.
In that country, all amounts are natural numbers, and there are $n$ different coin values $c_1 < c_2 < \dots < c_n$ used for paying amounts. Mr. Malnar's wallet can be imagined as an infinite source of money, where he has an arbitrary number of coins of each value at his disposal. To pay an amount, Mr. Malnar will choose a number of coins that sum up to the exact amount. Additionally, $c_1 = 1$ holds, which ensures that every amount can be paid.
Mr. Malnar does not bother too much with the choice of coins, so he uses the following greedy algorithm to pay any amount – he chooses the largest coin that does not exceed the amount that needs to be paid, and for the remaining part of the amount, he repeats this process until he has paid it in full. Since Mr. Malnar does not like the feeling 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. Mr. Malnar considers such a coin system "extraordinary".
Mr. Malnar has so far been to $t$ countries and knows the coin system for each of them. For each country, print "DA" or "NE" depending on whether the coin system in that country is extraordinary.
Input
The first line contains a natural number $t$ ($1 \le t \le 100$).
This is followed by $t$ descriptions of countries, where each country is described by two lines. The first line contains a natural number $n$ ($1 \le n \le 10\,000$), and the second line contains natural numbers $1 = c_1 < c_2 < \dots < c_n \le 10\,000$.
The sum of all values of $n$ across all countries does not exceed $10\,000$.
Output
Print $t$ lines, for each country the answer to the question of whether the coin system is extraordinary.
Examples
Input 1
3 3 1 2 5 4 1 3 8 13 4 1 3 4 10
Output 1
DA DA NE
Note
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$).