该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师在整理一批古老的文稿时，发现文字若要存入机器，必须先化作一串二进制编码。 然而，同样一段文字，若采用不同的编码方案，所占用的总空间也会不同。

为了让信息既精炼又安全，徐老师希望为一段只含小写字母的字符串设计一种编码方式，使其总编码长度尽可能小。 他想起了书中的经典方法——哈夫曼编码。

设每个字母的权值等于它在字符串中出现的次数。 对这些字母构造最优哈夫曼编码后，可以得到该字符串的最小总编码值。

现在，徐老师给出一个安全阈值 m 和一个字符串 s，请你判断该字符串的最小总编码值是否不超过 m。

若不超过，则认为该字符串是安全的；否则认为它是不安全的。

特别地，若字符串中只出现一种不同的字符，则规定该字符的编码长度为 1，此时字符串的最小总编码值等于字符串长度。

输入格式

第一行一个整数 n，表示数据组数。

接下来有 n 组数据，每组数据包含两行：

• 第一行一个整数 m，表示安全阈值；
• 第二行一个字符串 s，表示待编码的字符串。

保证字符串中不含空格，且仅由小写字母组成。

输出格式

对于每组数据，输出一行：

• 若字符串的最小总编码值小于等于 m，输出 yes；
• 否则输出 no。

样例输入

2
12
helloworld
66
ithinkyoucandoit

样例输出

no
yes

样例说明

对于每组数据，需要先统计字符串中每种字符出现的次数，将其作为权值构造哈夫曼树，并计算最优哈夫曼编码下的总编码长度。

然后将该最小总编码值与给定的安全阈值 m 比较：

• 若最小总编码值 ≤ m，输出 yes；
• 若最小总编码值 > m，输出 no。

数据范围

• 1 ≤ n ≤ 100
• 0 ≤ m ≤ 10^9
• 1 ≤ |s| ≤ 10^4

其中 s 仅由 a 到 z 的小写字母组成。

提示

哈夫曼编码的最优总代价，等价于不断合并当前权值最小的两个结点，并将每次合并产生的代价累加。 因此，本题可用优先队列高效实现。