#include <bitset>
#include <iostream>
#include <iomanip>
using namespace std;

/*
Achtung: V={0,1,...,n-1}
Modifikation: Nicht pi(1)=1 sondern pi(n)=n,
damit S nur aus {0,1,...,n-2}
*/

unsigned long formel(
	unsigned int n, unsigned int m[], unsigned int g[],
	unsigned int i, bitset<30> S){
  bitset<30>  S2;
  unsigned int minimum=2000000000, m2;
  if (S.none()) return m[i+n*(n-1)] ;
  else {
     for (unsigned j=0; j<n-1; j++){
       if (S.test(j)){
           S2=S;
           S2.set(j,0);
           m2=m[i+n*j]+g[j+n*S2.to_ulong()];
           if (m2< minimum) minimum=m2;
       }
     }
     return minimum;
   }
};

int main(){

unsigned int n;
cin >> n;
unsigned int zpn = 1<<(n-1); 
unsigned int m[n*n], g[n*zpn];

cout << "Parameter: "<< n <<", Teilmengen: "<< zpn<<"\n";

for(unsigned int i=0; i<n;i++) for(unsigned int j=0; j<n;j++) m[i+n*j]=4;
for(unsigned int i=0; i<n;i++)  m[i+n*i]=0;
for(unsigned int i=0; i<n-1;i++)  m[i+n*(i+1)]=2;  m[n-1 + n*0]=2;


for(unsigned int i=0; i<n-1;i++)
	g[i+n*0]=formel(n,m,g,i,0);

for (unsigned int k=1; k<= n-2; k++){
    cout << k<< "...\n";
    for (unsigned int iS=1; iS< zpn;iS+=1) {
       bitset<30> S(iS);
       if (S.count()==k) {
         for (unsigned int i=0; i<n-1;i++)
           if (!S.test(i)){
                g[i+n*iS]=formel(n,m,g,i,iS);
	    };
    }}
}
cout << "\nResultat: "<<formel(n,m,g,n-1, zpn-1) << "\n";

}