Paper Folding

Dongho folds a strip of paper while looking at it from the side. Each time he folds, he always moves the right half onto the left half, using exactly one of these two methods.

1. Rotate the right half counterclockwise so it lies above the left half.
2. Rotate the right half clockwise so it lies below the left half.

After each fold, the paper becomes half as long and twice as thick. Dongho may repeat this process as many times as he wants. When the paper is unfolded completely, crease directions remain from left to right.

A crease bent clockwise is called OUT, and a crease bent counterclockwise is called IN. In the input, OUT is written as 1, and IN is written as 0.

Given the crease information of a paper after it was folded and unfolded, determine whether that information could have been produced by Dongho's folding rule.

The first line contains the number of test cases T. T is a positive integer not greater than 1000.

Each of the next T lines contains one crease-information string. The string consists only of 0 and 1, its length is less than 3000, and its length is always of the form 2^N - 1, where N >= 1.

For each test case, print YES if the given crease information can be produced by Dongho's rule, and print NO otherwise.