adgԴ??

       #include <cstdio>

       #define UINT unsigned int

       #define ULL unsigned long long

       #define MAXN ;

       using namespace std;

       int N,ans,minstep;

       UINT Row,Col;

       UINT Lft,Rgt;

       inline UINT lowbit(UINT x){

           return x&(-x);

       }

       bool check(){

           UINT tR=~Row,tC;

           UINT curR,curC;

           while(tR){

               curR=lowbit(tR);

               tR ^= curR;

               tC = ~Col;

               while(tC){

                   curC=lowbit(tC);

                   tC^=curC;

                   if((Rgt & (curR*curC))!=0 || (Lft & ((1<<(N-1))/curR*curC))!=0)

                       continue;

                   return false;

               }

           }

           return true;

       }

       void dfs(int row,int used,UINT col,UINT dig,UINT adg){

           if(used>minstep)

               return;

           if(row == N){

               if(check()){

                   if(used < minstep){

                       minstep = used;

                       ans=0;

                   }

                   ans++;

               }

               return;

           }

           UINT status=~(col|dig|adg);

           UINT binRow=(1<<row);

           while(status){

               UINT t=status&(-status);

               Col^=t;

               Row^=binRow;

               Lft^=((1<<(N-1))/binRow*t);

               Rgt^=(binRow*t);

               dfs(row+1,used+1,(t|col),(t|dig)>>1,(t|adg)<<1);

               Col^=t;

               Row^=binRow;

               Lft^=((1<<(N-1))/binRow*t);

               Rgt^=(binRow*t);

               status^=t;

           }

           dfs(row+1,used,col,dig>>1,adg<<1);

       }

       int main(){

           while(cin>>N){

               UINT col=(1<<N)-1;

               col=~col;

               ans=0;

               minstep=N+1;

               Row=Col=col;

               Rgt=Lft=0;

               dfs(0,0,col,0,0);

               cout<<minstep<<endl<<ans<<endl;

           }

           return 0;

       }