Tables

Time limit1sMemory limit128 MB

Summary

Count the tilings of a polyiamond on a triangular grid by isosceles trapezoids made of three unit triangles, given the shape's boundary as a sequence of grid nodes.

Level: Hard9 of 10
Topics: Dynamic programming, Geometry, Combinatorics, Implementation
Solved: No attempts yet

Problem

The cafeteria of a university engineering faculty has a lot of tables. Instead of being square or rectangular, each table is an isosceles trapezoid with side lengths 1, 1, 1, and 2, like the one drawn below. You can view it as half of a regular hexagon, or as three equilateral triangles joined side by side. One table seats about five people, though the two acute corners leave little room for a plate.

One table

For larger groups, several tables are pushed together to form one big shape. The more tables you use, the more shapes become possible. Turning the question around: given a target shape, can it be assembled from these trapezoidal tables at all, and if so, in how many different ways? For instance, a regular hexagon can be assembled from two tables in three different ways.

Three ways to form a hexagon

One could argue that these three arrangements are really the same, differing only by a rotation. In this problem, however, they are counted as three different solutions.

The triangle encoding

Shapes are described on a triangular grid. Each node of the grid is labelled by a code of three digits, each digit in the range 0 to 8, whose sum is exactly 8. A shape is given by listing the nodes along its outline (contour), for example: 116, 314, 134, 125, 026. The outline is drawn by joining consecutive nodes along grid lines: the first node to the second, the second to the third, and so on, and finally the last node back to the first. Because every segment runs along a grid line, consecutive nodes always lie on a common grid line.

The outline always satisfies these rules:

As you walk along the outline in the given order, the enclosed region lies on your left-hand side.
The outline never crosses itself, and no node appears more than once.
The enclosed region has no holes (this actually follows from rules 1 and 2).

Given the outline of a shape, determine the number of different ways it can be assembled from the trapezoidal tables.

Input

The first line contains a single integer: the number of test cases that follow. Each test case has the following format:

The first line contains a single integer $n$ : the number of nodes on the outline.
The second line contains the $n$ node codes of the outline, in order, separated by single spaces.

Output

For each test case, print a single line containing one integer: the number of different ways to assemble the given shape from the trapezoidal tables.

Examples6

Example 1

Input

2
6
107 206 215 125 026 017
5
116 314 134 125 026

Expected output

3
0

Example 2
Input
```
1
4
611 701 800 620
```
Expected output
```
1
```
Example 3
Input
```
1
3
800 710 701
```
Expected output
```
0
```
Example 4
Input
```
1
3
530 503 800
```
Expected output
```
2
```
Example 5
Input
```
1
6
413 512 521 431 332 323
```
Expected output
```
3
```
Example 6
Input
```
1
3
404 800 440
```
Expected output
```
0
```