Hexagram

Time limit5sMemory limit128 MB

Summary

Count how many ways, up to rotation and reflection, the 12 given distinct numbers can be placed on the 12 vertices of a hexagram so all 6 lines share one sum.

Level: Hard8 of 10
Topics: Brute force, Backtracking, Combinatorics, Implementation
Solved: No attempts yet

Problem

A hexagram is a six-pointed star, also called the Star of David. It is drawn as two overlapping equilateral triangles and has $12$ vertices: $6$ outer points (the tips of the star) and $6$ inner points (where the edges of the two triangles cross). It also has $6$ straight lines. Each line is one full side of a triangle: it starts at an outer point, passes through two inner points, and ends at another outer point, so every line passes through exactly $4$ vertices. Every vertex lies on exactly $2$ of the $6$ lines.

Given $12$ distinct numbers, in how many ways, disregarding rotations and reflections, can you assign the numbers to the $12$ vertices so that the four numbers along each of the $6$ lines have the same sum? Two assignments that can be turned into each other by a rotation or a reflection of the star are counted as the same.

Input

There are several test cases. Each test case is a single line containing twelve distinct positive integers separated by single spaces; every number is less than $1{,}000{,}000$ . The input ends with a line of twelve zeros, which is not processed.

Output

For each test case, print on its own line the number of ways the numbers can be assigned to the vertices so that the sum along each of the $6$ lines is the same. Print no extra spaces, and do not separate the answers with blank lines.

Examples1

Example 1

Input

3 17 15 18 11 22 12 23 21 7 9 13
1 2 3 4 5 6 7 8 9 10 11 13
0 0 0 0 0 0 0 0 0 0 0 0

Expected output

4
0