Problem Statement

Golden Problem Description Linguists are fascinated by strings that follow special growth patterns. They define: A block is a maximal run of identical letters. If the block lengths form the Fibonacci sequence (starting with 1, 1, 2, 3, ...), the string is called a Golden string. If by rearranging the letters you can obtain such a Golden string, it is called a semi-Golden string. Given the counts of characters in the alphabet, decide if the described string can be rearranged into a semi-Golden string. Input The first line contains a single integer T (1 ≤ T ≤ 10 4 ) — the number of test cases. Each test case starts with an integer k (1 ≤ k ≤ 100) — the number of distinct characters in the alphabet. The next line contains k integers c1, c2, ..., ck (1 ≤ ci ≤ 10 9 ) — the frequency of each character. Output For each test case, print YES if the string can be rearranged into a semi-Golden string, and NO otherwise. Examples Example 1: Input: 2 6 1 39 8 2 17