Read problems statements in [Mandarin Chinese], [Russian], and [Bengali] as well.

You are given an array A with N integers. You have to tell Chef whether this array is closed under multiplication. 

We say that an array is closed under multiplication if, for all sequences 1 ≤ S_{1} < S_{2} < \dots < S_{k} ≤ N,  there exists 1 ≤ x ≤ N such that A_{S_{1}} \cdot A_{S_{2}} \cdot \dots \cdot A_{S_{k}} = A_{x}. 

Output 1 if it is closed, and 0 otherwise.

------ Input Format ------ 

- The first line of the input contains T - the number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer - N
- The second line of each test case contains N space-separated integers - the i^{th} of which is A_{i}

------ Output Format ------ 

For each test case, output the answer on a new line. Output 1 if A is closed under multiplication, and 0 otherwise. 

------ Constraints ------ 

$1 ≤ T, N ≤ 10^{5}$
$-10^{9} ≤ A_{i}  ≤ 10^{9}$
- The sum of $N$ across all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
3
3
1 0 3
3
1 -1 -1
3
1 3 3
----- Sample Output 1 ------ 
1
1
0

----- explanation 1 ------ 
Test case $1$: $[1, 0, 3]$ is closed under multiplication.

$A_{1} \cdot A_{2} = 1 \cdot 0 = 0 = A_{2}$

$A_{1} \cdot A_{2} \cdot A_{3} = 1 \cdot 0 \cdot 3 = 0 = A_{2}$

$A_{1} \cdot A_{3} = 1 \cdot 3 = 3 = A_{3}$

$A_{2} \cdot A_{3} = 0 \cdot 3 = 0 = A_{2}$

Therefore, the answer for the first test case is $1$.

Test case $2$: $[1, -1, -1]$ is closed under multiplication.

$A_{1} \cdot A_{2} = 1 \cdot -1 = -1 = A_{2}$

$A_{1} \cdot A_{2} \cdot A_{3} = 1 \cdot -1 \cdot -1 = 1 = A_{1}$

$A_{1} \cdot A_{3} = 1 \cdot -1 = -1 = A_{2}$

$A_{2} \cdot A_{3} = -1 \cdot -1 = 1 = A_{1}$

Therefore, the answer for the second test case is $1$.

Test case $3$: $A_{2} \cdot A_{3} = 3 \cdot 3 = 9$ is not present in the array. Therefore, $[1, 3, 3]$ is not closed under multiplication, and the answer is $0$.

Difficulty: MEDIUM_HARD
Tags: Ad-hoc

Starter code:

Solutions:
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	ct0 = 0
	neg = 0
	ct = 0
	ct1 = 0
	for i in range(n):
		if a[i] == 0:
			ct0 += 1
		elif a[i] == 1:
			ct1 += 1
		elif a[i] < 0:
			neg += 1
		if abs(a[i]) >= 2:
			ct += 1
	pos = n - ct0 - neg
	if neg == 0:
		if ct >= 2:
			print(0)
		else:
			print(1)
	elif pos == 0:
		if neg >= 2:
			print(0)
		else:
			print(1)
	elif ct >= 2:
		print(0)
	elif ct == 1:
		if neg == 1 and pos == ct1:
			print(1)
		else:
			print(0)
	else:
		print(1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = 0
	c = 0
	o = 0
	z = 0
	r = 1
	for j in range(n):
		if l[j] == -1:
			c += 1
		elif l[j] == 1:
			x += 1
		elif l[j] == 0:
			z += 1
		else:
			o += 1
		if o > 1:
			r = 0
			print(0)
			break
	if r != 0:
		if c > 1 and x == 0:
			r = 0
		elif c and o:
			r = 0
		print(r)


t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	one = 0
	mo = 0
	o = 0
	z = 0
	res = 1
	for i in range(n):
		if arr[i] == -1:
			mo += 1
		elif arr[i] == 1:
			one += 1
		elif arr[i] == 0:
			z += 1
		else:
			o += 1
		if o > 1:
			res = 0
			print(0)
			break
	if res != 0:
		if mo > 1 and one == 0:
			res = 0
		elif mo and o:
			res = 0
		print(res)


import collections
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	freq = collections.Counter(a)
	big = n - freq[0] - freq[1] - freq[-1]
	if big > 1:
		print(0)
		continue
	if big == 1 and freq[-1] > 0:
		print(0)
		continue
	if freq[-1] > 1 and freq[1] == 0:
		print(0)
		continue
	print(1)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	a.sort()
	if a[0] < 0:
		s1 = a[0] * a[n - 1]
		s2 = max(a[0] * a[1], a[n - 1] * a[n - 2])
	else:
		s1 = a[0] * a[1]
		s2 = a[n - 1] * a[n - 2]
	if a[0] <= s1 and a[n - 1] >= s2:
		print(1)
	else:
		print(0)


from collections import *
for u in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(a, b, z, o) = (0, 0, 0, 0)
	for i in range(n):
		if l[i] == 0:
			z += 1
		elif l[i] == 1:
			a += 1
		elif l[i] == -1:
			b += 1
		else:
			o += 1
	if o >= 2:
		print(0)
	elif b > 1 and a == 0:
		print(0)
	elif o == 0:
		print(1)
	elif b > 0:
		print(0)
	else:
		print(1)


T = int(input())
ans = []
for test in range(T):
	N = int(input())
	A = input().split()
	ones = A.count('1')
	zeros = A.count('0')
	negs = A.count('-1')
	nums = len(A) - ones - zeros - negs
	if nums > 1:
		MAX = 0
	elif negs > 1 and ones == 0:
		MAX = 0
	elif nums > 0 and negs > 0:
		MAX = 0
	else:
		MAX = 1
	ans.append(MAX)
for a in ans:
	print(a)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	notnums = 0
	neg = 0
	pos = 0
	zero = 0
	for i in range(n):
		if l[i] == 0:
			zero += 1
		elif l[i] == -1:
			neg += 1
		elif l[i] == 1:
			pos += 1
		else:
			notnums += 1
	if notnums > 1:
		print(0)
	elif notnums and neg:
		print(0)
	elif neg > 1 and pos == 0:
		print(0)
	else:
		print(1)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l1 = Counter(map(int, input().split()))
	c = n - l1[0] - l1[1] - l1[-1]
	a = 0
	if c > 1:
		print(a)
	elif c == 1 and l1[-1] > 0:
		print(a)
	elif l1[-1] > 1 and l1[1] == 0:
		print(a)
	else:
		print(1)


from collections import Counter

def f1(n, l):
	l1 = Counter(l)
	c = n - l1[0] - l1[1] - l1[-1]
	a = 0
	if c > 1:
		print(a)
		return
	if c == 1 and l1[-1] > 0:
		print(a)
		return
	if l1[-1] > 1 and l1[1] == 0:
		print(a)
		return
	print(1)
for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	f1(n, l1)


from collections import Counter

def solve(n, nums):
	numCounts = Counter(nums)
	big = n - numCounts[0] - numCounts[1] - numCounts[-1]
	if big > 1:
		print(0)
		return
	if big == 1 and numCounts[-1] > 0:
		print(0)
		return
	if numCounts[-1] > 1 and numCounts[1] == 0:
		print(0)
		return
	print(1)
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	solve(n, nums)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	minus1 = 0
	gthan1 = 0
	count1 = 0
	zz = 0
	for i in range(N):
		if A[i] == -1:
			minus1 += 1
		if abs(A[i]) > 1:
			gthan1 += 1
		if A[i] == 1:
			count1 += 1
	if gthan1 > 1:
		zz = 1
	if minus1 and gthan1:
		zz = 1
	if minus1 > 2 and count1 == 0:
		zz = 1
	if zz:
		print('0')
	else:
		print('1')


test = int(input())
while test:
	n = int(input())
	arr = list(map(int, input().split()))
	neg = 0
	pos = 0
	for i in arr:
		if i == -1:
			neg += 1
		elif abs(i) > 1:
			pos += 1
	if pos > 1:
		print(0)
	elif neg > 1 and 1 not in arr:
		print(0)
	elif neg >= 1 and pos == 1:
		print(0)
	else:
		print(1)
	test -= 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c1 = 0
	c2 = 0
	for i in l:
		if i == -1:
			c1 += 1
		elif abs(i) > 1:
			c2 += 1
	if c2 > 1:
		print(0)
	elif c1 > 1 and 1 not in l:
		print(0)
	elif c1 >= 1 and c2 == 1:
		print(0)
	else:
		print(1)


test = int(input())
for t in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	pos_1 = 0
	neg_1 = 0
	for num in arr:
		if abs(num) > 1:
			c += 1
		if num == -1:
			neg_1 += 1
		if num == 1:
			pos_1 += 1
	if c > 1:
		print(0)
	elif c == 1 and neg_1 > 0:
		print(0)
	elif neg_1 > 1 and pos_1 == 0:
		print(0)
	else:
		print(1)


t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = [int(i) for i in input().split()]
	d = {0: 0, 1: 0, 2: 0, -1: 0}
	flag = 0
	for i in arr:
		if i == 0:
			d[i] += 1
		elif i == 1:
			d[i] += 1
		elif i == -1:
			d[i] += 1
		else:
			d[2] += 1
		if d[2] > 1:
			flag = 1
			break
	if flag == 1:
		print(0)
	elif d[2] == 1:
		if d[-1] >= 1:
			print(0)
		else:
			print(1)
	elif d[-1] > 1 and d[1] == 0:
		print(0)
	else:
		print(1)


import sys
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(grt, cn1, cp1) = (0, 0, 0)
	for i in range(n):
		if abs(arr[i]) > 1:
			grt = grt + 1
		if arr[i] == -1:
			cn1 = cn1 + 1
		if arr[i] == 1:
			cp1 = cp1 + 1
	if cn1 > 0 and grt != 0:
		print(0)
	elif cn1 > 1 and cp1 == 0:
		print(0)
	elif grt > 1:
		print(0)
	else:
		print(1)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = True
	(grt, cn1, cp1) = (0, 0, 0)
	for i in range(n):
		if abs(arr[i]) > 1:
			grt = grt + 1
		if arr[i] == -1:
			cn1 = cn1 + 1
		if arr[i] == 1:
			cp1 = cp1 + 1
	if cn1 > 0 and grt != 0:
		ans = False
	if cn1 > 1 and cp1 == 0:
		ans = False
	if grt > 1:
		ans = False
	if ans:
		print(1)
	else:
		print(0)


T = int(input())

def find_closure(arr, index, val, arr_set):
	if val not in arr_set:
		return 0
	if index >= len(arr):
		return 1
	val_choose = val * arr[index]
	a = find_closure(arr, index + 1, val_choose, arr_set)
	b = find_closure(arr, index + 1, val, arr_set)
	c = find_closure(arr, index + 1, arr[index], arr_set)
	if a == 0 or b == 0 or c == 0:
		return 0
	return 1
for t in range(T):
	n = int(input())
	arr = [int(i) for i in str(input()).split()]
	arr = sorted(arr)
	arr_set = set(arr)
	if n == 1:
		print(1)
	elif arr[-1] > 1 and arr[-2] > 1:
		print(0)
	elif arr[0] < -1 and arr[1] <= -1:
		print(0)
	elif arr[-1] * arr[0] not in arr:
		print(0)
	elif arr[-1] > 1 and arr[0] <= -1:
		print(0)
	elif arr[0] == -1 and arr[1] == -1 and (1 not in arr_set):
		print(0)
	else:
		print(1)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = no = o = 0
	for num in arr:
		if num not in (1, 0, -1):
			cnt += 1
		if num == 1:
			o += 1
		if num == -1:
			no += 1
	if cnt > 1:
		print(0)
	elif no > 1 and o == 0:
		print(0)
	elif no > 0 and cnt > 0:
		print(0)
	else:
		print(1)


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		l = list(map(int, input().split()))
		a = l.count(1)
		b = l.count(-1)
		c = l.count(0)
		d = n - (a + b + c)
		if d > 1:
			print(0)
		elif d == 1:
			if b > 0:
				print(0)
			else:
				print(1)
		elif d == 0:
			if b > 1:
				if a >= 1:
					print(1)
				else:
					print(0)
			elif b == 1 or b == 0:
				print(1)
except:
	pass


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = [int(x) for x in input().split()]
		c1 = 0
		c2 = 0
		for i in range(N):
			if abs(A[i]) > 1:
				c1 += 1
				c2 = A[i]
		if c1 > 1:
			print(0)
		elif c1 == 1:
			if -1 in A:
				print(0)
			else:
				print(1)
		elif c1 == 0:
			d = A.count(-1)
			b = A.count(1)
			if b == 0 and d > 1:
				print(0)
			else:
				print(1)
main()


for i in range(int(input())):
	n = int(input())
	one = 0
	mone = 0
	zero = 0
	other = 0
	l = list(map(int, input().split()))
	for i in range(len(l)):
		if l[i] == 0:
			zero += 1
		elif l[i] == 1:
			one += 1
		elif l[i] == -1:
			mone += 1
		else:
			other += 1
	if other > 1:
		print(0)
	elif mone > 1 and one == 0:
		print(0)
	elif other and mone:
		print(0)
	else:
		print(1)


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	z = 0
	o = 0
	mo = 0
	go = 0
	for i in range(n):
		if a[i] == 0:
			z += 1
		elif a[i] == 1:
			o += 1
		elif a[i] == -1:
			mo += 1
		else:
			go += 1
	if go > 1:
		print(0)
	elif mo > 1 and o == 0:
		print(0)
	elif go and mo:
		print(0)
	else:
		print(1)


t = int(input())
for z in range(t):
	n = int(input())
	li = [int(x) for x in input().split()]
	c0 = 0
	c1 = 0
	c = 0
	c_1 = 0
	for i in li:
		if i == 0:
			c0 = c0 + 1
		elif i == 1:
			c1 = c1 + 1
		elif i == -1:
			c_1 = c_1 + 1
		else:
			c = c + 1
	if c >= 2:
		print(0)
	elif c == 1 and c_1 >= 1:
		print(0)
	elif c1 == 0 and c_1 > 1:
		print(0)
	else:
		print(1)


def solve(n, arr):
	mul = 1
	for i in range(n - 1):
		mul = arr[i] * arr[i + 1]
		if mul in arr:
			pass
		else:
			return 0
	return 1
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	d = {int(i): 1 for i in arr}
	(total, count, neg) = (1, 0, 0)
	for i in arr:
		if i != 0:
			total = total * i
			if i > 1 or i < -1:
				count += 1
			elif i == -1:
				neg += 1
			try:
				if d[total]:
					pass
			except:
				print(0)
				break
			if neg > 1 or (neg == 1 and count == 1):
				try:
					if d[-total]:
						pass
				except:
					print(0)
					break
			if count > 1:
				print(0)
				break
	else:
		print(1)
	t -= 1


from collections import Counter
t = int(input())
for tt in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	freq = Counter(arr)
	if len(freq) > 3:
		print(0)
		continue
	(minus, zero, plus, other) = (0, 0, 0, 0)
	if -1 in freq.keys():
		minus = freq[-1]
	if 0 in freq.keys():
		zero = freq[0]
	if 1 in freq.keys():
		plus = freq[1]
	other = n - (minus + zero + plus)
	if other > 1:
		print(0)
		continue
	if other == 1:
		if minus > 0:
			print(0)
		else:
			print(1)
	elif minus > 1:
		if plus > 0:
			print(1)
		else:
			print(0)
	else:
		print(1)


t = int(input())
for i in range(t):
	n = input()
	a = input()
	(c0, c1, cn1, cpos, cneg) = (0, 0, 0, 0, 0)
	for i in a.split():
		if i == '1':
			c1 += 1
		elif i == '0':
			c0 += 1
		elif i == '-1':
			cn1 += 1
		elif int(i) > 0:
			cpos += 1
		else:
			cneg += 1
	if cpos + cneg > 1 or (cn1 > 1 and c1 == 0) or (cpos + cneg > 0 and cn1 > 0):
		print('0')
	else:
		print('1')


from sys import stdin
from collections import Counter
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = []
	c = Counter()
	for i in range(n):
		if a[i] != 0:
			if c[a[i]] < 2:
				c[a[i]] += 1
				b.append(a[i])
	if len(b) > 10:
		print(0)
		continue
	for bitmask in range(1, 2 ** len(b)):
		product = 1
		for i in range(bitmask.bit_length()):
			if bitmask >> i & 1 == 1:
				product *= b[i]
		if product not in b:
			print(0)
			break
	else:
		print(1)


for _ in range(int(input())):
	_ = int(input())
	l = list(map(int, input().split()))
	d = {int(i): 1 for i in l}
	(total, count, neg) = (1, 0, 0)
	for i in l:
		if i != 0:
			total *= i
			if i > 1 or i < -1:
				count += 1
			elif i == -1:
				neg += 1
			try:
				if d[total]:
					pass
			except:
				print(0)
				break
			if neg > 1 or (neg == 1 and count == 1):
				try:
					if d[-total]:
						pass
				except:
					print(0)
					break
			if count > 1:
				print(0)
				break
	else:
		print(1)


def solveE(N, A):
	set_A = set(A)
	(p_1, m_1, x) = (False, False, None)
	if 1 in set_A:
		p_1 = True
		set_A.remove(1)
	if -1 in set_A:
		m_1 = True
		set_A.remove(-1)
	if 0 in set_A:
		set_A.remove(0)
	if set_A:
		x = next(iter(set_A))
	if len(set_A) > 1 or A.count(x) > 1 or (x and m_1) or (A.count(-1) > 1 and (not p_1)):
		return 0
	else:
		return 1
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	print(solveE(N, A))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	if n == 1:
		print(0)
		continue
	total = 0
	zeros = l.count(0)
	ones = l.count(1)
	if -1 in l:
		minusone = l.count(-1)
		total += zeros + minusone + ones
		if total == n:
			if zeros != 0 and ones != 0:
				print(1)
			elif zeros == 0 and ones == 0:
				print(0)
			elif zeros != 0 and ones == 0:
				if minusone == 1:
					print(1)
				else:
					print(0)
			elif zeros == 0 and ones != 0:
				print(1)
		else:
			print(0)
	else:
		total += zeros + ones
		if total == n or total == n - 1:
			print(1)
		else:
			print(0)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	dict = {}
	for i in arr:
		if i in dict:
			dict[i] += 1
		else:
			dict[i] = 1
	arr = sorted(arr)
	flag = None
	if arr[0] * arr[1] in dict.keys() and arr[0] * arr[n - 1] in dict.keys() and (arr[n - 1] * arr[n - 2] in dict.keys()):
		flag = True
	else:
		flag = False
	if flag:
		print(1)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	one = arr.count(1)
	zero = arr.count(0)
	minus_one = arr.count(-1)
	other = n - one - zero - minus_one
	if other > 1:
		print(0)
	elif n == 2:
		print(int(arr[0] * arr[1] in arr))
	elif n == 1:
		print(1)
	elif arr[0] * arr[1] in arr and arr[0] * arr[-1] in arr and (arr[-1] * arr[-2] in arr):
		print(1)
	else:
		print(0)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	q = Counter(l)
	c = n - q[0] - q[1] - q[-1]
	if c > 1 or (q[-1] > 0 and c >= 1) or (q[-1] > 1 and q[1] == 0):
		print(0)
	else:
		print(1)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	a = l.count(1)
	b = l.count(-1)
	c = l.count(0)
	d = n - (a + b + c)
	if d > 1:
		print('0')
	elif d == 1:
		if b > 0:
			print('0')
		if b == 0:
			print('1')
	elif d == 0:
		if b == 0:
			print('1')
		if b == 1:
			print('1')
		if b > 1:
			if a > 0:
				print('1')
			else:
				print('0')
	t -= 1


for tc in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	dis = dict()
	for x in ls:
		if dis.get(x) is None:
			dis[x] = 1
		else:
			dis[x] += 1
	cnt = 0
	for x in ls:
		if abs(x) > 1:
			cnt += 1
	if cnt > 1:
		print(0)
	elif dis.get(-1) is not None:
		if dis[-1] >= 2 and dis.get(1) is None:
			print(0)
		elif dis[-1] > 0 and cnt == 1:
			print(0)
		else:
			print(1)
	else:
		print(1)


def solve(n, Arr):
	onePresent = 1 in Arr
	_Arr = [item for item in Arr if item not in [0, 1, -1]]
	l = len(_Arr)
	if l > 1:
		return 0
	negativeOne = Arr.count(-1)
	if negativeOne == 0:
		return 1
	if l == 0:
		if negativeOne > 1 and onePresent:
			return 1
		elif negativeOne > 1 and (not onePresent):
			return 0
		else:
			return 1
	elif negativeOne == 0:
		return 1
	else:
		return 0
for _ in range(int(input())):
	n = int(input())
	Arr = list(map(int, input().split()))
	Ans = solve(n, Arr)
	if Ans is None:
		print(1 / 0)
	print(Ans)


try:
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		count_ = 0
		count_ve = 0
		count_1 = 0
		count_0 = 0
		for i in range(n):
			if l[i] != 0 and l[i] != 1 and (l[i] != -1):
				count_ += 1
			if l[i] == -1:
				count_ve += 1
			if l[i] == 0:
				count_0 += 1
			if l[i] == 1:
				count_1 += 1
		if count_0 == 0 and count_1 == 0:
			print(0)
			continue
		if count_ve > 1 and count_1 == 0:
			print(0)
			continue
		if count_ >= 1 and count_ve >= 1:
			print(0)
			continue
		if count_ >= 2:
			print(0)
			continue
		print(1)
except:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	mo = 0
	o = 0
	cl = 0
	cg = 0
	for i in l:
		if i > 1:
			cg += 1
		elif i < -1:
			cl += 1
		elif i == 1:
			o += 1
		elif i == -1:
			mo += 1
	if cg > 1 or cl > 1 or cl + cg > 1:
		print(0)
	elif cg == 1 and mo > 0 or (cl == 1 and mo > 0):
		print(0)
	elif mo > 1 and o == 0:
		print(0)
	else:
		print(1)


def solve(array):
	count_greater = 0
	count_lesser = 0
	negative = 0
	positive = 0
	for x in array:
		if x > 1:
			count_greater += 1
		elif x < -1:
			count_lesser += 1
		elif x == -1:
			negative += 1
		elif x == 1:
			positive += 1
	if count_greater > 1 or count_lesser > 1 or count_lesser + count_greater > 1:
		return 0
	if count_greater == 1 and negative > 0:
		return 0
	if count_lesser == 1 and negative > 0:
		return 0
	if negative > 1 and positive == 0:
		return 0
	return 1
test = int(input())
for _ in range(test):
	n = input()
	array = [int(x) for x in input().split()]
	print(solve(array))


T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	ct = 0
	(negs, pos) = (0, 0)
	for i in range(n):
		negs += arr[i] == -1
		pos += arr[i] == 1
		if abs(arr[i]) > 1:
			ct += 1
			if ct >= 2:
				break
	if ct >= 2:
		print(0)
		continue
	if negs > 1 and pos == 0:
		print(0)
		continue
	if negs > 0 and ct == 1:
		print(0)
		continue
	print(1)


from collections import Counter
t = int(input())
while t:
	n = int(input())
	ans = 0
	l = list(map(int, input().split()))
	l = dict(Counter(l))
	if -1 in l:
		if 0 in l:
			l.pop(0)
		if 1 in l:
			x = l[1]
			l.pop(1)
		else:
			x = 0
		y = l[-1]
		l.pop(-1)
		if len(l) == 0:
			if y == 1:
				ans = 1
			elif y > 1 and x > 0:
				ans = 1
			else:
				ans = 0
		else:
			ans = 0
	else:
		if 1 in l:
			l.pop(1)
		if 0 in l:
			l.pop(0)
		if len(l) > 1:
			ans = 0
		elif len(l) == 0:
			ans = 1
		elif len(l) == 1:
			l = list(l.values())
			if l[0] == 1:
				ans = 1
			else:
				ans = 0
	print(ans)
	t = t - 1


def solve(n, A):
	cnt = 0
	zero = 0
	one = 0
	neg = 0
	for num in A:
		if num > 1 or num < -1:
			cnt += 1
		elif num == -1:
			neg += 1
		elif num == 1:
			one += 1
		elif num == 0:
			zero += 1
		if cnt >= 2:
			return 0
	if cnt == 1:
		if neg >= 1:
			return 0
	if neg >= 2:
		if one == 0:
			return 0
	return 1
t = int(input())
for _ in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	ans = solve(n, A)
	print(ans)


import sys
tests = int(input())
for test in range(tests):
	n = int(input())
	ar = [int(i) for i in input().split()]
	zeroes = ar.count(0)
	ones = ar.count(1)
	neg_ones = ar.count(-1)
	other_count = n - zeroes - ones - neg_ones
	if other_count > 1:
		print(0)
	elif neg_ones > 1 and ones == 0:
		print(0)
	elif other_count == 0:
		print(1)
	elif neg_ones > 0:
		print(0)
	else:
		print(1)


def Solve(arr):
	minusonecount = 0
	onecount = 0
	bigcount = 0
	for i in arr:
		if i == -1:
			minusonecount += 1
		if i == 1:
			onecount += 1
		if abs(i) > 1:
			bigcount += 1
	if bigcount > 1:
		return False
	if minusonecount >= 2 and onecount == 0:
		return False
	if minusonecount > 0 and bigcount > 0:
		return False
	return True
test = int(input())
while test:
	l = int(input())
	arr = list(map(int, input().strip().split()))
	print(1) if Solve(arr) else print(0)
	test -= 1


import sys
import os.path
import heapq
import math
import copy
from sys import stdin, stdout
from collections import *
from math import gcd, ceil, floor
mod = int(1000000000.0 + 7)
m1 = float('inf')
if os.path.exists('Updated prg/Input3d.txt'):
	sys.stdout = open('Updated prg/Output3d.txt', 'w')
	sys.stdin = open('Updated prg/Input3d.txt', 'r')

def sinp():
	return input()

def ninp():
	return int(sinp())

def mapinp():
	return map(int, sinp().split())

def smapinp():
	return map(str, sinp().split())

def linp():
	return list(mapinp())

def sl():
	return list(sinp().split())

def power(n):
	return 1 << n

def prnt(a):
	print(a)

def prntl(a):
	print(a, end=' ')

def prntlist(l1):
	print(*l1)
for _ in range(ninp()):
	n = ninp()
	a = linp()
	count = Counter(a)
	c = 0
	for i in a:
		if abs(i) > 1:
			c = c + 1
	(a1, b) = (count[1], count[-1])
	if c > 1:
		prnt(0)
	elif b > 1 and a1 == 0:
		prnt(0)
	elif b >= 1 and c == 1:
		prnt(0)
	else:
		prnt(1)


t = int(input())
for test in range(t):
	d = {0: 0, 1: 0, -1: 0, 'a': 0}
	n = int(input())
	s = list(map(int, input().split()))
	for i in s:
		if i == 0:
			d[0] += 1
		elif i == 1:
			d[1] += 1
		elif i == -1:
			d[-1] += 1
		else:
			d['a'] += 1
	if n - (d[0] + d[1] + d[-1]) <= 1:
		if d['a'] == 1 and d[-1] > 0:
			print(0)
		elif d[-1] > 1 and d[1] == 0:
			print(0)
		else:
			print(1)
	elif n == 1:
		print(1)
	else:
		print(0)


def closChef(n, arr):
	output = 1
	mapNum = {'greaterThanOne': 0, 'minusone': 0, 'ones': 0}
	for num in arr:
		if abs(num) > 1:
			mapNum['greaterThanOne'] = mapNum['greaterThanOne'] + 1
		elif num == -1:
			mapNum['minusone'] = mapNum['minusone'] + 1
		elif num == 1:
			mapNum['ones'] = mapNum['ones'] + 1
	if mapNum['greaterThanOne'] > 1:
		output = 0
	elif mapNum['greaterThanOne'] == 1 and mapNum['minusone'] > 0:
		output = 0
	elif mapNum['greaterThanOne'] == 0 and mapNum['minusone'] > 1 and (mapNum['ones'] == 0):
		output = 0
	return output
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	print(closChef(n, arr))


import sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	(onp, ong, zer) = (arr.count(1), arr.count(-1), arr.count(0))
	for i in arr:
		if i == 1 or i == -1 or i == 0:
			continue
		ans += 1
	if ans > 1:
		print(0)
		continue
	if ong == 0:
		print(1)
		continue
	if onp == 0:
		if ong > 1:
			print(0)
		elif ans == 0:
			print(1)
		else:
			print(0)
		continue
	if ans:
		print(0)
		continue
	print(1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	ans = 1
	lst = [1, -1, 0]
	for i in arr:
		if i not in lst:
			count += 1
		if count > 1:
			ans = 0
			break
	if ans == 1:
		if count == 1 and arr.count(-1) > 0:
			ans = 0
		elif arr.count(-1) > 1 and 1 not in arr:
			ans = 0
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	if 1 not in l and -1 not in l and (0 not in l):
		print(0)
	elif -1 in l and max(l) > 1:
		print(0)
	elif l.count(-1) > 1 and 1 not in l:
		print(0)
	elif n == 2 and (1 in l or 0 in l):
		print(1)
	else:
		l.sort()
		if l[-1] * l[-2] not in l:
			print(0)
		elif l[0] * l[1] not in l:
			print(0)
		else:
			print(1)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
from math import inf, ceil, sqrt
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	v = [0, 0, 0, 0]
	for e in a:
		if abs(e) > 1:
			v[3] += 1
		else:
			v[e + 1] += 1
	ans = 1
	if v[3] > 1:
		ans = 0
	if v[3] and v[0]:
		ans = 0
	if v[0] > 1 and (not v[2]):
		ans = 0
	print(ans)


def solution(arr, n):
	if n == 1:
		return 1
	d = {}
	d['0'] = 0
	d['1'] = 0
	d['-1'] = 0
	d['u'] = 0
	for i in range(n):
		if arr[i] == 0:
			d['0'] = d['0'] + 1
		elif arr[i] == 1:
			d['1'] = d['1'] + 1
		elif arr[i] == -1:
			d['-1'] = d['-1'] + 1
		else:
			d['u'] = d['u'] + 1
	if d['u'] == 1:
		if d['-1'] == 0:
			return 1
	if d['-1'] == 1 and d['u'] == 0:
		return 1
	if d['-1'] != 0 and d['u'] == 0 and (d['1'] != 0):
		return 1
	if d['u'] == 0 and d['-1'] == 0:
		return 1
	return 0
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solution(arr, n))


import collections

def closure(arr, n):
	freq = collections.Counter(arr)
	big = n - freq[0] - freq[-1] - freq[1]
	if big > 1:
		return 0
	if big == 1 and freq[-1]:
		return 0
	if freq[-1] > 1 and freq[1] == 0:
		return 0
	return 1
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(closure(arr, n))


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	l0 = li.count(0)
	l1 = li.count(1)
	l2 = li.count(-1)
	if n == l0 + l1 + l2:
		if l2 > 1:
			if l1 == 0:
				print(0)
			else:
				print(1)
		else:
			print(1)
	elif n == l0 + l1 + 1:
		print(1)
	else:
		print(0)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	big_num_count = 0
	present_negative_one = 0
	negative_one_count = 0
	present_positive_one = 0
	zero_count = 0
	for i in range(n):
		if a[i] <= -2 or a[i] >= 2:
			big_num_count += 1
		if a[i] == -1:
			present_negative_one = 1
			negative_one_count += 1
		if a[i] == 1:
			present_positive_one = 1
		if a[i] == 0:
			zero_count += 1
	if zero_count == n:
		print(1)
	elif big_num_count >= 2:
		print(0)
	elif big_num_count == 1:
		if present_negative_one:
			print(0)
		else:
			print(1)
	elif negative_one_count == 1:
		print(1)
	elif present_positive_one:
		print(1)
	else:
		print(0)


def mgc(a):
	count = 0
	neg_one = 0
	pos_one = 0
	for i in a:
		if i == -1:
			neg_one += 1
		if i == 1:
			pos_one += 1
		if abs(i) > 1:
			count += 1
	if count > 1:
		return 0
	if neg_one > 1 and pos_one == 0:
		return 0
	if neg_one > 0 and count > 0:
		return 0
	return 1
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(mgc(a))


T = int(input())
for t in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	zcount = count = ngcount = 0
	for i in range(N):
		if arr[i] == 0:
			zcount += 1
		elif arr[i] == 1:
			count += 1
		elif arr[i] == -1:
			ngcount += 1
	if ngcount:
		if ngcount > 1 and (not count) or zcount + count + ngcount != N:
			print(0)
		else:
			print(1)
	elif zcount + count >= N - 1:
		print(1)
	else:
		print(0)


t = int(input())
for z in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if n == 1:
		print(1)
	else:
		s1 = a.count(0)
		s2 = a.count(1)
		s3 = a.count(-1)
		if s3 == 0 and (s1 + s2 == n or s1 + s2 + 1 == n or s1 == n or (s2 == n)):
			print(1)
		elif s3 > 0:
			if s2 == 0 and s3 == 1 and (s1 + s3 == n):
				print(1)
			elif s2 > 0 and s1 + s2 + s3 == n:
				print(1)
			else:
				print(0)
		else:
			print(0)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	c1 = l.count(-1)
	c2 = l.count(1)
	c3 = l.count(0)
	num = n - c1 - c2 - c3
	if num > 1:
		print(0)
		continue
	if c1 > 1 and c2 == 0:
		print(0)
		continue
	if num == 1 and c1 > 0:
		print(0)
		continue
	print(1)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	c = 0
	minus = 0
	one = False
	for ele in l:
		if ele != 0:
			if ele == 1:
				one = True
			elif ele == -1:
				minus += 1
			else:
				c += 1
	print(0) if c > 1 or (minus and c == 1) or (minus > 1 and (not one)) else print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	zero = 0
	one = 0
	extra = 0
	mone = 0
	for i in range(n):
		if arr[i] == 1:
			one += 1
		elif arr[i] == -1:
			mone += 1
		elif arr[i] == 0:
			zero += 1
		else:
			extra += 1
	if extra > 1:
		ans = 0
	elif extra == 1:
		if mone > 0:
			ans = 0
		else:
			ans = 1
	elif mone > 1 and one > 1:
		ans = 1
	elif mone > 1 and one == 1:
		ans = 1
	elif mone > 1 and one == 0:
		ans = 0
	else:
		ans = 1
	print(ans)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	l = list(map(int, sys.stdin.readline().split()))
	s = set(l)
	mul = 1
	f = 1
	for i in range(n):
		if l[i] == 0:
			continue
		mul *= l[i]
		if mul not in s:
			f = 0
			break
	sys.stdout.write(str(f) + '\n')


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	p1 = n1 = ln = 0
	for i in a:
		if i == 1:
			p1 += 1
		elif i == -1:
			n1 += 1
		elif abs(i) > 1:
			ln += 1
	if ln > 1:
		print('0')
	elif ln == 1 and n1 >= 1:
		print('0')
	elif n1 > 1 and p1 == 0:
		print('0')
	else:
		print('1')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	s = set(a)
	t = s.copy()
	s.discard(0)
	s.discard(1)
	if len(s) > 1:
		print(0)
		continue
	elif len(s) == 1:
		e = min(s)
		c = a.count(e)
		if e != -1 and c > 1 or (e == -1 and c > 1 and (1 not in t)):
			print(0)
			continue
	print(1)


import math
import sys

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

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

def binarySearch(a, item, l, r):
	while l <= r:
		mid = (l + r) // 2
		if a[mid] == item:
			return mid
		if a[mid] < item:
			l = mid + 1
		else:
			r = mid - 1
	return -1

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def _01knapsack(W, wt, p, n):
	k = [[0 for i in range(W + 1)] for i in range(n + 1)]
	for x in range(n + 1):
		for w in range(W + 1):
			if x == 0 or w == 0:
				k[x][w] = 0
			elif wt[x - 1] <= w:
				k[x][w] = max(k[x - 1][w], k[x - 1][w - wt[x - 1]] + p[x - 1])
			else:
				k[x][w] = k[x - 1][w]
	return k[n][W]

def solve():
	n = int(input())
	s = arr()
	if n == 1:
		print(1)
	else:
		s.sort()
		a = s[0]
		b = s[1]
		c = s[n - 2]
		d = s[n - 1]
		if a * b not in s or d * c not in s or a * d not in s:
			print(0)
		else:
			print(1)
t = int(input())
for _ in range(t):
	solve()