B. Фибоначчиевы строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во всех школах Бурятии в $$$1$$$ классе всем рассказывают теорию фибоначчиевых строк.

«Блок — это подотрезок строки, все буквы которого одинаковы, а слева и справа он ограничен концами строки или отличными от букв в блоке буквами. Строка называется фибоначчиевой, если при разбиении её на блоки их длины в порядке следования в строке составляют последовательность чисел Фибоначчи ($$$f_0 = f_1 = 1$$$, $$$f_i = f_{i-2} + f_{i-1}$$$), начиная с нулевого члена последовательности. Строка называется полуфибоначчиевой, если хотя бы одна из перестановок её букв является фибоначчиевой строкой.»

Бурёнка решила поступать в Бурятский государственный университет, но на вступительном экзамене ей дали непростую задачу. Ей дали строку, состоящую из букв бурятского алфавита (в котором ровно $$$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» будут распознаны как положительный ответ).

Пример
Входные данные
6
1
1
2
1 1
2
1 2
3
3 1 3
2
7 5
6
26 8 3 4 13 34
Выходные данные
YES
YES
NO
YES
NO
YES
Примечание

В первом наборе входных данных строка из одного символа является полуфибоначчиевой, являясь сама по себе фибоначчиевой строкой.

Во втором наборе входных данных строка из двух различных символов является фибоначчиевой.

В третьем наборе входных данных строка «abb» (пусть первая буква — a, вторая — b) не является полуфибоначчиевой строкой, так как все перестановки её букв («abb», «bab» и «bba») не являются фибоначчиевыми строками.

В четвёртом наборе входных данных две перестановки букв строки «abaccac» (первая буква — a, вторая — b, третья — c) являются фибоначчиевыми строками — «abaaccc» и «cbccaaa».