K. Hobz is a good guy
time limit per test
1 second
memory limit per test
256 megabytes
input
hobz.in
output
standard output

"I swear to god if what I am thinking is true. I will $$$010101010100011$$$ And $$$01010100001111$$$" said Modda.

Modda can rap in binary. As we all know to rap in binary the string must be non-empty and have the number of ones in even positions equal to the number of ones in odd positions.

Now Modda asks you if you can remove some number of characters from the given binary string $$$S$$$ so that you can use it in rap.

If I were you, I'd answer his question quickly. You don't want to know what happened to Hobz.

Input

The first line contains one integer $$$T$$$ $$$(1 \leq T \leq 10^{5})$$$ — the number of test cases.

The only line of each testcase contains a binary string.

The total length of the sequences over all testcases doesn't exceed $$$2$$$ $$$*$$$ $$$10^5$$$

Output

For each test case, print "Yes" if you can remove some number of characters from the given binary string $$$S$$$ so that you can use it in rap. Otherwise, print "No".

Example
Input
3
0
1
01
Output
YES
NO
YES