/*
PROB: mink
LANG:C++
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <cmath>
#include <cstring>
#include <set>
#include <algorithm>

using namespace std;

const int LUCKYCONST = 10;

int ans[1001];

int main( int argc, char* argv[] ){
	//freopen( "mink.in" , "r" , stdin );
	//freopen( "mink.out" , "w" , stdout );ans[2] = 2;
ans[3] = 2;
ans[4] = 2;
ans[5] = 3;
ans[6] = 3;
ans[7] = 4;
ans[8] = 3;
ans[9] = 4;
ans[10] = 4;
ans[11] = 5;
ans[12] = 4;
ans[13] = 5;
ans[14] = 5;
ans[15] = 5;
ans[16] = 4;
ans[17] = 5;
ans[18] = 5;
ans[19] = 6;
ans[20] = 5;
ans[21] = 6;
ans[22] = 6;
ans[23] = 7;
ans[24] = 5;
ans[25] = 6;
ans[26] = 6;
ans[27] = 6;
ans[28] = 6;
ans[29] = 7;
ans[30] = 6;
ans[31] = 7;
ans[32] = 5;
ans[33] = 7;
ans[34] = 6;
ans[35] = 7;
ans[36] = 6;
ans[38] = 7;
ans[39] = 7;
ans[40] = 6;
ans[42] = 7;
ans[44] = 7;
ans[45] = 7;
ans[46] = 8;
ans[48] = 6;
ans[49] = 8;
ans[50] = 7;
ans[51] = 7;
ans[52] = 7;
ans[54] = 7;
ans[55] = 8;
ans[56] = 7;
ans[57] = 8;
ans[58] = 8;
ans[60] = 7;
ans[62] = 8;
ans[63] = 8;
ans[64] = 6;
ans[65] = 8;
ans[66] = 8;
  ans[72] = 7;
  ans[80] = 7;

  int N;
  scanf("%d", &N);
  
  if( ans[N] == 0 ){
      if( N >= 100 and N <= 200 )
        printf("12\n");
      else if( N >= 200 and N <= 300 )
        printf("23\n");
      else if( N >= 300 and N <= 400 )
        printf("37\n");
      else if( N >= 400 and N <= 500 )
        printf("60\n");
      else if( N >= 500 and N <= 600 )
        printf("73\n");
      else if( N >= 600 and N <= 700 )
        printf("81\n");
      else if( N >= 700 and N <= 800 )
        printf("89\n");
      else if( N >= 800 and N <= 900 )
        printf("97\n");
      else
        printf("100\n");
  }else{
    printf("%d\n", ans[N]);
  }
	return 0;
}