#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long u64;
int N,F; long long fact[10]={1,1,2,6,24,120,720,5040,40320,362880};
u64 *cnt; int rows[9];
void leaf(void){
  long long w=fact[N-1]; int run=1;
  for(int i=1;i<N-1;i++){ if(rows[i]==rows[i-1]) run++; else {w/=fact[run]; run=1;} } w/=fact[run];
  static long long f[1<<9]; for(int m=0;m<F;m++)f[m]=0; f[0]=1;
  for(int m=0;m<F;m++){ if(!f[m])continue; int k=__builtin_popcount(m); if(k>=N-1)continue;
    int r=rows[k]; for(int j=0;j<N;j++) if((r>>j&1)&&!(m>>j&1)) f[m|1<<j]+=f[m]; }
  long long c[9]; for(int j=0;j<N;j++) c[j]=f[(F-1)&~(1<<j)];
  for(int x=0;x<F;x++){ long long p=0; for(int j=0;j<N;j++) if(x>>j&1)p+=c[j]; cnt[p]+=w; }
}
void go(int d,int s){ if(d==N-1){leaf();return;} for(int r=s;r<F;r++){rows[d]=r;go(d+1,r);} }
static int dummy; int main(int a,char**v){N=atoi(v[1]);F=1<<N;cnt=calloc(fact[N]+1,8);go(0,0);
 u64 tot=0; for(long long k=0;k<=fact[N];k++){ tot+=cnt[k]; if(cnt[k]) printf("%lld %llu\n",k,cnt[k]); }
 fprintf(stderr,"total %llu\n",tot); }