在布里亚特的所有学校,$$$1$$$ 班上,每个人都会学习斐波那契弦理论。
“块是字符串的一个子段,其中所有字母都相同,并且左右两侧以字符串的末端或块中字母以外的字母为界。如果将字符串分为块时,如果它们的长度按照它们在字符串中出现的顺序形成斐波那契数列,则该字符串称为斐波那契字符串($$$f_0 = f_1 = 1$$$, $$$f_i = f_{i-2} + f_{i-1}$$$),从该序列的第 0 个成员开始,如果可以重新排序其字母以获得斐波那契字符串,则该字符串称为半斐波那契字符串。”
布伦卡决定进入布里亚特国立大学,但在入学考试时她面临着一项艰巨的任务。给她一个由布里亚特字母表中的字母组成的字符串(其中恰好包含 $$$k$$$ 字母),并询问给定的字符串是否是半斐波那契数列。该字符串可能很长,因此她得到的不是该字符串,而是该字符串中每个字母的出现次数($$$c_i$$$ 表示第 $$$i$$$ 个字母)。不幸的是,布伦卡不再记得斐波那契弦理论,所以如果没有你的帮助,她将无法通过考试。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。以下是输入数据集的描述。
每个测试用例的第一行包含一个整数 $$$k$$$ ($$$1 \leq k \leq 100$$$) — 字母表中的字母数。
每个测试用例的第二行包含 $$$k$$$ 整数 $$$c_1, c_2, \ldots, c_k$$$ ($$$1 \leq c_i \leq 10^9$$$) — 字符串中每个字母出现的次数。
输出
对于每个测试用例,如果相应的字符串是半斐波那契,则打印字符串“YES”,如果不是,则打印“NO”。
在任何情况下都可以打印“YES”和“NO”(例如,字符串“yEs”、“yes”、“Yes”将被识别为肯定答案)。
示例
输入 #1
6 1 1 2 1 1 2 1 2 3 3 1 3 2 7 5 6 26 8 3 4 13 34
输出 #1
YES YES NO YES NO YES
注意
在第一个测试用例中,单字符字符串是半斐波那契字符串,它本身就是斐波那契字符串。
在第二个测试用例中,两个不同字符的字符串是斐波那契数。
在第三个测试用例中,字符串“abb”(令字母表中的第一个字母为 a,第二个字母为 b)不是半斐波那契字符串,因为其字母的排列(“abb”、“bab”和“bba”)都不是斐波那契字符串。
在第四个测试用例中,字符串“abaccac”的字母的两个排列(第一个字母是a,第二个字母是b,第三个字母是c)是斐波那契字符串——“abaaccc”和“cbccaaa”。