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