> #include <stdlib.h>
> #include <stdio.h>
> #include <string.h>
> #include <assert.h>
> typedef unsigned long long int U64;
> //using namespace std;
>     int next[800000];
>     int buf0[800000];
>     int res0[800000];
>     int res1[800000];
>     int buf1[800000];
> int lookback;
> int ii;
> int offset;
> int find_next(int max,int count,int buf_in[8000],int res_in[8000],int num_in,int buf_out[8000],int res_out[8000]){
>     int i,j;
>     int k=0;
>     int tmp;
>     int res;
>     int res1;
>     static int mult;
>     int div=max*2-count;
>     if (count==0) mult=1;
>     else mult*=2*max-count+1;
>     //printf("nult=%d\n",mult);
>     i=0;
>     //for(i=0;i<max*2-count;i++){
>         for(j=0;j<num_in;j++){
>             tmp=mult*i+buf_in[j];
>             res=res_in[j];
>             res1=(tmp-res)%(div);
>             if(res1){
>                 res1=div-res1;
>             }
>             if(res1<max-count){
>                 buf_out[k]=tmp;
>                 res_out[k]=res1;
>                 k++; 
>             }
>                   
>         }
>     //}
>     return k; 
> }
> int gen_next(int max,int count,int buf_in[8000],int res_in[8000],int num_in,int buf_out[8000],int res_out[8000]){
>     int i,j;
>     int k=0;
>     int tmp;
>     int res;
>     int res1;
>     static int mult;
> 
>     if (count==0) mult=1;
>     else mult*=2*max-count+1;
>     //printf("nult=%d\n",mult);
>     for(i=0;i<max*2-count;i++){
>         for(j=0;j<num_in;j++){
>             tmp=mult*i+buf_in[j];
>             res=res_in[j];
>             res1=(tmp-res)%(max*2-count);
>             if(res1){
>                 res1=max*2-count-res1;
>             }
>             if(res1<max-count){
>                 buf_out[k]=tmp;
>                 res_out[k]=res1;
>                 k++; 
>             }
>                   
>         }
>     }
>     return k; 
> }
> int gen_next(int max){
>     int i=max+1;
>     int j=0;
>     int last=0;
>     int tmp;
> 
>     return j; 
> }
> int find_next(int max){
>     if(max<5)ii++;
>     else {
>         ii++;
>     }
>     return ii;
> }
> int core(int max){
>     int i,j;
>     int res=max*2;
>     int tootle;
>     int tmp;
>     ii=max+1;
>     int sum=0;
>     int ans[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,13482720,25779600,68468401,610346880};
> 
>     int num_in;
>     int num_out;
>     num_in=1;
>     buf0[0]=0;
>     res0[0]=0;
>     int *buf_in;
>     int *buf_out;
>     int *buf_tmp;
>     int *res_in;
>     int *res_out;
>     int *res_tmp;
>     buf_in=buf0;
>     buf_out=buf1;
>     res_in=res0;
>     res_out=res1;
>     num_out=gen_next(max,0,buf_in,res_in,num_in,buf_out,res_out);
>     if(max==1){
>         if(num_out<2)   return max*2;
>         else return buf_out[1];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=gen_next(max,1,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d\n",num_out);
>     if(max==2){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=gen_next(max,2,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d\n",num_out);
>     if(max==3){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=gen_next(max,3,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d\n",num_out);
>     if(max==4){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=find_next(max,4,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
>     if(max==5){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=find_next(max,5,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
>     if(max==6){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=find_next(max,6,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
>     if(max==7){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=find_next(max,7,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
>     if(max==8){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=find_next(max,8,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
>     if(max==9){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=find_next(max,9,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
>     if(max==10){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=find_next(max,10,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
>     if(max==11){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=find_next(max,11,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
>     if(max==12){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>     buf_tmp=buf_in;
>     buf_in=buf_out;
>     buf_out=buf_tmp;
>     res_tmp=res_in;
>     res_in=res_out;
>     res_out=res_tmp;
>     num_in=num_out;
>     num_out=find_next(max,12,buf_in,res_in,num_in,buf_out,res_out);
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", buf_out[i]);
>     //}
>     //printf("\n");
>     //for(i=0;i<num_out;i++){
>     //    printf("%4d,", res_out[i]);
>     //}
>     //printf("\n");
>     //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
>     if(max==13){
>         for(i=1;i<num_out;i++)
>             if(res_out[i]==0)
>                 return buf_out[i];
>     }
>         return ans[max];
> }
> /*
>     int buf[15][800000];
>     int res[15][800000];
>     int num[15];
>     int last_num[15];
>     int r_num[15];
>     int mult_ram[15];
>     int offset_ram[15];
>     int count_ram[15];
>     int offset[15];
> int core1(int max){
>     int i,j;
>     int tmp;
>     unsigned int mult=1;
>     int nex;
>     int res0,res1;
>     for(j=0;j<15;j++){
>         num[j]=0;
>         last_num[j]=0;
>         r_num[j]=0;
>         mult_ram[j]=0;
>         offset_ram[j]=0;
>         count_ram[j]=0;
>         offset[j]=0;
> 
>     }
>     buf[0][0]=0;
>     res[0][0]=0;
>     num[0]=1;
>     last_num[0]=1;
>     mult_ram[0]=1;
>     offset_ram[0]=0;
>     count_ram[0]=0;
>     for(j=0;j<max;j++){
>         mult*=2*max-j;
>         if(mult>1<<26) mult=1<<26;
>         mult_ram[j+1]=mult;
>         num[j+1]=0;
>         last_num[j+1]=800000;
>         offset_ram[j+1]=0;
>         count_ram[j+1]=0;
>     }
>     
>     for(i=0;i<1<<30;i=nex){
>         nex=-1;
>         res0=0;
>         //printf("x%d,",i);
>         if(i<mult_ram[1]){
>             for(j=0;j<max;j++){
>                 int tmp=max*2-j;
>                 res1=(i-res0)%(tmp);
>                 if(res1){
>                     res0=tmp-res1;
>                 }
>                 else 
>                     res0=res1;
>                 if(res0<max-j){
>                     buf[j+1][num[j+1]]=i;
>                     res[j+1][num[j+1]]=res0;
>                     num[j+1]++;
>                     if(num[max]==2) {
>                         //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
>                         //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
>                         //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
>                         //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
>                         return i; 
>                     }
>                 }
>                 else
>                     break;
>             }
>             nex=i+1;
>             //printf("a%d,",nex);
>             offset_ram[1]=0;
>             count_ram[1]=1;
>         }
>         else if(i<mult_ram[2]){
>             res0=res[1][offset_ram[1]++];
>             for(j=1;j<max;j++){
>                 int tmp=max*2-j;
>                 res1=(i-res0)%(max*2-j);
>                 if(res1){
>                     res0=max*2-j-res1;
>                 }
>                 else 
>                     res0=res1;
>                 if(res0<max-j){
>                     buf[j+1][num[j+1]]=i;
>                     res[j+1][num[j+1]]=res0;
>                     num[j+1]++; 
>                     if(num[max]==2) {
>                         //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
>                         //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
>                         //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
>                         //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
>                         //for(int k=0;k<num[4];k++)printf("%d,",buf[4][k]);printf("\n");
>                         return i; 
>                     }
>                 }
>                 else
>                     break;
>             }
>             if(offset_ram[1]==num[1]){
>                 offset_ram[1]=0;
>                 count_ram[1]++;
>             }
> 
>                 
>             nex=count_ram[1]*mult_ram[1]+buf[1][offset_ram[1]];
>             offset_ram[2]=0;
>             count_ram[2]=1;
>             //printf("b%d,",nex);
>         }
>         else if(i<mult_ram[3]){
>             res0=res[2][offset_ram[2]++];
>             for(j=2;j<max;j++){
>                 int tmp=max*2-j;
>                 res1=(i-res0)%(tmp);
>                 if(res1){
>                     res0=tmp-res1;
>                 }
>                 else 
>                     res0=res1;
>                 if(res0<max-j){
>                     buf[j+1][num[j+1]]=i;
>                     res[j+1][num[j+1]]=res0;
>                     num[j+1]++; 
>                     if(num[max]==2) {
>                         //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
>                         //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
>                         //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
>                         //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
>                         //for(int k=0;k<num[4];k++)printf("%d,",buf[4][k]);printf("\n");
>                         //for(int k=0;k<num[5];k++)printf("%d,",buf[5][k]);printf("\n");
>                         return i; 
>                     }
>                 }
>                 else
>                     break;
>             }
>             if(offset_ram[2]==num[2]){
>                 offset_ram[2]=0;
>                 count_ram[2]++;
>             }
> 
>                 
>             nex=count_ram[2]*mult_ram[2]+buf[2][offset_ram[2]];
>             offset_ram[3]=0;
>             count_ram[3]=1;
>             //printf("c%d,",nex);
>         }
>         else if(i<mult_ram[4]){
>             res0=res[3][offset_ram[3]++];
>             for(j=3;j<max;j++){
>                 int tmp=max*2-j;
>                 res1=(i-res0)%(tmp);
>                 if(res1){
>                     res0=tmp-res1;
>                 }
>                 else 
>                     res0=res1;
>                 if(res0<max-j){
>                     buf[j+1][num[j+1]]=i;
>                     res[j+1][num[j+1]]=res0;
>                     num[j+1]++; 
>                     if(num[max]==2) {
>                         //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
>                         //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
>                         //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
>                         //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
>                         //for(int k=0;k<num[4];k++)printf("%d,",buf[4][k]);printf("\n");
>                         //for(int k=0;k<num[5];k++)printf("%d,",buf[5][k]);printf("\n");
>                         //for(int k=0;k<num[6];k++)printf("%d,",buf[6][k]);printf("\n");
>                         return i; 
>                     }
>                 }
>                 else
>                     break;
>             }
>             if(offset_ram[3]==num[3]){
>                 offset_ram[3]=0;
>                 count_ram[3]++;
>             }
> 
>                 
>             nex=count_ram[3]*mult_ram[3]+buf[3][offset_ram[3]];
>             offset_ram[4]=0;
>             count_ram[4]=1;
>             //printf("d%d,",nex);
>         }
>         else if(i<mult_ram[5]){
>             res0=res[4][offset_ram[4]++];
>             for(j=4;j<max;j++){
>                 int tmp=max*2-j;
>                 res1=(i-res0)%(tmp);
>                 if(res1){
>                     res0=tmp-res1;
>                 }
>                 else 
>                     res0=res1;
>                 if(res0<max-j){
>                     buf[j+1][num[j+1]]=i;
>                     res[j+1][num[j+1]]=res0;
>                     num[j+1]++; 
>                     if(num[max]==2) {
>                         //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
>                         //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
>                         //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
>                         //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
>                         //for(int k=0;k<num[4];k++)printf("%d,",buf[4][k]);printf("\n");
>                         //for(int k=0;k<num[5];k++)printf("%d,",buf[5][k]);printf("\n");
>                         //for(int k=0;k<num[6];k++)printf("%d,",buf[6][k]);printf("\n");
>                         return i; 
>                     }
>                 }
>                 else
>                     break;
>             }
>             if(offset_ram[4]==num[4]){
>                 offset_ram[4]=0;
>                 count_ram[4]++;
>             }
> 
>                 
>             nex=count_ram[4]*mult_ram[4]+buf[4][offset_ram[4]];
>             offset_ram[5]=0;
>             count_ram[5]=1;
>             //printf("d%d,",nex);
>         }
>         else if(i<mult_ram[6]){
>             res0=res[5][offset_ram[5]++];
>             for(j=5;j<max;j++){
>                 int tmp=max*2-j;
>                 res1=(i-res0)%(tmp);
>                 if(res1){
>                     res0=tmp-res1;
>                 }
>                 else 
>                     res0=res1;
>                 if(res0<max-j){
>                     buf[j+1][num[j+1]]=i;
>                     res[j+1][num[j+1]]=res0;
>                     num[j+1]++; 
>                     if(num[max]==2) {
>                         //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
>                         //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
>                         //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
>                         //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
>                         //for(int k=0;k<num[4];k++)printf("%d,",buf[4][k]);printf("\n");
>                         //for(int k=0;k<num[5];k++)printf("%d,",buf[5][k]);printf("\n");
>                         //for(int k=0;k<num[6];k++)printf("%d,",buf[6][k]);printf("\n");
> 
>                         //for(int k=0;k<15;k++)printf("%d,",num[k]);printf("\n");
>                         return i; 
>                     }
>                 }
>                 else
>                     break;
>             }
>             if(offset_ram[5]==num[5]){
>                 offset_ram[5]=0;
>                 count_ram[5]++;
>             }
> 
>                 
>             nex=count_ram[5]*mult_ram[5]+buf[5][offset_ram[5]];
>             offset_ram[6]=0;
>             count_ram[6]=1;
>             //printf("d%d,",nex);
>         }
>         else{
>             break;
>         }
>     }
>     //for(j=0;j<max+1;j++){
>     //    for(i=0;i<num[j];i++){
>     //        printf("%d,",buf[j][i]);
>     //    }
>     //    printf("\n");
>     //}
>     //for(i=0;i<15;i++)
>     //    printf("%d,",num[i]);
>     //printf("\n");
>     return i;
> }
> */
> 
> int main(){
>     int max_p  ;
>     int i;
>     //tmp_buf0[0]=0;
> 
>     int tmp;
>     int max;
>     int a=scanf("%d",&max);
>     int ans[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,13482720,25779600,68468401,610346880};
>     while(max){
>         tmp=core(max);
>         printf("%d\n",tmp);
>         //input(tmp_buf,max);
>         //maopao(tmp_buf,max);
>         //i=core(tmp_buf,max);
>         //printf("%d\n",i);
>         a=scanf("%d",&max);
>     }
>     return 0;   
> }