You are given two arrays \(a = [a_1, a_2, ..., a_n]\) and \(b = [b_1, b_2, ..., b_n]\), with \(a_1 = a_2 = ... = a_n = 0\).

First, you must choose two of indices \(i, j\) (\(1 \leq i, j \leq n, i \neq j\)) and assign \(a_i = a_j = 1\).

Then perform the following operation as many times as you want:

• Choose an index \(k (1 \leq k \leq n)\), and add the product of the two largest integers in \(a\) to \(a_k\). That is, \(a_k = a_k + a_i \cdot a_j\), where \(a_i \geq a_j \geq a_l\) for all \(l (1 \leq l \leq n, l \neq i, l \neq j)\).

Now, determine if you can transform the array \(a\) into the array \(b\) or not.

If you can construct the array, then print “YES”. Otherwise, print “NO”.

Constraints

• \(1 \leq T \leq 1000\)
• \(2 \leq n \leq 10^5\)
• \(0 \leq b_i \leq 10^9\)

Input Format

• The first line contains a single integer \(T\) —- the number of test cases.
• For each testcase:
  • The first line contains one integer \(n\) —- the length of the arrays.
  • The second line contains \(n\) nonnegative integers \(b_1, b_2, ... , b_n\).
• The sum of \(n\) over all test cases does not exceed \(10^6\).

Output Format

• For each Testcase, output "YES" if the array \(a\) can be transformed into \(b\). Otherwise, output "NO".