#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

#define all(c)    (c).begin(),  (c).end()
#define rall(c)  (c).rbegin(), (c).rend()

#define _auto(var, x)           typeof(x) var = (x)
#define _auxforeach(it, b, e)   for(_auto(it, b), _itend = e; it != _itend; ++it)
#define foreach(it, r...)       _auxforeach(it, r)

typedef long long LLONG;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef vector<VB> VVB;

enum { INF = 1<<30 };

struct EulerianCycle {  // (Closed Tour)

    // (OutDegree - InDegree) must be 0 for all vertices.

    VVI mtx;      // input (manipulated)
    const int V;  // input
    VI nextAdj;   // private

    VVI answer;   // output (list of stacks to be popped)

    /// mtx = binary adjacency matrix (directed graph)
    EulerianCycle(const VVI& mtx) : mtx(mtx),
             V(mtx.size()), nextAdj(V,0), answer(V) {  // O(Vē)
        foreach(i, 0,V)
            adjustNext(i);
        int nd = 0;
        while(nd < V) {
            if(nextAdj[nd] < V)
                depthFirstSearch(nd);
            else nd ++;
        }
    }

    /// Stores nodes from cycle in "output".
    void visit(VI& output) {  // O(E)
        VVI stackOf = answer;
        int nd = 0;
        while(stackOf[nd].empty() and nd < V) nd++;
        if(nd == V) return;
        output.push_back(nd);
        while(!stackOf[nd].empty()) {
            int newNd = stackOf[nd].back();
            output.push_back(newNd);
            stackOf[nd].pop_back();
            nd = newNd;
        }
    }
    /// Stores nodes from cycle in "output". Starts at "firstNode".
    void visit(VI& output, int firstNode) {  // O(E)
        visit(output);
        if(output.empty()) return; // All nodes "neighborless"...
        output.pop_back();
        VI::iterator it = find(all(output), firstNode);
        if(it == output.end()) throw "Node has no neighbors!";
        rotate(output.begin(), it, output.end());
        output.push_back(output[0]);
    }

    void adjustNext(int nd) {  // O(V)
        int& next = nextAdj[nd];
        while(next < V and mtx[nd][next] == 0) next++;
    }

    void depthFirstSearch(int firstNd) {
        int nd = firstNd;
        bool first = true;
        while(nd != firstNd or first) {
            int adj = nextAdj[nd];
            if(adj == V) throw "No Eulerian Cycle!";
            answer[nd].push_back(adj);
            mtx[nd][adj] --;
            adjustNext(nd);
            nd = adj;
            first = false;
        }
    }
};

#define bit(n, i) ((n & (1<<i))>0?1:0)
#define upbit(n, i) (n |= (1<<i)) 

bool confere(int a, int b, int n){
     for(int i=0; i<n-2; i++){
          if(bit(b,n-1-i-1)!=bit(a,(-i+n-2-1))) return false;
     }
     return true;
}

int main(){
    int n;
    while(true){
        puts("Digite o tamanho ou zero pra sair:");
        scanf("%d", &n);
        system("cls");
        if(!n) break;
        puts("Tratando excessoes...\n");
        if(n==1){
            puts("O Drum e': 10\n");
            continue;
        }
        puts("Nao existe excessoes...\n");
        int v = (1<<(n-1)); //2 elevado a n-1
        printf("Montando digrafo com %d vertices(2^%d)...\n\n", v, n-1);
        VVI mat(v, VI(v, 0));
        VVI label(v, VI(v, -1));
        puts("Criando arestas(A->B) onde os dois ultimos bits de A\nsao iguais aos dois primeiros bits de B...\n");
        for(int i=0; i<v; i++){
            for(int j=0; j<v; j++){
                if(confere(i, j, n)){
                     mat[i][j]=1;
                     label[i][j]=bit(j, 0);
                }
            }
        }
        puts("Buscando Ciclo Euleriano no digrafo, Complexidade O(V^2)\n");
        EulerianCycle ec(mat);
        puts("Ciclo Euleriano ENCONTRADO! Gerando saida...\n");
        VI ciclo;
        ec.visit(ciclo);
        //DESCOMENTE PARA VISUALIZAR O CICLO
        //for(int i=0; i<ciclo.size(); ++i) printf("%d ",ciclo[i]);
        puts("Reconstruindo ciclo e buscando labels..\n");
        
        vector<int> drum;
        
        puts("O Drum e':");
        for(int i=0; i<ciclo.size()-1; ++i){
            printf("%d",label[ciclo[i]][ciclo[i+1]]);
            drum.push_back(label[ciclo[i]][ciclo[i+1]]);
        }
        puts("\n");
                
    }

}