LONER - The Loner

The loner is a one-dimensional board game for a single player. The board is composed of squares arranged in a single line, some of which initially have pawns on them. The player makes a move by jumping with a pawn over a pawn on an adjacent field, to an empty square two fields to the right or left of its initial position. The pawn that was jumped over is removed directly after the move, as illustrated below.

The two acceptable types of moves

The game is considered won if exactly one pawn remains on the gaming board, and is lost if the player cannot make a move.

Given the initial state of the gaming board, your task is to determine whether it is possible for the player to win the game.

Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

Each test cases begins with the positive integer n <= 32000, denoting the size of the gaming board. The second and last line of the test case description contains a sequence of n characters 0 or 1, without any white spaces. The i-th square of the board is occupied by a pawn at the start of the game iff the i-th character of this sequence is 1.

Output

For each test case output the word yes if it is possible for the player to win the game for the presented starting configuration, or the word no in the opposite case.

Example

Sample input:
2
7
0110011
6
111001

Sample output:
yes
no

Added by:adrian
Date:2004-07-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:VI Polish Collegiate Team Programming Contest (AMPPZ), 2001

hide comments
2019-02-28 16:31:03
Enjoyed figuring out the logic, but absolutely hated implementing the solution. What seemed like possibly an oneliner in Bash or Perl, ended up as almost 2KB turd of a program. Feeling like an idiot :/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.