종이 접기

동호는 종이를 옆에서 보며 접는다. 종이를 한 번 접을 때에는 항상 오른쪽 절반을 왼쪽 절반 위로 가져오며, 다음 두 방법 중 하나만 사용할 수 있다.

1. 오른쪽 절반을 반시계 방향으로 돌려 왼쪽 절반의 위쪽에 겹친다.
2. 오른쪽 절반을 시계 방향으로 돌려 왼쪽 절반의 아래쪽에 겹친다.

한 번 접을 때마다 종이의 길이는 절반이 되고 두께는 두 배가 된다. 동호는 이 과정을 원하는 만큼 반복할 수 있다. 접었던 종이를 모두 펼치면 접힌 자국들이 왼쪽부터 오른쪽까지 남는다.

접힌 자국이 시계 방향으로 꺾여 있으면 OUT, 반시계 방향으로 꺾여 있으면 IN이라고 한다. 입력에서는 OUT을 1, IN을 0으로 나타낸다.

어떤 사람이 접었다가 펼친 종이의 접힌 자국 정보가 주어진다. 이 정보가 동호의 규칙으로 접어서 만들 수 있는 형태인지 판별하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000 이하의 자연수이다.

다음 T개의 줄에는 각 종이의 접힌 자국 정보가 문자열로 주어진다. 문자열은 0과 1로만 이루어져 있고, 길이는 3000보다 작으며 항상 2^N - 1 꼴이다. 여기서 N >= 1이다.

각 테스트 케이스마다 주어진 접힌 자국 정보를 동호의 규칙으로 만들 수 있으면 YES, 만들 수 없으면 NO를 한 줄에 하나씩 출력한다.