国际奥林匹克竞赛不仅是参赛者展示知识的机会，也是马尔纳先生（Mr. Malnar）期待在新的国家品尝特色美食的机会。为了准备支付昂贵的晚餐，他决定在出发前将部分资金兑换成该国的货币。

在该国，所有金额均为自然数，且有 $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$ 行，针对每个国家回答该硬币系统是否为“非凡的”。

样例

输入 1

3
3
1 2 5
4
1 3 8 13
4
1 3 4 10

输出 1

DA
DA
NE

说明 1

在第三个国家中，金额 $6$ 可以通过两枚硬币支付（$6 = 3 + 3$），但贪心算法使用了三枚硬币（$6 = 4 + 1 + 1$）。