Problem description

Jasio, przygotowując się na przyjęcie gości, postanowił udekorować swój dom. Przeglądając internet, natrafił na fraktal o ciekawym wyglądzie – dywan Sierpińskiego. Wpadł na pomysł, aby wydrukować go na plakatach i przykleić do ścian. Niestety, jego stara drukarka obsługuje wyłącznie standardowe znaki ASCII.

Pomóż Jasiowi i napisz program, który wczyta stopień fraktalu i wydrukuje go przy użyciu jedynie znaków spacji oraz #.

Dywan stopnia 0 (D₀) to pojedynczy znak #.

Dywan stopnia k + 1 (D_k + 1) otrzymujemy, układając osiem kopii dywanu stopnia D_k w układzie 3×3, pozostawiając środkowy fragment pusty.

Graficzna ilustracja tego procesu:

Puste miejsca w trakcie konstrukcji kolejnych stopni fraktalu należy wypełnić spacjami (patrz przykłady).

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się pojedyczna liczba całkowita n, oznaczająca poziom fraktalu, jaki należy wypisać.

Wyjście

Na wyjściu powinien znaleźć się dywan sierpińskiego według powyżej opisanych reguł i konwencji.

Ograniczenia

0 ≤ n ≤ 7.

Przykład

0

#

1

###
# #
###

2

#########
# ## ## #
#########
###   ###
# #   # #
###   ###
#########
# ## ## #
#########