Problem Statement

Golden Problem Description Some linguists study strings whose internal structure grows in a very particular way. For this problem: 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 how many times each letter of the alphabet occurs, work out whether those letters could 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 Exam