#include<cstdio>
int res[1024];
int main(){
res[3]=2;
res[4]=2;
res[5]=3;
res[6]=3;
res[7]=4;
res[8]=3;
res[9]=4;
res[10]=4;
res[11]=5;
res[12]=4;
res[13]=5;
res[14]=5;
res[15]=5;
res[16]=4;
res[17]=5;
res[18]=5;
res[19]=0;
res[20]=5;
res[21]=6;
res[22]=6;
res[23]=0;
res[24]=5;
res[25]=6;
res[26]=6;
res[27]=6;
res[28]=6;
res[29]=0;
res[30]=6;
res[31]=0;
res[32]=5;
res[33]=7;
res[34]=6;
res[35]=7;
res[36]=6;
res[37]=0;
res[38]=0;
res[39]=7;
res[40]=6;
res[41]=0;
res[42]=7;
res[43]=0;
res[44]=7;
res[45]=7;
res[46]=0;
res[47]=0;
res[48]=6;
res[49]=8;
res[50]=7;
res[51]=7;
res[52]=7;
res[53]=0;
res[54]=7;
res[55]=8;
res[56]=7;
res[57]=0;
res[58]=0;
res[59]=0;
res[60]=7;
res[61]=0;
res[62]=0;
res[63]=8;
res[64]=6;
res[65]=8;
res[66]=8;
res[67]=0;
res[68]=7;
res[69]=0;
res[70]=8;
res[71]=0;
res[72]=7;
res[73]=0;
res[74]=0;
res[75]=8;
res[76]=0;
res[77]=0;
res[78]=8;
res[79]=0;
res[80]=7;
res[81]=8;
res[82]=0;
res[83]=0;
res[84]=8;
res[85]=0;
res[86]=0;
res[87]=0;
res[88]=8;
res[89]=0;
res[90]=8;
res[91]=0;
res[92]=0;
res[93]=0;
res[94]=0;
res[95]=0;
res[96]=7;
res[97]=0;
res[98]=9;
res[99]=0;
res[100]=8;
res[101]=0;
res[102]=0;
res[103]=0;
res[104]=8;
res[105]=9;
res[106]=0;
res[107]=0;
res[108]=8;
res[109]=0;
res[110]=0;
res[111]=0;
res[112]=8;
res[113]=0;
res[114]=0;
res[115]=0;
res[116]=0;
res[117]=0;
res[118]=0;
res[119]=0;
res[120]=8;
res[121]=0;
res[122]=0;
res[123]=0;
res[124]=0;
res[125]=9;
res[126]=9;
res[127]=0;
res[128]=7;
res[129]=0;
res[130]=0;
res[131]=0;
res[132]=0;
res[133]=0;
res[134]=0;
res[135]=9;
res[136]=0;
res[137]=0;
res[138]=0;
res[139]=0;
res[140]=9;
res[141]=0;
res[142]=0;
res[143]=0;
res[144]=8;
res[145]=0;
res[146]=0;
res[147]=10;
res[148]=0;
res[149]=0;
res[150]=9;
res[151]=0;
res[152]=0;
res[153]=0;
res[154]=0;
res[155]=0;
res[156]=0;
res[157]=0;
res[158]=0;
res[159]=0;
res[160]=8;
res[161]=0;
res[162]=9;
res[163]=0;
res[164]=0;
res[165]=0;
res[166]=0;
res[167]=0;
res[168]=9;
res[169]=0;
res[170]=0;
res[171]=0;
res[172]=0;
res[173]=0;
res[174]=0;
res[175]=10;
res[176]=0;
res[177]=0;
res[178]=0;
res[179]=0;
res[180]=9;
res[181]=0;
res[182]=0;
res[183]=0;
res[184]=0;
res[185]=0;
res[186]=0;
res[187]=0;
res[188]=0;
res[189]=10;
res[190]=0;
res[191]=0;
res[192]=8;
res[193]=0;
res[194]=0;
res[195]=0;
res[196]=10;
res[197]=0;
res[198]=0;
res[199]=0;
res[200]=9;
res[201]=0;
res[202]=0;
res[203]=0;
res[204]=0;
res[205]=0;
res[206]=0;
res[207]=0;
res[208]=0;
res[209]=0;
res[210]=10;
res[211]=0;
res[212]=0;
res[213]=0;
res[214]=0;
res[215]=0;
res[216]=9;
res[217]=0;
res[218]=0;
res[219]=0;
res[220]=0;
res[221]=0;
res[222]=0;
res[223]=0;
res[224]=9;
res[225]=10;
res[226]=0;
res[227]=0;
res[228]=0;
res[229]=0;
res[230]=0;
res[231]=0;
res[232]=0;
res[233]=0;
res[234]=0;
res[235]=0;
res[236]=0;
res[237]=0;
res[238]=0;
res[239]=0;
res[240]=9;
res[241]=0;
res[242]=0;
res[243]=10;
res[244]=0;
res[245]=0;
res[246]=0;
res[247]=0;
res[248]=0;
res[249]=0;
res[250]=10;
res[251]=0;
res[252]=10;
res[253]=0;
res[254]=0;
res[255]=0;
res[256]=8;
res[257]=0;
res[258]=0;
res[259]=0;
res[260]=0;
res[261]=0;
res[262]=0;
res[263]=0;
res[264]=0;
res[265]=0;
res[266]=0;
res[267]=0;
res[268]=0;
res[269]=0;
res[270]=10;
res[271]=0;
res[272]=0;
res[273]=0;
res[274]=0;
res[275]=0;
res[276]=0;
res[277]=0;
res[278]=0;
res[279]=0;
res[280]=10;
res[281]=0;
res[282]=0;
res[283]=0;
res[284]=0;
res[285]=0;
res[286]=0;
res[287]=0;
res[288]=9;
res[289]=0;
res[290]=0;
res[291]=0;
res[292]=0;
res[293]=0;
res[294]=0;
res[295]=0;
res[296]=0;
res[297]=0;
res[298]=0;
res[299]=0;
res[300]=10;
res[301]=0;
res[302]=0;
res[303]=0;
res[304]=0;
res[305]=0;
res[306]=0;
res[307]=0;
res[308]=0;
res[309]=0;
res[310]=0;
res[311]=0;
res[312]=0;
res[313]=0;
res[314]=0;
res[315]=0;
res[316]=0;
res[317]=0;
res[318]=0;
res[319]=0;
res[320]=9;
res[321]=0;
res[322]=0;
res[323]=0;
res[324]=10;
res[325]=0;
res[326]=0;
res[327]=0;
res[328]=0;
res[329]=0;
res[330]=0;
res[331]=0;
res[332]=0;
res[333]=0;
res[334]=0;
res[335]=0;
res[336]=10;
res[337]=0;
res[338]=0;
res[339]=0;
res[340]=0;
res[341]=0;
res[342]=0;
res[343]=0;
res[344]=0;
res[345]=0;
res[346]=0;
res[347]=0;
res[348]=0;
res[349]=0;
res[350]=0;
res[351]=0;
res[352]=0;
res[353]=0;
res[354]=0;
res[355]=0;
res[356]=0;
res[357]=0;
res[358]=0;
res[359]=0;
res[360]=10;
res[361]=0;
res[362]=0;
res[363]=0;
res[364]=0;
res[365]=0;
res[366]=0;
res[367]=0;
res[368]=0;
res[369]=0;
res[370]=0;
res[371]=0;
res[372]=0;
res[373]=0;
res[374]=0;
res[375]=0;
res[376]=0;
res[377]=0;
res[378]=0;
res[379]=0;
res[380]=0;
res[381]=0;
res[382]=0;
res[383]=0;
res[384]=9;
res[385]=0;
res[386]=0;
res[387]=0;
res[388]=0;
res[389]=0;
res[390]=0;
res[391]=0;
res[392]=0;
res[393]=0;
res[394]=0;
res[395]=0;
res[396]=0;
res[397]=0;
res[398]=0;
res[399]=0;
res[400]=10;
res[401]=0;
res[402]=0;
res[403]=0;
res[404]=0;
res[405]=0;
res[406]=0;
res[407]=0;
res[408]=0;
res[409]=0;
res[410]=0;
res[411]=0;
res[412]=0;
res[413]=0;
res[414]=0;
res[415]=0;
res[416]=0;
res[417]=0;
res[418]=0;
res[419]=0;
res[420]=0;
res[421]=0;
res[422]=0;
res[423]=0;
res[424]=0;
res[425]=0;
res[426]=0;
res[427]=0;
res[428]=0;
res[429]=0;
res[430]=0;
res[431]=0;
res[432]=10;
res[433]=0;
res[434]=0;
res[435]=0;
res[436]=0;
res[437]=0;
res[438]=0;
res[439]=0;
res[440]=0;
res[441]=0;
res[442]=0;
res[443]=0;
res[444]=0;
res[445]=0;
res[446]=0;
res[447]=0;
res[448]=10;
res[449]=0;
res[450]=0;
res[451]=0;
res[452]=0;
res[453]=0;
res[454]=0;
res[455]=0;
res[456]=0;
res[457]=0;
res[458]=0;
res[459]=0;
res[460]=0;
res[461]=0;
res[462]=0;
res[463]=0;
res[464]=0;
res[465]=0;
res[466]=0;
res[467]=0;
res[468]=0;
res[469]=0;
res[470]=0;
res[471]=0;
res[472]=0;
res[473]=0;
res[474]=0;
res[475]=0;
res[476]=0;
res[477]=0;
res[478]=0;
res[479]=0;
res[480]=10;
res[481]=0;
res[482]=0;
res[483]=0;
res[484]=0;
res[485]=0;
res[486]=0;
res[487]=0;
res[488]=0;
res[489]=0;
res[490]=0;
res[491]=0;
res[492]=0;
res[493]=0;
res[494]=0;
res[495]=0;
res[496]=0;
res[497]=0;
res[498]=0;
res[499]=0;
res[500]=0;
res[501]=0;
res[502]=0;
res[503]=0;
res[504]=0;
res[505]=0;
res[506]=0;
res[507]=0;
res[508]=0;
res[509]=0;
res[510]=0;
res[511]=0;
res[512]=9;
res[513]=0;
res[514]=0;
res[515]=0;
res[516]=0;
res[517]=0;
res[518]=0;
res[519]=0;
res[520]=0;
res[521]=0;
res[522]=0;
res[523]=0;
res[524]=0;
res[525]=0;
res[526]=0;
res[527]=0;
res[528]=0;
res[529]=0;
res[530]=0;
res[531]=0;
res[532]=0;
res[533]=0;
res[534]=0;
res[535]=0;
res[536]=0;
res[537]=0;
res[538]=0;
res[539]=0;
res[540]=0;
res[541]=0;
res[542]=0;
res[543]=0;
res[544]=0;
res[545]=0;
res[546]=0;
res[547]=0;
res[548]=0;
res[549]=0;
res[550]=0;
res[551]=0;
res[552]=0;
res[553]=0;
res[554]=0;
res[555]=0;
res[556]=0;
res[557]=0;
res[558]=0;
res[559]=0;
res[560]=0;
res[561]=0;
res[562]=0;
res[563]=0;
res[564]=0;
res[565]=0;
res[566]=0;
res[567]=0;
res[568]=0;
res[569]=0;
res[570]=0;
res[571]=0;
res[572]=0;
res[573]=0;
res[574]=0;
res[575]=0;
res[576]=10;
res[577]=0;
res[578]=0;
res[579]=0;
res[580]=0;
res[581]=0;
res[582]=0;
res[583]=0;
res[584]=0;
res[585]=0;
res[586]=0;
res[587]=0;
res[588]=0;
res[589]=0;
res[590]=0;
res[591]=0;
res[592]=0;
res[593]=0;
res[594]=0;
res[595]=0;
res[596]=0;
res[597]=0;
res[598]=0;
res[599]=0;
res[600]=0;
res[601]=0;
res[602]=0;
res[603]=0;
res[604]=0;
res[605]=0;
res[606]=0;
res[607]=0;
res[608]=0;
res[609]=0;
res[610]=0;
res[611]=0;
res[612]=0;
res[613]=0;
res[614]=0;
res[615]=0;
res[616]=0;
res[617]=0;
res[618]=0;
res[619]=0;
res[620]=0;
res[621]=0;
res[622]=0;
res[623]=0;
res[624]=0;
res[625]=0;
res[626]=0;
res[627]=0;
res[628]=0;
res[629]=0;
res[630]=0;
res[631]=0;
res[632]=0;
res[633]=0;
res[634]=0;
res[635]=0;
res[636]=0;
res[637]=0;
res[638]=0;
res[639]=0;
res[640]=10;
res[641]=0;
res[642]=0;
res[643]=0;
res[644]=0;
res[645]=0;
res[646]=0;
res[647]=0;
res[648]=0;
res[649]=0;
res[650]=0;
res[651]=0;
res[652]=0;
res[653]=0;
res[654]=0;
res[655]=0;
res[656]=0;
res[657]=0;
res[658]=0;
res[659]=0;
res[660]=0;
res[661]=0;
res[662]=0;
res[663]=0;
res[664]=0;
res[665]=0;
res[666]=0;
res[667]=0;
res[668]=0;
res[669]=0;
res[670]=0;
res[671]=0;
res[672]=0;
res[673]=0;
res[674]=0;
res[675]=0;
res[676]=0;
res[677]=0;
res[678]=0;
res[679]=0;
res[680]=0;
res[681]=0;
res[682]=0;
res[683]=0;
res[684]=0;
res[685]=0;
res[686]=0;
res[687]=0;
res[688]=0;
res[689]=0;
res[690]=0;
res[691]=0;
res[692]=0;
res[693]=0;
res[694]=0;
res[695]=0;
res[696]=0;
res[697]=0;
res[698]=0;
res[699]=0;
res[700]=0;
res[701]=0;
res[702]=0;
res[703]=0;
res[704]=0;
res[705]=0;
res[706]=0;
res[707]=0;
res[708]=0;
res[709]=0;
res[710]=0;
res[711]=0;
res[712]=0;
res[713]=0;
res[714]=0;
res[715]=0;
res[716]=0;
res[717]=0;
res[718]=0;
res[719]=0;
res[720]=0;
res[721]=0;
res[722]=0;
res[723]=0;
res[724]=0;
res[725]=0;
res[726]=0;
res[727]=0;
res[728]=0;
res[729]=0;
res[730]=0;
res[731]=0;
res[732]=0;
res[733]=0;
res[734]=0;
res[735]=0;
res[736]=0;
res[737]=0;
res[738]=0;
res[739]=0;
res[740]=0;
res[741]=0;
res[742]=0;
res[743]=0;
res[744]=0;
res[745]=0;
res[746]=0;
res[747]=0;
res[748]=0;
res[749]=0;
res[750]=0;
res[751]=0;
res[752]=0;
res[753]=0;
res[754]=0;
res[755]=0;
res[756]=0;
res[757]=0;
res[758]=0;
res[759]=0;
res[760]=0;
res[761]=0;
res[762]=0;
res[763]=0;
res[764]=0;
res[765]=0;
res[766]=0;
res[767]=0;
res[768]=10;
res[769]=0;
res[770]=0;
res[771]=0;
res[772]=0;
res[773]=0;
res[774]=0;
res[775]=0;
res[776]=0;
res[777]=0;
res[778]=0;
res[779]=0;
res[780]=0;
res[781]=0;
res[782]=0;
res[783]=0;
res[784]=0;
res[785]=0;
res[786]=0;
res[787]=0;
res[788]=0;
res[789]=0;
res[790]=0;
res[791]=0;
res[792]=0;
res[793]=0;
res[794]=0;
res[795]=0;
res[796]=0;
res[797]=0;
res[798]=0;
res[799]=0;
res[800]=0;
res[801]=0;
res[802]=0;
res[803]=0;
res[804]=0;
res[805]=0;
res[806]=0;
res[807]=0;
res[808]=0;
res[809]=0;
res[810]=0;
res[811]=0;
res[812]=0;
res[813]=0;
res[814]=0;
res[815]=0;
res[816]=0;
res[817]=0;
res[818]=0;
res[819]=0;
res[820]=0;
res[821]=0;
res[822]=0;
res[823]=0;
res[824]=0;
res[825]=0;
res[826]=0;
res[827]=0;
res[828]=0;
res[829]=0;
res[830]=0;
res[831]=0;
res[832]=0;
res[833]=0;
res[834]=0;
res[835]=0;
res[836]=0;
res[837]=0;
res[838]=0;
res[839]=0;
res[840]=0;
res[841]=0;
res[842]=0;
res[843]=0;
res[844]=0;
res[845]=0;
res[846]=0;
res[847]=0;
res[848]=0;
res[849]=0;
res[850]=0;
res[851]=0;
res[852]=0;
res[853]=0;
res[854]=0;
res[855]=0;
res[856]=0;
res[857]=0;
res[858]=0;
res[859]=0;
res[860]=0;
res[861]=0;
res[862]=0;
res[863]=0;
res[864]=0;
res[865]=0;
res[866]=0;
res[867]=0;
res[868]=0;
res[869]=0;
res[870]=0;
res[871]=0;
res[872]=0;
res[873]=0;
res[874]=0;
res[875]=0;
res[876]=0;
res[877]=0;
res[878]=0;
res[879]=0;
res[880]=0;
res[881]=0;
res[882]=0;
res[883]=0;
res[884]=0;
res[885]=0;
res[886]=0;
res[887]=0;
res[888]=0;
res[889]=0;
res[890]=0;
res[891]=0;
res[892]=0;
res[893]=0;
res[894]=0;
res[895]=0;
res[896]=0;
res[897]=0;
res[898]=0;
res[899]=0;
res[900]=0;
res[901]=0;
res[902]=0;
res[903]=0;
res[904]=0;
res[905]=0;
res[906]=0;
res[907]=0;
res[908]=0;
res[909]=0;
res[910]=0;
res[911]=0;
res[912]=0;
res[913]=0;
res[914]=0;
res[915]=0;
res[916]=0;
res[917]=0;
res[918]=0;
res[919]=0;
res[920]=0;
res[921]=0;
res[922]=0;
res[923]=0;
res[924]=0;
res[925]=0;
res[926]=0;
res[927]=0;
res[928]=0;
res[929]=0;
res[930]=0;
res[931]=0;
res[932]=0;
res[933]=0;
res[934]=0;
res[935]=0;
res[936]=0;
res[937]=0;
res[938]=0;
res[939]=0;
res[940]=0;
res[941]=0;
res[942]=0;
res[943]=0;
res[944]=0;
res[945]=0;
res[946]=0;
res[947]=0;
res[948]=0;
res[949]=0;
res[950]=0;
res[951]=0;
res[952]=0;
res[953]=0;
res[954]=0;
res[955]=0;
res[956]=0;
res[957]=0;
res[958]=0;
res[959]=0;
res[960]=0;
res[961]=0;
res[962]=0;
res[963]=0;
res[964]=0;
res[965]=0;
res[966]=0;
res[967]=0;
res[968]=0;
res[969]=0;
res[970]=0;
res[971]=0;
res[972]=0;
res[973]=0;
res[974]=0;
res[975]=0;
res[976]=0;
res[977]=0;
res[978]=0;
res[979]=0;
res[980]=0;
res[981]=0;
res[982]=0;
res[983]=0;
res[984]=0;
res[985]=0;
res[986]=0;
res[987]=0;
res[988]=0;
res[989]=0;
res[990]=0;
res[991]=0;
res[992]=0;
res[993]=0;
res[994]=0;
res[995]=0;
res[996]=0;
res[997]=0;
res[998]=0;
res[999]=0;
res[1000]=0;
res[1001]=0;
int n;
scanf("%d",&n);
if(res[n]>0) printf("%d\n",res[n]);
else printf("14\n");
return 0;
}
