Valid Binary String

Interview

Time limit1sMemory limit128 MB

Summary

Given a binary string with erased positions, decide whether the missing bits can be filled so the counts of 0 and 1 are equal and no character runs three times in a row.

Level: Medium6 of 10
Topics: Greedy, String, Implementation, Two pointers
Solved: No attempts yet

Problem

A string made up only of the characters 0 and 1 is called a binary string. A binary string is called a valid binary string if it satisfies both of the following conditions:

Balanced: the number of 0s equals the number of 1s.
Run limit: the same character never appears three or more times in a row; that is, every maximal run of consecutive 0s or consecutive 1s has length at most 2.

You are given a binary string in which some characters have been erased. Write a program that decides whether the erased positions can each be filled with a 0 or a 1 so that the whole string becomes a valid binary string.

Input

The first line contains the number of test cases $T$ ( $T \le 100$ ).

Each test case is given on its own line as a string made up of the characters 0, 1, and ., where . marks an erased position. The length of the string is an even number between 2 and 100,000, inclusive.

Output

For each test case, print yes if the given string can be turned into a valid binary string, and no otherwise, each on its own line.

Examples2

Example 1

Input

6
001100110011
110..0...00...0011
..............
01....100100
010101110100
101011011001

Expected output

yes
yes
yes
no
no
no

Example 2
Input
```
5
01
10
00
11
..
```
Expected output
```
yes
yes
no
no
yes
```