You are given an array $a$ consisting of $n$ positive integers. You can perform operations on it.

In one operation you can replace any element of the array $a_i$ with $\lfloor \frac{a_i}{2} \rfloor$, that is, by an integer part of dividing $a_i$ by $2$ (rounding down).

See if you can apply the operation some number of times (possible $0$) to make the array $a$ become a permutation of numbers from $1$ to $n$ —that is, so that it contains all numbers from $1$ to $n$, each exactly once.

For example, if $a = [1, 8, 25, 2]$, $n = 4$, then the answer is yes. You could do the following:

Replace $8$ with $\lfloor \frac{8}{2} \rfloor = 4$, then $a = [1, 4, 25, 2]$.

Replace $25$ with $\lfloor \frac{25}{2} \rfloor = 12$, then $a = [1, 4, 12, 2]$.

Replace $12$ with $\lfloor \frac{12}{2} \rfloor = 6$, then $a = [1, 4, 6, 2]$.

Replace $6$ with $\lfloor \frac{6}{2} \rfloor = 3$, then $a = [1, 4, 3, 2]$.


-----Input-----

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases.

Each test case contains exactly two lines. The first one contains an integer $n$ ($1 \le n \le 50$), the second one contains integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).


-----Output-----

For each test case, output on a separate line:

YES if you can make the array $a$ become a permutation of numbers from $1$ to $n$,

NO otherwise.

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


-----Examples-----

Input
6
4
1 8 25 2
2
1 1
9
9 8 3 4 2 7 1 5 6
3
8 2 1
4
24 7 16 7
5
22 6 22 4 22
Output
YES
NO
YES
NO
NO
YES


-----Note-----

The first test case is explained in the text of the problem statement.

In the second test case, it is not possible to get a permutation.

Source: codeforces | Difficulty: EASY
Tags: Flows and cuts

Constructive algorithms

Mathematics

Greedy algorithms


Solutions:
from sys import stdin

def solve():
	for _ in range(int(stdin.readline().strip())):
		n = int(stdin.readline().rstrip())
		A = list(map(int, stdin.readline().rstrip().split()))
		B = [0] * (n + 1)
		C = []
		ans = 'YES'
		for x in A:
			if x <= n:
				if B[x] == 0:
					B[x] = 1
				else:
					while B[x] == 1 and x > 0:
						x //= 2
					if x == 0 or B[x] == 1:
						ans = 'NO'
						break
					B[x] = 1
			else:
				C.append(x)
		if ans == 'YES':
			for x in C:
				while x > n:
					x = x // 2
				if B[x] == 0:
					B[x] = 1
				else:
					while B[x] == 1 and x > 0:
						x = x // 2
					if x == 0 or B[x] == 1:
						ans = 'NO'
						break
					B[x] = 1
		if ans == 'YES':
			for i in range(1, n + 1):
				if B[i] != 1:
					ans = 'NO'
					break
		print(ans)
solve()


import math, os, io, heapq
from functools import reduce
from sys import stdin, stdout
from collections import Counter, deque, defaultdict
from itertools import product
import bisect

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def checkMod(a, b):
	return a > 0 and a % b == 0

def solve():
	(n, a) = (getInt(), getList())
	a.sort(reverse=True)
	added = [False for _ in range(n + 1)]
	for v in a:
		while v > n or added[v]:
			v //= 2
		if v == 0:
			return 'NO'
		added[v] = True
	return 'YES'
for _ in range(getInt()):
	print(solve())


import os
import math
import statistics
true = True
false = False
from functools import reduce
is_dev = 'vscode' in os.environ
if is_dev:
	inF = open('in.txt', 'r')
	outF = open('out.txt', 'w')

def ins():
	return list(map(int, input_().split(' ')))

def inss():
	return list(input_().split(' '))

def input_():
	if is_dev:
		return inF.readline()[:-1]
	else:
		return input()

def ranin():
	return range(int(input_()))

def print_(data):
	if is_dev:
		outF.write(str(data) + '\n')
	else:
		print(data)
epsilon = 1e-07
for _ in ranin():
	lx = int(input_())
	x = ins()
	counters = [0] * (lx + 1)
	impossible = False
	for i in range(lx):
		while x[i] > 1048576:
			x[i] >>= 10
		while x[i] > 4096:
			x[i] >>= 6
		while x[i] > lx:
			x[i] >>= 1
		counters[x[i]] += 1
	for i in range(lx, 0, -1):
		if counters[i] == 0:
			impossible = True
			break
		if counters[i] > 1:
			counters[i // 2] += counters[i] - 1
			counters[i] = 1
	if impossible:
		print_('NO')
	else:
		print_('YES')
if is_dev:
	outF.close()

	def compare_file():
		print(open('out.txt', 'r').read() == open('outactual.txt', 'r').read())
	compare_file()


def solve(n, l):
	numbs = [False] * (n + 1)
	for i in l:
		while i > n:
			i //= 2
		while numbs[i]:
			i //= 2
		numbs[i] = 1
		if numbs[0]:
			return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(solve(n, l))


def solve():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		ok = False
		per = [False] * (n + 1)
		for ele in a:
			while ele > n or per[ele]:
				ele = ele // 2
			if ele == 0:
				ok = True
			else:
				per[ele] = True
		if ok:
			print('NO')
		else:
			print('YES')
solve()


func = lambda x: bin(int(x))
for _ in range(int(input())):
	n = int(input())
	a = list(map(func, input().split()))
	x = []
	ll = len(bin(n))
	for i in a:
		p = min(ll, len(i))
		if int(i[:p], 2) > n:
			p = p - 1
		while p > 2 and i[:p] in x:
			p = p - 1
		if p == 2:
			break
		else:
			x.append(i[:p])
	print('YNEOS'[int(len(x) != n)::2])


def func():
	n = int(input())
	l = list(map(int, input().split()))
	d = {i: 0 for i in range(0, n + 1)}
	new_l = []
	for i in l:
		if i > n:
			while i > n:
				i = i // 2
			new_l.append(i)
			d[i] += 1
		else:
			new_l.append(i)
			d[i] += 1
	for i in range(n, 0, -1):
		if d[i] == 0:
			return 'NO'
		else:
			d[i // 2] += d[i] - 1
	return 'YES'
t = int(input())
for i in range(t):
	print(func())


t = int(input())
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	gotten = set()
	maxNeeded = n
	found = [False] * n
	for i in range(n):
		num = array[i]
		if num > 63:
			num = int(str(bin(num))[2:8], base=2)
		while (num > maxNeeded or num in gotten) and num > 0:
			num = num // 2
		if num == maxNeeded:
			gotten.add(num)
			found[-num] = True
			if False in found:
				maxNeeded = n - found.index(False)
		elif num > 0:
			gotten.add(num)
			found[-num] = True
		else:
			break
	if False in found:
		print('NO')
	else:
		print('YES')


t = int(input())

def calc():
	n = int(input())
	l = list(map(int, input().split()))
	for j in range(n):
		val = l[j]
		while val > n:
			val = val // 2
		l[j] = val
	arr = [0 for k in range(n)]
	for j in range(n):
		while l[j] > 0:
			if arr[l[j] - 1] == 0:
				arr[l[j] - 1] = 1
				break
			else:
				l[j] = l[j] // 2
		if l[j] == 0:
			return 'NO'
	return 'YES'
for i in range(t):
	print(calc())


import math
for _ in range(int(input())):
	num = int(input())
	all = list(map(int, input().split()))
	dic = {}
	for i in range(num):
		dic[i + 1] = 0
	rest = []
	for i in all:
		if i > num:
			rest.append(i)
		elif dic[i] == 0:
			dic[i] = 1
		else:
			rest.append(i)
	long = len(rest)
	if long == 0:
		print('YES')
	else:
		flag = 0
		for j in range(long):
			re = rest[j]
			if rest[j] > num:
				temp = math.ceil(rest[j] / num)
				ci = math.floor(math.log(temp, 2))
				t = rest[j] // 2 ** ci
			else:
				t = rest[j]
			if t > num:
				t = t // 2
			while dic[t] != 0:
				t = t // 2
				if t == 0:
					flag = 1
					break
			if t != 0:
				if dic[t] == 0:
					dic[t] = 1
			if flag == 1:
				break
		if flag == 0:
			print('YES')
		else:
			print('NO')


import heapq

def solve(n, a):
	b = []
	for x in a:
		while x > n:
			x >>= 1
		b.append(-x)
	heapq.heapify(b)
	for i in range(-n, 0):
		x = heapq.heappop(b)
		while x < i:
			y = -(-x >> 1)
			x = heapq.heappushpop(b, y)
		if x > i:
			return 'NO'
	return 'YES'
T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in input().split()]
	result = solve(n, a)
	print(result)


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)

def func(x):
	global n, cl
	x = int(x)
	while x > n:
		x //= 2
	while x in cl:
		x //= 2
		if x == 1 and 1 in cl:
			return False
	else:
		cl.append(x)
	return x

def Solve():
	global n, cl
	for t in range(int(input())):
		e = True
		cl = []
		n = int(input())
		l = input().split()
		for i in l:
			if func(i) == False:
				e = False
				break
		if e:
			print('YES')
		else:
			print('NO')
Solve()


def solve():
	n = int(input())
	A = [int(x) for x in input().split()]
	found = [False] * (n + 1)
	for x in A:
		while x > n or found[x]:
			x //= 2
			if x == 0:
				return 'NO'
		found[x] = True
	return 'YES'
t = int(input())
for _ in range(t):
	print(solve())


def check_perm(n, arr):
	arr.sort(reverse=True)
	arr_set = set()
	ans = 'YES'
	for num in arr:
		x = num
		while x > n or x in arr_set:
			x = x // 2
		if x > 0:
			arr_set.add(x)
		else:
			ans = 'NO'
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(check_perm(n, arr))


def func(x):
	global n, cl
	x = int(x)
	while x > n:
		x //= 2
	while x in cl:
		x //= 2
		if x == 1 and 1 in cl:
			return False
	else:
		cl.append(x)
	return x

def Solve():
	global n, cl
	for t in range(int(input())):
		e = True
		cl = []
		n = int(input())
		l = input().split()
		for i in l:
			if func(i) == False:
				e = False
				break
		if e:
			print('YES')
		else:
			print('NO')
Solve()


from collections import Counter, deque
from collections import OrderedDict
import math
from random import randint
from bisect import bisect, bisect_left
import sys
import re
MOD = 10 ** 9 + 7
MAX = -sys.maxsize
MIN = sys.maxsize

class get:

	def int():
		return list(map(int, input().split()))

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

	def map():
		return map(int, input().split())

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def solve():
	n = int(input())
	a = get.int()
	a.sort(reverse=True)
	s = set([i for i in range(1, n + 1)])
	for item in a:
		if item in s:
			s.remove(item)
			continue
		while item > 0:
			item = item // 2
			if item in s:
				s.remove(item)
				break
		if item == 0:
			print('NO')
			return
	print('YES')
t = int(input())
for tt in range(t):
	solve()


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	seen = [False] * (n + 1)
	flag = True
	for i in l:
		x = i
		while x > n or seen[x] == True:
			x //= 2
		if x > 0:
			seen[x] = True
		else:
			flag = False
	if flag:
		return 'YES'
	else:
		return 'NO'
T = int(input())
for _ in range(T):
	print(solve())


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	visited = [False for i in range(n + 1)]
	for i in range(n):
		x = arr[i]
		if x <= n and visited[x] == False:
			visited[x] = True
			arr[i] = -1
	for i in range(n):
		if arr[i] != -1:
			x = arr[i]
			flag = 0
			while x > 0:
				if x <= n and visited[x] == False:
					visited[x] = True
					flag = 1
					break
				x = x // 2
			if flag == 0:
				return 'NO'
	for i in range(1, n + 1):
		if visited[i] == False:
			return 'NO'
	return 'YES'
t = int(input())
for i in range(t):
	print(solve())


t = int(input())

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	arr = list(range(n + 1))
	for i in range(n + 1):
		arr[i] = 0
	for i in a:
		while i > n:
			i = i // 2
		while arr[i] == 1 and i != 0:
			i = i // 2
		arr[i] = 1
	answer = True
	for i in range(n + 1):
		if arr[i] == 0 and i != 0:
			answer = False
	if answer:
		print('YES')
	else:
		print('NO')
for i in range(t):
	solve()


def divBy2AndPermutaton(n, a):
	b = [False for _ in range(n + 1)]
	b[0] = True
	for x in a:
		while x > n or (x > 0 and b[x] == True):
			x //= 2
		b[x] = True
	if False in b:
		return 'NO'
	return 'YES'
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	print(divBy2AndPermutaton(n, a))


def f(a, n):
	while a > n:
		a = a // 2
	return a
T = int(input())
for tc in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		t = a[i]
		a[i] = f(t, n)
	d = {i: False for i in range(1, n + 1)}
	a.sort()
	i = n - 1
	while i >= 0 and a[i] != 0:
		if d[a[i]] == False:
			d[a[i]] = True
			i = i - 1
		else:
			a[i] = a[i] // 2
	if a[i] == 0:
		print('NO')
	if i == -1:
		print('YES')


def calc(arr, n):
	perm = [0 for i in range(n)]
	for a in arr:
		placed = False
		while a > 0 and (not placed):
			if a > n or perm[a - 1] == 1:
				a = a // 2
			elif perm[a - 1] == 0:
				placed = True
				perm[a - 1] = 1
		if a == 0:
			print('NO')
			return
	print('YES')
	return
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(a) for a in input().split()]
	calc(arr, n)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	q = list(map(int, inp().split()))
	while q:
		w = []
		ok = False
		for x in q:
			while x > n:
				x //= 2
			if x == n:
				ok = True
				n -= 1
			else:
				w.append(x)
		if not ok:
			break
		q = w
	print(['NO', 'YES'][len(q) == 0])

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def reduceby2(val, n):
	if val <= n:
		return val
	while val > n:
		val = val // 2
	return val
t = int(input())
for _ in range(t):
	result = 'YES'
	n = int(input())
	b = []
	a = list(map(int, input().split()))
	for i in range(len(a)):
		val = reduceby2(a[i], n)
		while val > 0:
			if not val in b:
				b.append(val)
				break
			val = val // 2
		if val == 0:
			result = 'NO'
			break
	print(result)


import sys
input = sys.stdin.readline

def main():
	for _ in range(int(input())):
		n = int(input())
		(*arr,) = map(int, input().split())
		while arr:
			tmp = []
			ok = False
			for x in arr:
				while x > n:
					x //= 2
				if x == n:
					ok = True
					n -= 1
				else:
					tmp.append(x)
			if not ok:
				break
			arr = tmp
		print('YES' if n == 0 else 'NO')
main()


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def main():
	for _ in range(int(input())):
		n = int(input())
		st = set()
		ls = get_ls()
		for x in ls:
			while (x > n or x in st) and x > 1:
				x >>= 1
			st.add(x)
		print('YES' if len(st) == n else 'NO')
main()


def solve():
	n = int(input())
	li = list(map(int, input().split()))
	visited = [0] * (n + 1)
	k = []
	for i in li:
		if i <= n and visited[i] == 0:
			visited[i] = 1
		else:
			k.append(i)
	for i in k:
		while i > 0:
			if i <= n and visited[i] == 0:
				visited[i] = 1
				break
			i = i // 2
	visited[0] = 0
	return 'YES' if sum(visited) == n else 'NO'
t = int(input())
while t > 0:
	print(solve())
	t -= 1


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	if max(arr) < n:
		print('NO')
		return
	l = []
	for i in arr:
		while i > 0:
			if i <= n and i not in l:
				l.append(i)
				break
			i = i // 2
	if len(l) == n:
		print('YES')
	else:
		print('NO')
for x in range(int(input())):
	solve()


def main():
	t = int(input())
	while t:
		t -= 1
		n = int(input())
		a = sorted([int(x) for x in input().split()], reverse=True)
		s = set()
		for i in a:
			while (i > n or i in s) and i > 1:
				i >>= 1
			s.add(i)
		print(['NO', 'YES'][len(s) == n])
main()


def canI(arr, n):
	perm = []
	for i in arr:
		while i > 0:
			if i <= n:
				if i not in perm:
					perm.append(i)
					break
			i = i // 2
	if len(perm) == n:
		print('YES')
	else:
		print('NO')
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	canI(arr, n)


def ans(a, n):
	used = set()
	for i in a:
		while (i > n or i in used) and i > 1:
			i = i // 2
		used.add(i)
	if len(used) == n:
		print('YES')
	else:
		print('NO')
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans(a, n)


def fun(i, n):
	while i > n:
		i = i // 2
	return i

def Fun(i, c):
	j = len(c) - 1
	while c[j] > i:
		x = c.pop(j)
		x = fun(x, i)
		c.append(x)
		j -= 1
	c.sort()
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	i = 0
	while i < n:
		if a[i] != i + 1:
			break
		i += 1
	b = a[:i]
	a = a[i:]
	c = []
	X = []
	for i in a:
		c.append(fun(i, n))
	c.sort()
	for i in range(n, len(b), -1):
		Fun(i, c)
		if i != c[-1]:
			print('NO')
			break
		c.pop()
	else:
		print('YES')


def soluciona():
	n = int(input())
	arr = list(map(int, input().split()))
	if max(arr) < n:
		print('NO')
		return
	permutacao = []
	for i in arr:
		while i > 0:
			if i <= n and i not in permutacao:
				permutacao.append(i)
				break
			i = i // 2
	print('YES') if len(permutacao) == n else print('NO')
for _ in range(int(input())):
	soluciona()


def ispossible(arr, n):
	lis = []
	lis = set(lis)
	arr.sort()
	for i in arr:
		while (i > n or i in lis) and i > 1:
			i //= 2
		lis.add(i)
	if len(lis) == n:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ispossible(arr, n)


def C(a, n):
	p = []
	for i in a:
		while i > 0:
			if i <= n:
				if i not in p:
					p.append(i)
					break
			i = i // 2
	if len(p) == n:
		print('YES')
	else:
		print('NO')
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	C(a, n)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(i) for i in input().strip().split()]
	s = {i + 1 for i in range(n)}
	check = True
	for x in l:
		y = x
		while x > n:
			x = x // 2
		if x in s:
			s.remove(x)
		else:
			while x > 0:
				x = x // 2
				if x in s:
					s.remove(x)
					break
			if x == 0:
				check = False
		if check == False:
			break
	if check:
		print('YES')
	else:
		print('NO')


import math

def solve(n, lst):
	lst.sort()
	already_have = set(lst)
	dct = {}
	for ele in lst:
		dct[ele] = dct.get(ele, 0) + 1
	missing = set()
	for i in range(1, n + 1):
		if i not in already_have:
			missing.add(i)
	extra = []
	for ele in lst:
		if dct[ele] > 1 or ele > n:
			dct[ele] = dct[ele] - 1
			extra.append(ele)
	extra.sort()
	for ele in extra:
		x = 2
		temp = ele
		while temp not in missing:
			temp = temp // 2
			if temp == 0:
				break
		if temp in missing:
			missing.remove(temp)
		else:
			print('NO')
			return
	if len(missing) == 0:
		print('YES')
	else:
		print('NO')
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	solve(n, lst)


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	perm = set((x + 1 for x in range(n)))
	for el in l:
		if el in perm:
			perm.remove(el)
		else:
			while el > 0:
				el //= 2
				if el in perm:
					perm.remove(el)
					break
	print('YES' if len(perm) == 0 else 'NO')
for _ in range(int(input())):
	solve()


c = int(input())
for i in range(c):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	index_array = [0] * n
	total_counter = 0
	res = 'YES'
	for v in arr:
		while v > n:
			v //= 2
		while index_array[v - 1] > 0:
			v //= 2
			if v == 0:
				break
		if v == 0:
			res = 'NO'
			break
		else:
			total_counter += 1
			index_array[v - 1] = 1
	print(res)


N_LIMIT = 50

def solve():
	t = int(input())
	for _ in range(t):
		solve_one(construct_convert_map(N_LIMIT))

def construct_convert_map(limit: int):
	convert_map = {}
	for i in range(1, limit + 1):
		convert_map[i] = {1, i}
		cur_val = i
		while cur_val != 1:
			cur_val = cur_val // 2
			convert_map[i].add(cur_val)
	return convert_map

def solve_one(convert_map: dict):
	n = int(input())
	a = [int(x) for x in input().split()]
	assert len(a) == n
	b = []
	for e in a:
		b.append(boil_down(e, N_LIMIT))
	cur_n = n
	sorted_b = sorted(b, reverse=True)
	while cur_n > 0:
		for e in sorted_b:
			if cur_n in convert_map[e]:
				break
		else:
			print('NO')
			return
		cur_n -= 1
		sorted_b.remove(e)
	print('YES')

def boil_down(val: int, limit: int):
	cur_val = val
	while cur_val > limit:
		cur_val //= 2
	return cur_val
solve()


import sys
input = sys.stdin.readline
tests = int(input())
for test in range(tests):
	n = int(input())
	an = list(map(int, input().split()))
	done = [False] * (n + 1)
	doable = True
	for a in an:
		this_a = a
		while this_a > n:
			this_a = this_a // 2
		while done[this_a]:
			this_a = this_a // 2
		if this_a:
			done[this_a] = True
		else:
			print('NO')
			doable = False
			break
	if doable:
		print('YES')


t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))[:n]
	a.sort(reverse=True)
	net = [0] * (n + 1)
	yes = 1
	for i in a:
		x = i
		while x > n or net[x]:
			x = x // 2
		if x > 0:
			net[x] = 1
		else:
			yes = 0
			break
	if yes == 1:
		print('YES')
	else:
		print('NO')
	t -= 1


import math
for _ in range(int(input())):
	n = int(input())
	ai = list(map(int, input().split()))
	ai.sort()
	ai.reverse()
	m = min(ai)
	k = 0
	if m > n:
		k = int(math.log(m, 2) - math.log(n, 2))
		ai = [int(i / 2 ** k) for i in ai]
	output = []
	for i in ai:
		while i > 0:
			if i <= n and i not in output:
				output.append(i)
				break
			else:
				i = int(i / 2)
	if len(output) == n:
		print('YES')
	else:
		print('NO')


def main():
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	arr.sort()
	vis = set()
	for num in arr:
		while num > 1 and (num in vis or num > n):
			num //= 2
		if num in vis:
			print('NO')
			return
		vis.add(num)
	print('YES')
t = int(input())
while t != 0:
	main()
	t -= 1


def q(x, y):
	o = set()
	for i in range(len(y)):
		f = y[i]
		while True:
			if 0 == f:
				if 9 + 1 == 10:
					return 'NO'
			if f not in o and f <= x:
				if 0 + 0 == 0:
					o.add(f)
					break
			elif 1 + 1 == 2:
				f = f // 2
	l = len(o)
	if x == l:
		if 2 + 3 == 5:
			return 'YES'
	if 4 + 4 == 8:
		return 'NO'
z = int(input())
for t in range(z):
	x = int(input())
	y = list(map(int, input().split()))
	if 2 * 8 == 16:
		print(q(x, y))


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	used = [False] * n
	flag = True
	for num in l:
		while num > n:
			num //= 2
		while used[num - 1] and num > 0:
			num //= 2
		if num == 0:
			flag = False
			break
		else:
			used[num - 1] = True
	if flag:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	d = [*map(int, input().split())]
	r = 'YES'
	v = [False] * (n + 1)
	for i in d:
		while i > n or v[i]:
			i //= 2
		if i:
			v[i] = True
		else:
			r = 'NO'
			break
	print(r)


for _ in range(int(input())):
	n = int(input())
	c = [0] * 99
	for v in map(int, input().split()):
		while v > n:
			v //= 2
		c[v] += 1
	for i in range(n, 0, -1):
		if c[i]:
			c[i // 2] += c[i] - 1
		else:
			break
	else:
		print('YES')
		continue
	print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	used = [False] * (n + 1)
	flag = True
	for v in a:
		while v > n or used[v] == True:
			v //= 2
		if v != 0:
			used[v] = True
		else:
			flag = False
			break
	print('YES' if flag else 'NO')


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a = a[::-1]
	used = (n + 1) * [False]
	impossible = False
	for b in a:
		while b > n:
			b //= 2
		while used[b]:
			b //= 2
		if b:
			used[b] = True
		else:
			impossible = True
			break
	if impossible:
		print('NO')
	else:
		print('YES')


def find(k, n):
	a = []
	while k > n:
		k //= 2
	while k >= 1:
		a.append(k)
		k //= 2
	return a
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [find(a[i], n) for i in range(n)]
	f = []
	for i in b:
		for j in i:
			if j not in f:
				f.append(j)
				break
	print('YES' if len(set(f)) == n else 'NO')


def cal(lst, num):
	d = {}
	ma = 0
	lst.sort()
	l1 = []
	p = 1
	for i in range(num):
		if lst[i] != p:
			d[p] = 1
			l1.append(l[i])
		p += 1
	for i in l1:
		while i >= 1:
			if i in d and d[i] > 0:
				d[i] = 0
				break
			else:
				i = i // 2
	c = 1
	for i in d:
		if d[i] == 1:
			c = 0
			break
	if c == 0:
		print('NO')
	else:
		print('YES')
t = int(input())
for test in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	cal(l, n)


def check(a, n):
	b = [0] * (n + 1)
	a.sort()
	for i in range(n):
		if a[i] <= n:
			if b[a[i]] == 0:
				b[a[i]] = a[i]
			else:
				s = 1
				val = a[i]
				while s != 0:
					val = val // 2
					if b[val] == 0:
						b[val] = val
						s = 0
					if val == 0:
						s = 0
		else:
			s = 1
			val = a[i]
			while s != 0:
				val = val // 2
				if val <= n:
					if b[val] == 0:
						b[val] = val
						s = 0
					if val == 0:
						s = 0
	if b.count(0) > 1:
		return 'NO'
	else:
		return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(check(a, n))


from typing import Counter
import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		for i in range(n):
			while a[i] > n:
				a[i] //= 2
		a = Counter(a)
		for i in reversed(range(1, n + 1)):
			if a[i] == 1:
				continue
			if a[i] == 0:
				print('NO')
				break
			a[i // 2] += a[i] - 1
			a[i] = 1
		else:
			print('YES')
main()


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	v = {}
	for i in range(n):
		while a[i] > n:
			a[i] //= 2
		while a[i] in v:
			a[i] //= 2
		if a[i] == 0:
			print('NO')
			return
		v[a[i]] = 1
	print('YES')
t = int(input())
for _ in range(t):
	solve()


def tperm(a, n):
	mx = n
	for i in range(n):
		while a[i] > n:
			a[i] //= 2
	a.sort()
	while a:
		if mx != a.pop():
			return False
		if mx == 1:
			return True
		i = mx - 2
		while i >= 0 and a[i] == mx:
			a[i] //= 2
			i -= 1
		a.sort()
		mx -= 1
t = int(input())
tests = [False for i in range(t)]
n = 0
for i in range(t):
	n = int(input())
	if tperm(list(map(int, input().split())), n):
		tests[i] = True
for test in tests:
	if test:
		print('YES')
	else:
		print('NO')


t = int(input())
tt = [list(map(int, input().split())) for i in range(2 * t)]
for i in range(1, len(tt), 2):
	ti = tt[i]
	n = tt[i - 1][0]
	done = set()
	for j in ti:
		while j > n or j in done:
			j //= 2
		if j == 0:
			break
		else:
			done.add(j)
	if len(done) == n:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	sel = {}
	i = 0
	s = 0
	while i < n:
		ai = a[i]
		while ai > n:
			ai = ai // 2
		if ai not in sel:
			s += 1
			sel[ai] = True
		else:
			teste = True
			ai = ai // 2
			while ai > 0:
				if ai not in sel:
					sel[ai] = True
					s += 1
					teste = False
					break
				ai = ai // 2
			if teste:
				break
		i += 1
	if s == n:
		print('YES')
	else:
		print('NO')
	t -= 1


def problem3(arr, n):
	found = set()
	for num in arr:
		while num > 0:
			if num not in found and 1 <= num <= n:
				found.add(num)
				break
			num //= 2
		if num == 0:
			print('NO')
			return
	if len(found) == n:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	n = int(input())
	arr = [int(num) for num in input().split(' ')]
	problem3(arr, n)


import sys

def input():
	return sys.stdin.readline().rstrip()
t = int(input())
for _ in range(t):
	n = int(input())
	lst = sorted(list(map(int, input().split())), reverse=True)
	check = [False] * (n + 1)
	flag = False
	for num in lst:
		while num > n:
			num //= 2
		while check[num]:
			if num == 1 and check[num] == True:
				flag = True
				check[1] = False
			num //= 2
		if flag:
			break
		check[num] = True
	if False in check[1:]:
		print('NO')
	else:
		print('YES')


from functools import lru_cache as cache
import math
from heapq import *
import sys

def get_int():
	return int(input())

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def main():
	testcases = get_int()
	for i in range(testcases):
		n = get_int()
		arr = get_list()
		if solve(arr, n):
			print('YES')
		else:
			print('NO')

def solve(arr, n):
	count = [0 for i in range(n + 1)]
	for i in range(n):
		num = arr[i]
		while num > 0:
			if num <= n:
				count[num] += 1
			num >>= 1
	for i in range(n, 0, -1):
		num = i
		if count[num] == 0:
			return False
		while num > 0:
			count[num] -= 1
			num >>= 1
	return True
main()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	hashTable = [0 for i in range(n + 1)]
	flag = 1
	for i in range(n):
		t = arr[i]
		while t > n:
			t = t // 2
		hashTable[t] += 1
	for i in range(n, 1, -1):
		if hashTable[i] > 1:
			hashTable[i // 2] += hashTable[i] - 1
			hashTable[i] = 1
	for i in range(1, n + 1):
		if hashTable[i] == 0:
			print('NO')
			flag = 0
			break
	if flag:
		print('YES')


for ii in range(int(input())):
	n = int(input())
	st = set(range(1, 1 + n))
	l = list((int(i) for i in input().split()))
	ps = 1
	for e in l:
		while e > 0 and e not in st:
			e >>= 1
		if e == 0:
			ps = 0
			break
		else:
			st.remove(e)
	print(['NO', 'YES'][ps])


def solver(arr):
	n = len(arr)
	freq = [0] * (n + 1)
	for i in range(n):
		while arr[i] > n:
			arr[i] //= 2
		freq[arr[i]] += 1
	flag = True
	for i in range(n, 0, -1):
		if freq[i] == 0:
			flag = False
			break
		freq[i // 2] += freq[i] - 1
	if flag:
		print('YES')
	else:
		print('NO')
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	solver(arr)
	t -= 1


def solution():
	n = int(input())
	a = [int(i) for i in input().split()]
	used = [False] * n
	for i in range(n):
		while a[i] > n or (1 <= a[i] <= n and used[a[i] - 1]):
			a[i] //= 2
		if a[i] == 0:
			return 'NO'
		used[a[i] - 1] = True
	return 'YES'
t = int(input())
for _ in range(t):
	print(solution())


def f(a):
	n = len(a)
	used = [0] * (n + 1)
	a.sort(key=lambda el: -el)
	for i in range(n):
		while a[i] > n or used[a[i]]:
			a[i] //= 2
		if a[i] > 0:
			used[a[i]] = 1
		else:
			return 'NO'
	return 'YES'
inp = lambda : list(map(int, input().split()))
t = int(input())
r = []
for _ in range(t):
	n = int(input())
	a = inp()
	print(f(a))


def solve():
	size = int(input())
	array = list(map(int, input().split()))
	count = [0 for i in range(size + 1)]
	for i in range(size):
		if array[i] <= size:
			count[array[i]] += 1
		else:
			while array[i] > size:
				array[i] = array[i] // 2
			count[array[i]] += 1
	j = size
	while j > 0:
		if j == 1:
			if count[j] > 1:
				return False
		if j == size:
			if count[j] <= 0:
				return False
		if count[j] > 1:
			count[j // 2] += count[j] - 1
			count[j] = 1
		j -= 1
	for i in range(1, size + 1):
		if count[i] == 0:
			return False
	return True
remained_test_cases = 1
remained_test_cases = int(input())
while remained_test_cases > 0:
	if solve():
		print('YES')
	else:
		print('NO')
	remained_test_cases -= 1


c = int(input())
for i in range(c):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	res = 'YES'
	arr_sub = [False] * n
	for a in arr:
		if a <= n and arr_sub[a - 1] == False:
			arr_sub[a - 1] = True
		else:
			while a > n:
				a //= 2
			while arr_sub[a - 1] == True and a != 0:
				a //= 2
		if a == 0:
			res = 'NO'
			break
		else:
			arr_sub[a - 1] = True
	print(res)


def solve():
	n = int(input())
	arr = [int(x) for x in input().split()]
	s = set()
	for j in range(n):
		while arr[j] > n or arr[j] in s:
			arr[j] = arr[j] // 2
		if arr[j]:
			s.add(arr[j])
		else:
			print('NO')
			return
	print('YES')
for i in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	s = set([k for k in range(1, n + 1)])
	a = list(map(int, input().split()))
	flag = True
	for j in a:
		if j in s:
			s.remove(j)
		else:
			while True:
				j = j // 2
				if j in s:
					s.remove(j)
					break
				elif j == 0:
					flag = False
					break
		if flag == False:
			break
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	correct = set(range(1, n + 1))
	b = []
	stop = False
	for item in a:
		if stop:
			break
		while item > n:
			item = item // 2
		if item in b:
			while item in b:
				item = item // 2
				if item == 0:
					stop = True
					break
		b.append(item)
	if set(b) == correct:
		print('YES')
	else:
		print('NO')


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	values = list(map(int, input().split()))
	values.sort()
	permutation = set()
	for val in values:
		while val > n:
			val = val // 2
		while val:
			if val not in permutation:
				permutation.add(val)
				break
			val = val // 2
	if len(permutation) == n:
		print('YES')
	else:
		print('NO')


tst = int(input())
for i in range(tst):
	n = int(input())
	a = sorted([int(i) for i in input().split()])
	temp = [i for i in range(1, n + 1)]
	ans = []
	flag = True
	for i in a:
		if not flag:
			break
		while i > n:
			i = i >> 1
		while i in ans:
			i = i >> 1
			if i == 0:
				flag = False
				break
		ans.append(i)
	if set(ans) == set(range(1, n + 1)):
		print('YES')
	else:
		print('NO')