题目描述
五一期间, 小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
等.
数据范围
对于所有数据 满足 $1 \leq T \leq 100$, $1 \leq N \leq 1000$, $\sum{N} \leq 1000$, 并且$1 = a_1 < a_2 < ... < a_n <= 10000$.
样例输入
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\}$的支付方法, 使用的货币数量更少.