Wstęp do programowania w C++

Mrówka Langtona

Mrówka Langtona to automat wymyślony i opisany przez Chrisa Langtona, stąd jej nazwa. Mrówka porusza się według pewnych zasad po siatce pól, zamieniając ich kolory na przeciwne. Początkowo nadajemy mrówce jeden z czterech kierunków i ustawiamy ją na pewnym polu siatki, dalej mrówka radzi sobie już sama. Jeśli pole, na którym się znajduje jest koloru białego, mrówka obraca się o 90 stopni w kierunku przeciwnym do ruchu wskazówek zegara, zamienia kolor pola na czarny i przechodzi na sąsiednie pole. Jeśli pole, na którym się znajduje jest koloru czarnego, mrówka obraca się o 90 stopni w kierunku zgodnym z ruchem wskazówek zegara, zamienia kolor pola na biały i przechodzi na sąsiednie pole. Poniżej symulacja kilku początkowych ruchów mrówki Langtona.

W tym zadaniu mrówkę osadzimy w diagramie 6 × 6, którego początkowo wszystkie pola są koloru białego. Swoją przygodę mrówka rozpoczyna w polu (3,3) obrócona w kierunku północnym. To jest jej pierwszy ruch, w którym obraca się na zachód, pole zabarwia na kolor czarny i idzie przed siebie. Mrówka porusza się według zasad podanych wyżej, z drobną różnicą. Ponieważ znajduje się w diagramie ograniczonym, za każdym razem, gdy próbuje wyjść poza jego granice, przechodzi cyklicznie na pole z drugiej strony diagramu. Na przykład z pola (2,6) chcąc iść na wschód przechodzi na pole (2,1), a z pola (1,3) idąc na północ, mrówka przechodzi na pole (6,3). I tak sobie mrówka przechadza po diagramie zmieniając stany pól z każdym kolejnym ruchem. Twoim zadaniem jest odtworzyć aktualny stan diagramu po n ruchach mrówki. Dla potrzeb zadania przyjmujemy, że każde pole koloru białego oznaczamy znakiem kropki (.), a pola koloru czarnego - znakiem x.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 10⁵). Każdy przypadek to jedna liczba całkowita n (1 ≤ n ≤ 10⁹) oznaczająca liczbę ruchów mrówki.

Wyjście
Dla każdego przypadku testowego należy wydrukować diagram 6 × 6 z aktualnym stanem pól po n ruchach mrówki Langtona. Między przypadkami testowymi dozwolony jest dodatkowy znak końca linii.

Przykład

Wejście
3
3
14
100

Wyjście

......
......
.xx...
.x....
......
......

......
..xx..
.xxxx.
.xxxx.
......
......

.xx.xx
xx..xx
xx.xx.
...x.x
..x..x
.x..x.