You are given $4n$ sticks, the length of the $i$-th stick is $a_i$.

You have to create $n$ rectangles, each rectangle will consist of exactly $4$ sticks from the given set. The rectangle consists of four sides, opposite sides should have equal length and all angles in it should be right. Note that each stick can be used in only one rectangle. Each stick should be used as a side, you cannot break the stick or use it not to the full length.

You want to all rectangles to have equal area. The area of the rectangle with sides $a$ and $b$ is $a \cdot b$.

Your task is to say if it is possible to create exactly $n$ rectangles of equal area or not.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 500$) — the number of queries. Then $q$ queries follow.

The first line of the query contains one integer $n$ ($1 \le n \le 100$) — the number of rectangles.

The second line of the query contains $4n$ integers $a_1, a_2, \dots, a_{4n}$ ($1 \le a_i \le 10^4$), where $a_i$ is the length of the $i$-th stick.


-----Output-----

For each query print the answer to it. If it is impossible to create exactly $n$ rectangles of equal area using given sticks, print "NO". Otherwise print "YES".


-----Example-----
Input
5
1
1 1 10 10
2
10 5 2 10 1 1 2 5
2
10 5 1 10 5 1 1 1
2
1 1 1 1 1 1 1 1
1
10000 10000 10000 10000

Output
YES
YES
NO
YES
YES

Difficulty: introductory

Starter code:

Solutions:
for _ in range(int(input())):
    n = int(input())
    A = list(map(int, input().split()))
    B = {}
    for i in A:
        if i not in B:
            B[i] = 0
        B[i] += 1
    ans = 'YES'
    J = []
    for i in B:
        if B[i] % 2:
            ans = 'NO'
            break
        else:
            for _ in range(B[i] // 2):
                J.append(i)
    if ans == 'YES':
        J.sort()
        s = set()
        for i in range(n):
            s.add(J[i] * J[-i-1])
        if len(s) != 1:
            ans = 'NO'
    print(ans)

from sys import stdin
from collections import deque
q=int(stdin.readline().strip())
for i in range(q):
    n=int(stdin.readline().strip())
    s=list(map(int,stdin.readline().strip().split()))
    s.sort()
    s=deque(s)
    t=True
    A=s[0]*s[-1]
    while len(s)>0:
        a1=s[0]*s[-1]
        if a1!=A or s[0]!=s[1] or s[-1]!=s[-2]:
            t=False
            break
        s.popleft()
        s.popleft()
        s.pop()
        s.pop()
    if t :
        print("YES")
    else:
        print("NO")
        


q = int(input())
for i in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	for i in range(0, 2 * n, 2):
		if a[i] != a[i + 1] or a[-i-1] != a[-i-2]:
			print('NO')
			break
		if i == 0:
			area = a[i] * a[-i-1]
		else:
			if area != a[i] * a[-i-1]:
				print('NO')
				break
	else:
		print('YES')



T = int(input())
for t in range(T):
    n = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    ok = 1
    areas = []
    left = 0

    right = 4*n - 1
    for i in range(n):
        l1 = left
        l2 = left + 1

        r1 = right
        r2 = right - 1
        
        if not (A[l1] == A[l2] and A[r1] == A[r2]):
            ok = 0    
        areas.append(A[l1]*A[r1])

        left += 2
        right -= 2
        
    #print(areas, ok)
    if len(set(areas)) == 1 and ok:
        print('YES')
    else:
        print('NO')


q = int(input())
for _ in range(q):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    pos = True
    for i in range(0, 4 * n, 2):
        if a[i] != a[i + 1]:
            pos = False
            break
    area = a[0] * a[-1]
    if pos:
        for i in range(2, 2 * n, 2):
            pos = pos and a[i] * a[-i - 1] == area
    print('YES' if pos else 'NO')


for _ in range(int(input())):
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort()
    i = 1
    j = len(a)-2
    ans = "YES"
    area = a[0]*a[-1]
    while i<j:
        if a[i] == a[i-1] and a[j] == a[j+1] and a[i]*a[j]==area:
            i+=2
            j-=2
        else:
            ans = "NO"
            break
    print(ans)

for _ in range(int(input())):
    n = int(input())
    a = list(sorted(map(int, input().split())))
    b = []
    for i in range(0, len(a), 2):
        if a[i + 1] != a[i]:
            print("NO")
            break
        b.append(a[i])
    else:
        s = b[0] * b[-1]
        for j in range(1, len(a) // 2):
            if b[j] * b[-j-1] != s:
                print("NO")
                break
        else:
            print("YES")

def main():
  q = int(input())
  for _ in range(q):
    n = int(input())
    slist = list(sorted(map(int, input().split())))
    li, ri = 0, 4*n-1
    ans = None
    for j in range(n):
      if slist[li] != slist[li+1] or slist[ri] != slist[ri-1]:
        print('NO')
        break
      if ans is None:
        ans = slist[li]*slist[ri]
        li += 2
        ri -= 2
      else:
        if ans != slist[li]*slist[ri]:
          print('NO')
          break
        else:
          li += 2
          ri -= 2
    else:
      print('YES')


def __starting_point():
  main()

__starting_point()

Q = int(input())
for q in range(Q):
    N = int(input())
    A = sorted([int(a) for a in input().split()])
    S = A[0] * A[-1]
    i, j = 0, 4*N-1
    for _ in range(N):
        if not(A[i] == A[i+1] and A[j] == A[j-1] and A[i] * A[j] == S):
            print("NO")
            break
        i += 2
        j -= 2
    else:
        print("YES")


q=int(input())
for i in range(q):
    t=int(input())
    arr=[int(x) for x in input().split()]
    arr.sort()
    pos=True
    lengths=[]
    for j in range(2*t):
        if arr[2*j]!=arr[2*j+1]:
            pos=False
            break
        lengths.append(arr[2*j])
    if pos==True:
        area=lengths[0]*lengths[2*t-1]
        for j in range(t-1):
            if lengths[1+j]*lengths[2*t-2-j]!=area:
                pos=False
                break
    if pos==True:
        print("YES")
    else:
        print("NO")
        


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

t=int(input())


for i in range(t):
    n=int(input())
    ns=gns()
    ns.sort()
    a=ns[0]*ns[-1]
    f=True
    for i in range(4*n):
        if i%2==1:
            continue
        if ns[i]!=ns[i+1]:
            f=False
            break
    if not f:
        print('NO')
        continue
    for i in range(4*n):
        if ns[i]*ns[4*n-1-i]!=a:
            f=False
            break
    if not f:
        print('NO')
        continue
    print('YES')





#579_B

import sys

q = int(input())

for i in range(0, q):
    n = int(input())
    ln = [int(j) for j in sys.stdin.readline().rstrip().split(" ")]
    ln = sorted(ln)
    f = True
    for j in range(1, len(ln), 2):
        if ln[j] != ln[j - 1]:
            f = False

    ind1 = 0
    ind2 = len(ln) - 2
    sm = ln[ind1] * ln[ind2]
    while ind1 < ind2:
        ind1 += 2
        ind2 -= 2
        if ln[ind1] * ln[ind2] != sm:
            f = False
            break
    if f:
        print("YES")
    else:
        print("NO")


q = int(input())
for _ in range(q):
    n = int(input())
    a = list(map(int, input().split()))

    def solve(a):
        from collections import Counter
        c = Counter(a)
        keys = sorted(c)
        for key in keys:
            if c[key] % 2 != 0:
                return False
        temp = [[k]*c[k] for k  in keys]
        keys = []
        for t in temp:
            keys += t
        area = keys[0] * keys[-1]
        head = 0
        tail = len(keys) - 1
        if len(keys) % 2 != 0:
            return False
        while head < tail:
            if keys[head] * keys[tail] != area:
                return False
            head += 1
            tail -= 1
        return True
    print("YES" if solve(a) else "NO")


import sys
input=sys.stdin.readline
def query(n,A):
    A.sort()
    B=[]
    for i in range(0,n*4,2):
        if A[i]!=A[i+1]:
            return 'NO'
        B.append(A[i])
    s=B[0]*B[-1]
    for i in range(n*2):
        if B[i]*B[-i-1]!=s:
            return 'NO'
    return 'YES'

q=int(input())
for _ in range(q):
    n=int(input())
    A=list(map(int,input().split()))
    print(query(n,A))

for _ in range(int(input())):
	n=int(input())
	l=list(map(int,input().split()))
	d1={}
	for i in l:
		if i in d1:
			d1[i]+=1

		else:
			d1[i]=1

	f=True
	li=[]
	for i in d1:
		if d1[i]%2!=0:
			f=False
			break
		else:
			li.extend([i]*(d1[i]//2))

	if f:
		li.sort()
		c=li[0]*li[-1]
		i=1
		j=len(li)-2
		while i<j:
			if c!=li[i]*li[j]:
				f=False
				break

			else:
				i+=1
				j-=1
		if f:
			print("YES")

		else:
			print("NO")

	else:
		print("NO")



t = int(input())
for u in range(t):
	n = int(input())
	n = n*4
	x = list(map(int, input().split()))
	x.sort()
	i = 0
	f = []
	while(i < n):
		if(x[i]==x[i+1]):
			f += [x[i]]
			i += 2
		else:
			break
	ans = "YES"
	if(len(f)==n//2):
		ar = f[0]*f[-1]
		i = 0
		j = len(f)-1
		for k in range(n//4):
			if(f[i]*f[j] != ar):
				ans = "NO"
				break
			else:
				i += 1
				j -= 1
	else:
		ans = "NO"
	print(ans)


q = int(input())
for qq in range(q):
    n = int(input())
    *a, = list(map(int, input().split()))
    a = list(sorted(a))
    br = False
    for i in range(2*n):
        if a[2*i] != a[2*i+1]:
            print("NO")
            br = True
            break
    if br:
        continue
    a = a[::2]
    ar = a[0]*a[-1]
    for i in range(n):
        if a[i]*a[-i-1] != ar:
            print("NO")
            break
    else:
        print("YES")


import io, os
#input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline

q = int(input())

for i in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	mn, mx = 10 ** 18, 0
	for c in a:
		if c < mn:
			mn = c
		if c > mx:
			mx = c
		d[c] = d.get(c, 0) + 1
	
	s = mn * mx
	f = True
	for c in d:
		if not(d[c] % 2 == 0 and s % c == 0 and d.get(s // c, 0) == d[c]):
			f = False
			print("NO")
			break
	if f:
		print("YES")
	


q = int(input())
for Q in range(q):
    n = int(input())
    arr = list(map(int, input().split()))
    arr2 = []
    unused = set()
    for i in arr:
        if i not in unused:
            unused.add(i)
        else:
            arr2.append(i)
            unused.remove(i)

    if len(unused) != 0:
        print("NO")
    else:
        flag = True
        arr2.sort()
        s = arr2[0] * arr2[-1]
        arr2 = arr2[1:-1]
        while len(arr2) != 0:
            s2 = arr2[0] * arr2[-1]
            if s2 != s:
                print("NO")
                flag = False
                break
            else:
                arr2 = arr2[1:-1]
        if flag:
            print("YES")


N = int(input())
for i in range(N):
    A = int(input())
    B = list(map(int,input().split()))
    B.sort()
    flag = True
    for i in range(2*A):
        if B[2*i] != B[2*i+1]:
            flag = False
            break
    S = B[0]*B[-1]
    for i in range(A):
        if B[i*2] * B[-i*2-1] != S:
            flag = False
            break
    print(["NO","YES"][flag])


q = int(input())
for j in range(q):
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)
    if n == 1:
        if a[0] == a[1] and a[2] == a[3]:
            print('YES')
        else:
            print('NO')
    else:
        b = []
        for i in range(0, 4 * n - 1, 2):
            if a[i] == a[i + 1]:
                b.append(a[i])
        #print(b)
        if len(b) == 2 * n:
            x = b[0] * b[2 * n - 1]
            for i in range(1, n):
                #print(x)
                if b[i] * b[2 * n - i - 1]== x:
                    x = b[i] * b[2 * n - i - 1]
                else:
                    x = 0
                    break
            if x != 0:
                print('YES')
            else:
                print('NO')
        else:
            print('NO')
            


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    t=[]
    k=0
    for i in range(0,2*n,2):
        if a[i]==a[i+1] and a[4*n-i-1]==a[4*n-i-2]:
            s=a[i]*a[4*n-i-1]
            t.append(s)
            

        else:
            k+=1
    if k>0:
        print('NO')
    else:
        if len(list(set(t)))==1:
            print('YES')
        else:
            print('NO')


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    hsh=[0]*max(a)
    for i in a:
        hsh[i-1]+=1
    flag=0
    for i in hsh:
        flag+=i%2
        if(flag):
            break
    if(flag):
        print("NO")
    else:
        a.sort()
        s=a[0]*a[-1]
        for i in range(2*n):
            if(a[i]*a[4*n-1-i]!=s):
                flag=1
                break
        if(flag):
            print("NO")
        else:
            print("YES")



q=int(input())
while q:
    n=int(input())
    a=input().split()
    for i in range(4*n):
        a[i]=int(a[i])
    a.sort()
    count=0
    value=a[0]*a[4*n-1]
    j=0
    while j<=2*n-2:
        if(a[j]==a[j+1] and a[4*n-j-1]==a[4*n-j-2]):
            if(a[j]*a[4*n-j-1]==value):
                count+=1
        j+=2      
    if(count==n) : print("YES")
    else: print("NO")
    q-=1    

q = int(input())
for i in range(q):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = True
    S = -1
    i = 0
    for j in range(n):
        if a[i] == a[i + 1] and a[-(1 + i)] == a[-(2 + i)]:
            if S == -1 or S == a[i] * a[-(1 + i)]:
                S = a[i] * a[-(1 + i)]
            else:
                ans = False
                break
        else:
            ans = False
            break
        i += 2
    if ans:
        print("YES")
    else:
        print("NO")