Make Length 1 Codechef Solution

Problem

You are given a binary string $S$ of length $N$.

You can perform the following operation on $S$:

• Select an index $i(1\le i<|S|)$ such that S_i=S_{i+1}Si​=Si+1​.
• Set S_iSi​ to $0$ and remove S_{i+1}Si+1​ from the string.

Note that after each operation, the length of $S$ decreases by $1$.

Is it possible to reduce $S$ to a single character by performing the mentioned operation exactly $N-1$ times?

Input Format

• The first line of input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• Each test case consists of two lines of input.
  • The first line of each test case contains a single integer $N$, the length of $S$.
  • The second line contains a binary string $S$ of length $N$.

Output Format

For each test case, print the answer on a new line: YES if it is possible to perform the operation $N-1$ times, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase, i.e, YES, yes, yEs and yES will all be treated as identical.

Constraints

Sample 1:

4
2
11
2
10
4
1100
3
101

YES
NO
YES
NO

Explanation:

Test case $1$: Perform the operation choosing $i=1$. This sets S_1 = 0S1​=0 and deletes S_2S2​ from the string, after which $S$ is now a single character.

Test case $2$: It is not possible to perform any operation.

Test case $3$: One sequence of operations is as follows:

• Perform the operation on $i=3$. Now, $S=110$.
• Perform the operation on $i=1$. Now, $S=00$.
• Perform the operation on $i=1$. Now, $S=0$ and we are done.

Test case $4$: It is not possible to perform any operation.