#P1624C. Division by Two and Permutation

    ID: 6250 Type: RemoteJudge 3000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>constructive algorithmsflowsgraph matchingsgreedymath*1100

Division by Two and Permutation

No submission language available for this problem.

Description

You are given an array aa consisting of nn positive integers. You can perform operations on it.

In one operation you can replace any element of the array aia_i with ai2\lfloor \frac{a_i}{2} \rfloor, that is, by an integer part of dividing aia_i by 22 (rounding down).

See if you can apply the operation some number of times (possible 00) to make the array aa become a permutation of numbers from 11 to nn —that is, so that it contains all numbers from 11 to nn, each exactly once.

For example, if a=[1,8,25,2]a = [1, 8, 25, 2], n=4n = 4, then the answer is yes. You could do the following:

  1. Replace 88 with 82=4\lfloor \frac{8}{2} \rfloor = 4, then a=[1,4,25,2]a = [1, 4, 25, 2].
  2. Replace 2525 with 252=12\lfloor \frac{25}{2} \rfloor = 12, then a=[1,4,12,2]a = [1, 4, 12, 2].
  3. Replace 1212 with 122=6\lfloor \frac{12}{2} \rfloor = 6, then a=[1,4,6,2]a = [1, 4, 6, 2].
  4. Replace 66 with 62=3\lfloor \frac{6}{2} \rfloor = 3, then a=[1,4,3,2]a = [1, 4, 3, 2].

The first line of input data contains an integer tt (1t1041 \le t \le 10^4) —the number of test cases.

Each test case contains exactly two lines. The first one contains an integer nn (1n501 \le n \le 50), the second one contains integers a1,a2,,ana_1, a_2, \dots, a_n (1ai1091 \le a_i \le 10^9).

For each test case, output on a separate line:

  • YES if you can make the array aa become a permutation of numbers from 11 to nn,
  • NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

Input

The first line of input data contains an integer tt (1t1041 \le t \le 10^4) —the number of test cases.

Each test case contains exactly two lines. The first one contains an integer nn (1n501 \le n \le 50), the second one contains integers a1,a2,,ana_1, a_2, \dots, a_n (1ai1091 \le a_i \le 10^9).

Output

For each test case, output on a separate line:

  • YES if you can make the array aa become a permutation of numbers from 11 to nn,
  • NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

Samples

Sample Input 1

6
4
1 8 25 2
2
1 1
9
9 8 3 4 2 7 1 5 6
3
8 2 1
4
24 7 16 7
5
22 6 22 4 22

Sample Output 1

YES
NO
YES
NO
NO
YES

Note

The first test case is explained in the text of the problem statement.

In the second test case, it is not possible to get a permutation.