Roses and pots (1) P88410

You have roses of three different colors. In particular, you have n roses of each color. Please print all the ways to plant all the roses in a line of 3n pots, one rose per pot, in such a way that there is exactly one pair of adjacent roses of the same color. The roses of the same color are indistinguishable.

Input

Input consists of several cases, each with n. Assume 1 ≤ n ≤ 6.

Output

For every case, print all the solutions in lexicographical order. Use numbers starting at one to identify each color. Print a line with 10 asterisks after every case.