for(i=n=[,8,32,128][readline()];i--;print(o))for(o=j='';j1;v=v&&1526906730-444161385*v>>2*(p/g<<2|q/g)&3)p%=g,q%=g,g/=4