시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

다음과 같은 두 가지 조건을 만족하는 바이너리 문자열 (0과 1로만 이루어짐)을 올바른 바이너리 문자열 이라고 한다.

  1. DC-균형: 0과 1의 개수가 같다
  2. RL-제한: 연속된 0또는 1의 개수가 2개를 넘지 않는다

일부 글자가 지워진 바이너리 문자열이 주어졌을 때, 지워진 글자를 0 또는 1로 바꿔서 올바른 바이너리 문자열로 바꿀 수 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T (T ≤ 100)가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, '0', '1', '.'으로 이루어진 바이너리 문자열이 주어진다. '.'는 지워진 글자를 의미하고, 길이는 2보다 크거나 같고, 100,000보다 작거나 같은 짝수이다.

출력

각각의 테스트 케이스마다 입력으로 주어진 바이너리 문자열을 올바른 바이너리 문자열로 바꿀 수 있으면 "yes"를 없으면 "no"를 출력한다.

예제 입력

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

예제 출력

yes
yes
yes
no
no
no

힌트