Sweetie Drops, or Bon Bon, is a female Earth pony with a cutie mark of three candies. Lyra Heartstrings, is a female unicorn pony with a cutie mark of a lyre.
They always appear together in TV show as background characters. In The Last Problem, Lyra is shown in newspaper as having gotten married to Sweetie Drops.
The fans use LyraBon as the femslash ship between Lyra Heartstrings and Sweetie Drops.
Today they are playing a black-white game, the game progresses turn by turn, Bon Bon moves first.
Initially, there are $$$n+1$$$ points connected by either white or black edge in a row. In one move a pony must choose at least two points and then do some removal.
More specific, Bon Bon can choose some consecutive points without black edge between any two of them, and then remove these points and all edge(s) connected to them. Be attention that black edge may be removed in the process.
Similarly, Lyra can choose consecutive points without white edge and then do removal in same way.
It is required that after either Bon Bon or Lyra's removal, the points must not be split into two separate blocks.
The pony who cannot make a move loses. If both ponys play optimally, could Bon Bon ultimately win the game?
The first line contains an integer $$$T$$$ $$$(1\le T \le 10^6)$$$, representing the number of test cases.
Each test case contains a binary string of length $$$n$$$ $$$(1\le \sum n\le 2\times 10^6)$$$, representing the colors of the edges, 0 represents a white edge, and 1 represents a black edge.
For each test case, output one line. If Bon Bon wins, output "YES", otherwise output "NO" (without the quotes).
3 0110 0001010 1001100
NO YES YES
In the first test case, Bon Bon could first choose the leftmost two points, then remove them, the edge between them and the edge marked with a purple cross in the figure below. In Lyra's turn, she could remove similarly and leave only one point(the rightmost one). Thus Bon Bon could not move and lose.
In the second test case, Bon Bon has four choices in the first move. Note that the edge connect to the chosen points will be removed, too.
