Description
Agak Ribet means a little bit complicated in Indonesian. This problem can be solved with recursion, similar to Sierpinski.
RH, a green sock, loves programming and overcomplicating things.
After finishing Sierpinski's Carpet, he think that it was way too simple, So he designed a cooler looking carpet and named it Karpet Agak Ribet.
The square in the center should be of length 8 units.
The construction is decribed as follow.
For a Carpet that has depth 1, consists of 1x1 square colored black.
For depth 2, it has side length 4, its 4 corners are made up of depth 1 Carpet with a 2x2 center square.
For depth 3, it has side length 10, its 4 corners are made up of depth 2 Carpet with a 4x4 center square.
For carpet with depth of n, its 4 corners are made up of depth (n-1) carpet, without the opposite diagonal of each corner and a 2n-1 center square.
For a clear picture, the following figures are the carpet with Depth 1, 2, and 3.
The following figure is the carpet with depth 5.
The square in the center should be of length 16 units.
Input
Input contains only one line with single integer n (1 <= n < 12).
Output
Output the carpet with depth n and use ' ' (space) to represent white, '*' to represent black.
Remember to add a newline character at the end of line.