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

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