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.


-----Input-----

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.


-----Output-----

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).


-----Examples-----

Input
6
1
1
2
1 1
2
1 2
3
3 1 3
2
7 5
6
26 8 3 4 13 34
Output
YES
YES
NO
YES
NO
YES


-----Note-----

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".

Source: codeforces | Difficulty: HARD
Tags: Mathematics

Number theory

Implementation

Greedy algorithms


Solutions:
import heapq
FIBS = []
CUMSUMS = []
a = 0
b = 1
cumsum = 0
while cumsum < 10 ** 12:
	FIBS.append(b)
	cumsum += b
	CUMSUMS.append(cumsum)
	(a, b) = (b, a + b)

def solve(nums):
	s = sum(nums)
	if s not in CUMSUMS:
		return False
	nums = [-n for n in nums]
	heapq.heapify(nums)
	not_use = 0
	for ind in range(CUMSUMS.index(s), -1, -1):
		f = FIBS[ind]
		max_num = -heapq.heappop(nums)
		if f > max_num:
			return False
		max_num -= f
		heapq.heappush(nums, -not_use)
		not_use = max_num
	return True
n = int(input())
for _ in range(n):
	input()
	nums = list(map(int, input().strip().split()))
	if solve(nums):
		print('YES')
	else:
		print('NO')


import heapq
FIBNUM = 50
fibs = [1, 1]
for i in range(FIBNUM):
	fibs.append(fibs[-1] + fibs[-2])
fibs_sum = [1]
for num in fibs[1:]:
	fibs_sum.append(num + fibs_sum[-1])
fibs_sum_dict = dict()
for (idx, num) in enumerate(fibs_sum):
	fibs_sum_dict[num] = idx
t = int(input())
for _ in range(t):
	k = int(input())
	arr = input().split()
	arr = [int(i) for i in arr]
	arr_sum = sum(arr)
	if arr_sum not in fibs_sum_dict:
		print('NO')
	else:
		arr_heap = [-i for i in arr]
		heapq.heapify(arr_heap)
		idx = fibs_sum_dict[arr_sum]
		last_value = 0
		success = True
		while True:
			if len(arr_heap) == 0:
				success = False
				break
			value = -heapq.heappop(arr_heap)
			if value < fibs[idx]:
				success = False
				break
			if last_value > 0:
				heapq.heappush(arr_heap, -last_value)
			last_value = value - fibs[idx]
			idx -= 1
			if idx < 0:
				break
		if success:
			print('YES')
		else:
			print('NO')


def fibSeq(summation):
	x = []
	i = 0
	a = 0
	b = 0
	c = 1
	while i <= summation:
		if i == summation:
			return x
		a = b + c
		temp = a
		c = b
		b = temp
		i += a
		x.append(a)
	return x
import heapq
t = int(input())
for case in range(t):
	k = int(input())
	c = list(map(int, input().split()))
	summation = 0
	x = []
	x = fibSeq(sum(c))
	if sum(c) != sum(x):
		print('NO')
		continue
	c.sort()
	cT = c
	c = [-i for i in cT]
	heapq.heapify(c)
	index = -1
	lstVal = 0
	success = True
	for i in range(len(x) - 1, -1, -1):
		if not len(c):
			success = False
			break
		val = heapq.heappop(c)
		if -val < x[i]:
			success = False
			break
		if lstVal < 0:
			heapq.heappush(c, lstVal)
		lstVal = val + x[i]
		if not i:
			break
	if success:
		print('YES')
	else:
		print('NO')


import heapq as h
T = int(input())
for _ in range(T):
	n = int(input())
	lst = list(map(int, input().split()))
	lstsum = sum(lst)
	lst = [-i for i in lst]
	h.heapify(lst)
	fiblst = [1]
	fibsum = 1
	cur = 1
	while fibsum < lstsum:
		fibsum += cur
		fiblst.append(cur)
		cur = cur + fiblst[-2]
	if fibsum != lstsum:
		print('NO')
		continue
	tmp1 = -1
	tmp2 = -1
	flag = 1
	for i in range(len(fiblst) - 1, -1, -1):
		if i % 2 == 0 and tmp1 != -1:
			h.heappush(lst, -tmp1)
			tmp1 = -1
		if i % 2 == 1 and tmp2 != -1:
			h.heappush(lst, -tmp2)
			tmp2 = -1
		if len(lst) == 0:
			flag = 0
			break
		maxlst = -h.heappop(lst)
		res = maxlst - fiblst[i]
		if res > 0:
			if i % 2 == 0:
				tmp1 = res
			else:
				tmp2 = res
		elif res < 0:
			flag = 0
			break
	if flag == 0:
		print('NO')
	else:
		print('YES')


def tr(a, b, z, m):
	n = z
	(x, y) = (a, b)
	li = m
	li.append(list(x))
	if sum(x) == 0:
		return 'YES'
	if x[0] >= y[n]:
		d = x[0] - y[n]
		x.pop(0)
		x.sort(reverse=True)
		x.append(d)
		n += 1
		return tr(x, y, n, li)
	elif n == 0:
		return 'NO'
	else:
		x = m[n - 1]
		x.append(x.pop(0))
		n -= 1
		return tr(x, y, n, li)
o = []
for t in range(int(input())):
	k = int(input())
	c = list(map(int, input().split()))
	summ = sum(c)
	f = [1]
	while sum(f) < summ:
		if f == [1]:
			f.append(1)
		else:
			x = len(f)
			f.append(f[x - 1] + f[x - 2])
	if sum(f) != summ:
		o.append('NO')
	else:
		f.sort(reverse=True)
		c.sort(reverse=True)
		c.append(0)
		o.append(tr(c, f, 0, []))
for u in o:
	print(u)