문제
하노이 문제는 기둥을 1, 2, 3 번으로 하고, N개의 원판이 작은 것부터 1, 2, 3, 4 … N이라고 할 때,
아래의 규칙에 따라 1번 기둥에 있는 모든 원판을 3번 기둥으로 이동하는 문제이다.
규칙1) 한 번에 하나의 원판만 이동시킨다.
규칙2) 작은 원판위에 큰 원판을 놓을 수 없다.
위 규칙대로 하노이 탑 완구를 가지고 문제를 풀던 수민이는 너무 지겨워서 새 규칙을 만들었다.
규칙3) 원판은 항상 인접한 오른쪽 기둥으로만 이동 가능하다.
만약 오른쪽 기둥이 없을 경우 가장 왼쪽 기둥으로 이동한다. 1->2, 2->3, 3->1
수민이는 당신에게 하노이 탑의 상태를 보여주며 이 상태가 올바른 상태인지 물어보았다.
올바른 상태란, 위 규칙대로 최소 이동 횟수로 하노이 탑 문제를 해결하는 과정에서 나오는 상태를 말한다.
예를 들어, 원판이 3개가 있을 때, 아래 그림은 올바르지 않은 상태다.
현재 원판들의 위치 상태가 주어졌을 때 수민이의 하노이 탑이 올바른 상태인지 알려주자.
입력
100 이하의 자연수인 테스트 케이스의 수 T가 첫번째 줄에 주어진다.
그 다음, T줄마다 원판들이 위치한 기둥 번호가 주어진다.
원판들의 기둥 번호 S는 작은 원판에서 큰 원판 순서대로 주어지며, 공백없이 1,2,3 숫자로 주어진다.
주어지는 하노이 탑 완구의 원판 수는 1개 이상 1,000,000개 이하이다. 즉, S의 길이는 1 이상 1,000,000 이하다.
출력
각 테스트 케이스마다 한 줄로 올바른 상태의 여부를 출력한다.
올바른 상태일 경우 YES, 그렇지 않을 경우 NO를 출력한다.
예제
3
223
123
2211
NO
YES
NO
로그인해야 코드를 작성할 수 있어요.