테이블

어느 대학 공학부의 구내식당에는 탁자가 아주 많습니다. 이 탁자들은 정사각형이나 직사각형이 아니라, 아래 그림처럼 변의 길이가 1, 1, 1, 2인 이등변사다리꼴 모양입니다. 정육각형을 절반으로 나눈 것으로 볼 수도 있고, 정삼각형 세 개를 나란히 붙인 것으로 볼 수도 있습니다. 탁자 하나에는 다섯 명 정도가 앉을 수 있지만, 예각인 두 모서리 쪽은 접시를 놓을 자리가 거의 없습니다.

인원이 많을 때에는 여러 탁자를 이어 붙여 하나의 큰 모양을 만듭니다. 사용하는 탁자가 많아질수록 만들 수 있는 모양도 다양해집니다. 반대로, 주어진 모양을 이 사다리꼴 탁자들로 만들 수 있는지, 만들 수 있다면 서로 다른 방법이 몇 가지인지 물을 수도 있습니다. 예를 들어 정육각형은 탁자 두 개로 서로 다르게 세 가지 방법으로 만들 수 있습니다.

이 세 가지는 회전하면 같은 것으로 볼 수도 있지만, 이 문제에서는 서로 다른 방법으로 셉니다.

모양은 삼각 격자 위에서 표현합니다. 격자의 각 꼭짓점(노드)에는 세 자리 코드가 붙어 있는데, 각 자리는 0부터 8까지의 숫자이고 세 숫자의 합은 항상 8입니다. 모양은 그 외곽선(윤곽)을 이루는 노드들을 순서대로 나열하여 나타냅니다. 예: 116, 314, 134, 125, 026. 외곽선은 이웃한 노드를 격자선을 따라 이어서 그립니다. 즉 첫 번째 노드와 두 번째 노드를, 두 번째와 세 번째를, 이런 식으로 차례로 잇고, 마지막 노드는 다시 첫 번째 노드와 잇습니다. 모든 선분이 격자선을 따라가므로, 나열된 이웃한 노드는 항상 같은 격자선 위에 놓입니다.

외곽선은 항상 다음 규칙을 만족합니다.

1. 주어진 순서대로 외곽선을 따라 걸을 때, 둘러싸인 영역은 항상 왼쪽에 있습니다.
2. 외곽선은 스스로 교차하지 않으며, 같은 노드가 두 번 이상 쓰이지 않습니다.
3. 둘러싸인 영역에는 구멍이 없습니다(사실 이는 규칙 1과 2에서 저절로 따라옵니다).

모양의 외곽선이 주어질 때, 그 모양을 사다리꼴 탁자들로 만들 수 있는 서로 다른 방법의 수를 구하세요.

첫째 줄에는 테스트 케이스의 수를 나타내는 정수 하나가 주어집니다. 각 테스트 케이스의 형식은 다음과 같습니다.

• 첫째 줄에는 외곽선을 이루는 노드의 개수 $n$이 정수 하나로 주어집니다.
• 둘째 줄에는 외곽선을 이루는 $n$개의 노드 코드가 순서대로 공백 하나로 구분되어 주어집니다.

각 테스트 케이스마다, 주어진 모양을 사다리꼴 탁자들로 만들 수 있는 서로 다른 방법의 수를 한 줄에 정수 하나로 출력합니다.