#P1988B. Make Majority

Make Majority

Description

You are given a sequence [a1,,an][a_1,\ldots,a_n] where each element aia_i is either 00 or 11. You can apply several (possibly zero) operations to the sequence. In each operation, you select two integers 1lra1\le l\le r\le |a| (where a|a| is the current length of aa) and replace [al,,ar][a_l,\ldots,a_r] with a single element xx, where xx is the majority of [al,,ar][a_l,\ldots,a_r].

Here, the majority of a sequence consisting of 00 and 11 is defined as follows: suppose there are c0c_0 zeros and c1c_1 ones in the sequence, respectively.

  • If c0c1c_0\ge c_1, the majority is 00.
  • If c0<c1c_0<c_1, the majority is 11.

For example, suppose a=[1,0,0,0,1,1]a=[1,0,0,0,1,1]. If we select l=1,r=2l=1,r=2, the resulting sequence will be [0,0,0,1,1][0,0,0,1,1]. If we select l=4,r=6l=4,r=6, the resulting sequence will be [1,0,0,1][1,0,0,1].

Determine if you can make a=[1]a=[1] with a finite number of operations.

Each test contains multiple test cases. The first line contains the number of test cases tt (1t41041 \le t \le 4\cdot 10^4). Description of the test cases follows.

The first line of each testcase contains one integer nn (1n21051\le n\le 2\cdot 10^5).

The second line of each testcase contains a string consisting of 00 and 11, describing the sequence aa.

It's guaranteed that the sum of nn over all testcases does not exceed 21052\cdot 10^5.

For each testcase, if it's possible to make a=[1]a=[1], print YES. Otherwise, print NO. You can output the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will be recognized as positive responses.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1t41041 \le t \le 4\cdot 10^4). Description of the test cases follows.

The first line of each testcase contains one integer nn (1n21051\le n\le 2\cdot 10^5).

The second line of each testcase contains a string consisting of 00 and 11, describing the sequence aa.

It's guaranteed that the sum of nn over all testcases does not exceed 21052\cdot 10^5.

Output

For each testcase, if it's possible to make a=[1]a=[1], print YES. Otherwise, print NO. You can output the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will be recognized as positive responses.

Sample Input 1

5
1
0
1
1
2
01
9
100000001
9
000011000

Sample Output 1

No
Yes
No
Yes
No

Note

In the fourth testcase of the example, initially a=[1,0,0,0,0,0,0,0,1]a=[1,0,0,0,0,0,0,0,1]. A valid sequence of operations is:

  1. Select l=2,r=8l=2,r=8 and apply the operation. aa becomes [1,0,1][1,0,1].
  2. Select l=1,r=3l=1,r=3 and apply the operation. aa becomes [1][1].