货币系统

题目描述

五一期间, 小t去$T$个国家游玩, 他发现每个国家都有自己的货币系统, 即货币面值构成的集合. 如中国的货币系统为$\{ 1, 5, 10, 20, 50, 100 \}$.

假设小t的钱包里每种面值的货币都有无限个. 小t旅游时需要购买一些东西, 不妨设其中的一个价值为$x$, 因为小t的数学比较拉, 所以他每次会从钱包里找出不超过还需要支付的金额的最大货币, 用于支付, 一直到支付完毕.

例如当货币系统为$\{1, 3, 6\}$, 物品价值$x = 10$时, 小t会依次使用面值为$6, 3, 1$的金币进行支付.

如果在当前国家, 对于任意价值的物品, 都不存在另一种支付方案, 使得用来支付的货币总数严格小于小t的方法. 那么我们说在该国家小t是聪明的. (保证每个国家都有面值为$1$的货币, 即任意价值的物品都可以被支付)

给定这$T$个国家的货币系统, 判断小t在这些国家是不是聪明的.

输入格式

第一行一个正整数$T$, 表示国家的个数

对于每个国家, 第一行输入一个正整数$N$, 表示该国家货币系统的大小

接下来一行输入$N$个正整数 $a_1, a_2, ... , a_n$, 分别表示这$N$种面值.

输出格式

对于每个国家, 输出一行一个字符串 : 如果在这个国家小t是聪明的, 输出Yes, 否则 输出No.

你可以输出任意大小写形式 如YES, yEs, NO等.

样例输入

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

样例输出

Yes
Yes
No

样例解释

对于第三个国家, 当我们购买价值为$6$的物品时, 小t的方法会使用$\{4, 1, 1 \}$. 但是存在$\{3, 3\}$的支付方法, 使用的货币数量更少.

数据范围

对于所有数据 满足 $1 \leq T \leq 100$, $1 \leq N \leq 1000$, $\sum{N} \leq 1000$, 并且$1 = a_1 < a_2 < ... < a_n <= 10000$.