CF1718B.Fibonacci Strings

In all schools in Buryatia, in the $1$ class, everyone is told the theory of Fibonacci strings.

"A block is a subsegment of a string where all the letters are the same and are bounded on the left and right by the ends of the string or by letters other than the letters in the block. A string is called a Fibonacci string if, when it is divided into blocks, their lengths in the order they appear in the string form the Fibonacci sequence ($f_0 = f_1 = 1$, $f_i = f_{i-2} + f_{i-1}$), starting from the zeroth member of this sequence. A string is called semi-Fibonacci if it possible to reorder its letters to get a Fibonacci string."

Burenka decided to enter the Buryat State University, but at the entrance exam she was given a difficult task. She was given a string consisting of the letters of the Buryat alphabet (which contains exactly $k$ letters), and was asked if the given string is semi-Fibonacci. The string can be very long, so instead of the string, she was given the number of appearances of each letter ($c_i$ for the $i$-th letter) in that string. Unfortunately, Burenka no longer remembers the theory of Fibonacci strings, so without your help she will not pass the exam.

在布里亚特共和国的所有学校中，一年级学生都会学习斐波那契字符串（Fibonacci strings）的理论。

“块（block） 是字符串的一个子段，其中所有字符均相同，且该子段的左右边界要么是字符串的端点，要么是不同于该块内字符的其他字符。若将一个字符串划分为若干块，则当这些块按其在字符串中出现的顺序排列时，其长度序列构成斐波那契数列（定义为 $f_0 = f_1 = 1$，$f_i = f_{i-2} + f_{i-1}$），则称该字符串为斐波那契字符串（从该数列的第零项 $f_0$ 开始）。若一个字符串可通过重排其字符得到某个斐波那契字符串，则称其为半斐波那契字符串（semi-Fibonacci）。”

布伦卡决定报考布里亚特国立大学，但在入学考试中她遇到了一道难题：她被给定一个仅由布里亚特字母表中的字母组成的字符串（该字母表恰好包含 $k$ 个字母），并被要求判断该字符串是否为半斐波那契字符串。由于字符串可能非常长，她并未获得字符串本身，而是获得了每个字母的出现次数（即第 $i$ 个字母的出现次数为 $c_i$）。不幸的是，布伦卡已不再记得斐波那契字符串的相关理论，因此若无你的帮助，她将无法通过此次考试。

The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The following is a description of the input data sets.

The first line of each test case contains one integer $k$ ($1 \leq k \leq 100$) — the number of letters in the alphabet.

The second line of each test case contains $k$ integers $c_1, c_2, \ldots, c_k$ ($1 \leq c_i \leq 10^9$) — the number of occurrences of each letter in the string.

第一行包含一个整数 $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$）——字符串中每个字母的出现次数。

For each test case print the string "YES" if the corresponding string is semi-Fibonacci, and "NO" if it is not.

You can print "YES" and "NO" in any case (for example, the strings "yEs", "yes", "Yes" will be recognized as a positive answer).

对于每个测试用例，如果对应的字符串是半斐波那契（semi-Fibonacci）字符串，则输出字符串 "YES"；否则输出 "NO"。

你可以以任意大小写形式输出 "YES" 和 "NO"（例如，字符串 "yEs"、"yes"、"Yes" 均会被识别为肯定回答）。

In the first test case, a one-character string is semi-Fibonacci, being itself a Fibonacci string.

In the second test case, a string of two different characters is Fibonacci.

In the third test case, the string "abb" (let the first of the alphabet letter be a, the second letter b) is not a semi-Fibonacci string, since no permutation of its letters ("abb", "bab", and "bba") is a Fibonacci string.

In the fourth test case, two permutations of the letters of the string "abaccac" (the first letter is a, the second letter is b, the third letter is c) are Fibonacci strings — "abaaccc" and "cbccaaa".

在第一个测试用例中，一个单字符字符串是半斐波那契字符串，因为它本身就是一个斐波那契字符串。

在第二个测试用例中，由两个不同字符组成的字符串是一个斐波那契字符串。

在第三个测试用例中，字符串 “abb”（设字母表中第一个字母为 a，第二个字母为 b）不是半斐波那契字符串，因为其字母的任意排列（“abb”、“bab” 和 “bba”）均不是斐波那契字符串。

在第四个测试用例中，字符串 “abaccac”（第一个字母为 a，第二个字母为 b，第三个字母为 c）的两个字母排列 —— “abaaccc” 和 “cbccaaa” —— 是斐波那契字符串。