#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100004;
int n,m,a[N],f[N],ans;
int main()
{
	f[7]=2,f[25]=2,f[30]=3,f[42]=2,f[45]=3,f[51]=3,f[52]=2,f[75]=3,f[76]=2,f[82]=2,f[85]=3,f[97]=2,f[102]=3,f[120]=3,f[127]=5,f[385]=2,f[390]=3,f[408]=3,f[415]=5,f[427]=4,f[428]=4,f[434]=4,f[437]=4,f[458]=4,f[461]=4,f[467]=4,f[468]=4,f[480]=3,f[487]=5,f[505]=5,f[510]=6,f[642]=2,f[645]=3,f[667]=4,f[668]=4,f[680]=3,f[687]=5,f[689]=4,f[694]=4,f[713]=4,f[718]=4,f[720]=3,f[727]=5,f[739]=4,f[740]=4,f[762]=5,f[765]=6,f[771]=3,f[772]=2,f[794]=4,f[797]=4,f[809]=4,f[814]=4,f[816]=3,f[823]=5,f[840]=3,f[847]=5,f[849]=4,f[854]=4,f[866]=4,f[869]=4,f[891]=6,f[892]=5,f[1155]=3,f[1156]=2,f[1178]=4,f[1181]=4,f[1193]=4,f[1198]=4,f[1200]=3,f[1207]=5,f[1224]=3,f[1231]=5,f[1233]=4,f[1238]=4,f[1250]=4,f[1253]=4,f[1275]=6,f[1276]=5,f[1282]=2,f[1285]=3,f[1307]=4,f[1308]=4,f[1320]=3,f[1327]=5,f[1329]=4,f[1334]=4,f[1353]=4,f[1358]=4,f[1360]=3,f[1367]=5,f[1379]=4,f[1380]=4,f[1402]=5,f[1405]=6,f[1537]=2,f[1542]=3,f[1560]=3,f[1567]=5,f[1579]=4,f[1580]=4,f[1586]=4,f[1589]=4,f[1610]=4,f[1613]=4,f[1619]=4,f[1620]=4,f[1632]=3,f[1639]=5,f[1657]=5,f[1662]=6,f[1920]=3,f[1927]=5,f[1945]=5,f[1950]=6,f[1962]=5,f[1965]=6,f[1971]=6,f[1972]=5,f[1995]=6,f[1996]=5,f[2002]=5,f[2005]=6,f[2017]=5,f[2022]=6,f[2040]=6,f[2047]=8,f[2184]=2,f[2191]=4,f[2193]=3,f[2198]=4,f[2210]=3,f[2213]=4,f[2235]=5,f[2236]=4,f[2243]=4,f[2244]=3,f[2266]=4,f[2269]=5,f[2281]=4,f[2286]=5,f[2288]=4,f[2295]=6,f[2313]=3,f[2318]=4,f[2320]=2,f[2327]=4,f[2339]=4,f[2340]=3,f[2362]=4,f[2365]=5,f[2370]=3,f[2373]=4,f[2395]=5,f[2396]=4,f[2408]=4,f[2415]=6,f[2417]=4,f[2422]=5,f[2570]=3,f[2573]=4,f[2579]=4,f[2580]=3,f[2592]=2,f[2599]=4,f[2617]=4,f[2622]=5,f[2625]=3,f[2630]=4,f[2648]=4,f[2655]=6,f[2667]=5,f[2668]=4,f[2674]=4,f[2677]=5,f[2955]=5,f[2956]=4,f[2962]=4,f[2965]=5,f[2977]=4,f[2982]=5,f[3000]=5,f[3007]=7,f[3008]=4,f[3015]=6,f[3033]=6,f[3038]=6,f[3050]=6,f[3053]=6,f[3059]=6,f[3060]=6,f[3083]=4,f[3084]=3,f[3090]=3,f[3093]=4,f[3105]=3,f[3110]=4,f[3128]=4,f[3135]=6,f[3136]=2,f[3143]=4,f[3161]=4,f[3166]=5,f[3178]=4,f[3181]=5,f[3187]=5,f[3188]=4,f[3466]=4,f[3469]=5,f[3475]=5,f[3476]=4,f[3488]=4,f[3495]=6,f[3513]=6,f[3518]=6,f[3521]=4,f[3526]=5,f[3544]=5,f[3551]=7,f[3563]=6,f[3564]=6,f[3570]=6,f[3573]=6,f[3721]=4,f[3726]=5,f[3728]=4,f[3735]=6,f[3747]=5,f[3748]=4,f[3770]=6,f[3773]=6,f[3778]=4,f[3781]=5,f[3803]=6,f[3804]=6,f[3816]=5,f[3823]=7,f[3825]=6,f[3830]=6,f[3848]=4,f[3855]=6,f[3857]=4,f[3862]=5,f[3874]=4,f[3877]=5,f[3899]=6,f[3900]=6,f[3907]=5,f[3908]=4,f[3930]=6,f[3933]=6,f[3945]=6,f[3950]=6,f[3952]=5,f[3959]=7,f[4233]=3,f[4238]=4,f[4240]=2,f[4247]=4,f[4259]=4,f[4260]=3,f[4282]=4,f[4285]=5,f[4290]=3,f[4293]=4,f[4315]=5,f[4316]=4,f[4328]=4,f[4335]=6,f[4337]=4,f[4342]=5,f[4360]=2,f[4367]=4,f[4369]=3,f[4374]=4,f[4386]=3,f[4389]=4,f[4411]=5,f[4412]=4,f[4419]=4,f[4420]=3,f[4442]=4,f[4445]=5,f[4457]=4,f[4462]=5,f[4464]=4,f[4471]=6,f[4619]=4,f[4620]=3,f[4626]=3,f[4629]=4,f[4641]=3,f[4646]=4,f[4664]=4,f[4671]=6,f[4672]=2,f[4679]=4,f[4697]=4,f[4702]=5,f[4714]=4,f[4717]=5,f[4723]=5,f[4724]=4,f[5002]=4,f[5005]=5,f[5011]=5,f[5012]=4,f[5024]=4,f[5031]=6,f[5049]=6,f[5054]=6,f[5057]=4,f[5062]=5,f[5080]=5,f[5087]=7,f[5099]=6,f[5100]=6,f[5106]=6,f[5109]=6,f[5130]=3,f[5133]=4,f[5139]=4,f[5140]=3,f[5152]=2,f[5159]=4,f[5177]=4,f[5182]=5,f[5185]=3,f[5190]=4,f[5208]=4,f[5215]=6,f[5227]=5,f[5228]=4,f[5234]=4,f[5237]=5,f[5515]=5,f[5516]=4,f[5522]=4,f[5525]=5,f[5537]=4,f[5542]=5,f[5560]=5,f[5567]=7,f[5568]=4,f[5575]=6,f[5593]=6,f[5598]=6,f[5610]=6,f[5613]=6,f[5619]=6,f[5620]=6,f[5768]=4,f[5775]=6,f[5777]=4,f[5782]=5,f[5794]=4,f[5797]=5,f[5819]=6,f[5820]=6,f[5827]=5,f[5828]=4,f[5850]=6,f[5853]=6,f[5865]=6,f[5870]=6,f[5872]=5,f[5879]=7,f[5897]=4,f[5902]=5,f[5904]=4,f[5911]=6,f[5923]=5,f[5924]=4,f[5946]=6,f[5949]=6,f[5954]=4,f[5957]=5,f[5979]=6,f[5980]=6,f[5992]=5,f[5999]=7,f[6001]=6,f[6006]=6,f[6145]=2,f[6150]=3,f[6168]=3,f[6175]=5,f[6187]=4,f[6188]=4,f[6194]=4,f[6197]=4,f[6218]=4,f[6221]=4,f[6227]=4,f[6228]=4,f[6240]=3,f[6247]=5,f[6265]=5,f[6270]=6,f[6528]=3,f[6535]=5,f[6553]=5,f[6558]=6,f[6570]=5,f[6573]=6,f[6579]=6,f[6580]=5,f[6603]=6,f[6604]=5,f[6610]=5,f[6613]=6,f[6625]=5,f[6630]=6,f[6648]=6,f[6655]=8,f[6787]=4,f[6788]=4,f[6810]=5,f[6813]=6,f[6825]=5,f[6830]=6,f[6832]=4,f[6839]=6,f[6856]=4,f[6863]=6,f[6865]=5,f[6870]=6,f[6882]=5,f[6885]=6,f[6907]=7,f[6908]=6,f[6914]=4,f[6917]=4,f[6939]=6,f[6940]=5,f[6952]=4,f[6959]=6,f[6961]=5,f[6966]=6,f[6985]=5,f[6990]=6,f[6992]=4,f[6999]=6,f[7011]=6,f[7012]=5,f[7034]=6,f[7037]=7,f[7298]=4,f[7301]=4,f[7323]=6,f[7324]=5,f[7336]=4,f[7343]=6,f[7345]=5,f[7350]=6,f[7369]=5,f[7374]=6,f[7376]=4,f[7383]=6,f[7395]=6,f[7396]=5,f[7418]=6,f[7421]=7,f[7427]=4,f[7428]=4,f[7450]=5,f[7453]=6,f[7465]=5,f[7470]=6,f[7472]=4,f[7479]=6,f[7496]=4,f[7503]=6,f[7505]=5,f[7510]=6,f[7522]=5,f[7525]=6,f[7547]=7,f[7548]=6,f[7680]=3,f[7687]=5,f[7705]=5,f[7710]=6,f[7722]=5,f[7725]=6,f[7731]=6,f[7732]=5,f[7755]=6,f[7756]=5,f[7762]=5,f[7765]=6,f[7777]=5,f[7782]=6,f[7800]=6,f[7807]=8,f[8065]=5,f[8070]=6,f[8088]=6,f[8095]=8,f[8107]=7,f[8108]=6,f[8114]=6,f[8117]=7,f[8138]=6,f[8141]=7,f[8147]=7,f[8148]=6,f[8160]=6,f[8167]=8,f[8185]=8,f[8190]=8,f[8330]=3,f[8333]=4,f[8339]=4,f[8340]=3,f[8352]=2,f[8359]=4,f[8377]=4,f[8382]=5,f[8385]=3,f[8390]=4,f[8408]=4,f[8415]=6,f[8427]=5,f[8428]=4,f[8434]=4,f[8437]=5,f[8459]=4,f[8460]=3,f[8466]=3,f[8469]=4,f[8481]=3,f[8486]=4,f[8504]=4,f[8511]=6,f[8512]=2,f[8519]=4,f[8537]=4,f[8542]=5,f[8554]=4,f[8557]=5,f[8563]=5,f[8564]=4,f[8712]=2,f[8719]=4,f[8721]=3,f[8726]=4,f[8738]=3,f[8741]=4,f[8763]=5,f[8764]=4,f[8771]=4,f[8772]=3,f[8794]=4,f[8797]=5,f[8809]=4,f[8814]=5,f[8816]=4,f[8823]=6,f[9097]=4,f[9102]=5,f[9104]=4,f[9111]=6,f[9123]=5,f[9124]=4,f[9146]=6,f[9149]=6,f[9154]=4,f[9157]=5,f[9179]=6,f[9180]=6,f[9192]=5,f[9199]=7,f[9201]=6,f[9206]=6,f[9225]=3,f[9230]=4,f[9232]=2,f[9239]=4,f[9251]=4,f[9252]=3,f[9274]=4,f[9277]=5,f[9282]=3,f[9285]=4,f[9307]=5,f[9308]=4,f[9320]=4,f[9327]=6,f[9329]=4,f[9334]=5,f[9608]=4,f[9615]=6,f[9617]=4,f[9622]=5,f[9634]=4,f[9637]=5,f[9659]=6,f[9660]=6,f[9667]=5,f[9668]=4,f[9690]=6,f[9693]=6,f[9705]=6,f[9710]=6,f[9712]=5,f[9719]=7,f[9867]=5,f[9868]=4,f[9874]=4,f[9877]=5,f[9889]=4,f[9894]=5,f[9912]=5,f[9919]=7,f[9920]=4,f[9927]=6,f[9945]=6,f[9950]=6,f[9962]=6,f[9965]=6,f[9971]=6,f[9972]=6,f[9994]=4,f[9997]=5,f[10003]=5,f[10004]=4,f[10016]=4,f[10023]=6,f[10041]=6,f[10046]=6,f[10049]=4,f[10054]=5,f[10072]=5,f[10079]=7,f[10091]=6,f[10092]=6,f[10098]=6,f[10101]=6,f[10242]=2,f[10245]=3,f[10267]=4,f[10268]=4,f[10280]=3,f[10287]=5,f[10289]=4,f[10294]=4,f[10313]=4,f[10318]=4,f[10320]=3,f[10327]=5,f[10339]=4,f[10340]=4,f[10362]=5,f[10365]=6,f[10627]=4,f[10628]=4,f[10650]=5,f[10653]=6,f[10665]=5,f[10670]=6,f[10672]=4,f[10679]=6,f[10696]=4,f[10703]=6,f[10705]=5,f[10710]=6,f[10722]=5,f[10725]=6,f[10747]=7,f[10748]=6,f[10880]=3,f[10887]=5,f[10905]=5,f[10910]=6,f[10922]=5,f[10925]=6,f[10931]=6,f[10932]=5,f[10955]=6,f[10956]=5,f[10962]=5,f[10965]=6,f[10977]=5,f[10982]=6,f[11000]=6,f[11007]=8,f[11009]=4,f[11014]=4,f[11032]=4,f[11039]=6,f[11051]=6,f[11052]=5,f[11058]=5,f[11061]=6,f[11082]=5,f[11085]=6,f[11091]=6,f[11092]=5,f[11104]=4,f[11111]=6,f[11129]=6,f[11134]=7,f[11393]=4,f[11398]=4,f[11416]=4,f[11423]=6,f[11435]=6,f[11436]=5,f[11442]=5,f[11445]=6,f[11466]=5,f[11469]=6,f[11475]=6,f[11476]=5,f[11488]=4,f[11495]=6,f[11513]=6,f[11518]=7,f[11520]=3,f[11527]=5,f[11545]=5,f[11550]=6,f[11562]=5,f[11565]=6,f[11571]=6,f[11572]=5,f[11595]=6,f[11596]=5,f[11602]=5,f[11605]=6,f[11617]=5,f[11622]=6,f[11640]=6,f[11647]=8,f[11779]=4,f[11780]=4,f[11802]=5,f[11805]=6,f[11817]=5,f[11822]=6,f[11824]=4,f[11831]=6,f[11848]=4,f[11855]=6,f[11857]=5,f[11862]=6,f[11874]=5,f[11877]=6,f[11899]=7,f[11900]=6,f[12162]=5,f[12165]=6,f[12187]=7,f[12188]=6,f[12200]=6,f[12207]=8,f[12209]=6,f[12214]=7,f[12233]=6,f[12238]=7,f[12240]=6,f[12247]=8,f[12259]=7,f[12260]=6,f[12282]=8,f[12285]=8,f[12291]=3,f[12292]=2,f[12314]=4,f[12317]=4,f[12329]=4,f[12334]=4,f[12336]=3,f[12343]=5,f[12360]=3,f[12367]=5,f[12369]=4,f[12374]=4,f[12386]=4,f[12389]=4,f[12411]=6,f[12412]=5,f[12674]=4,f[12677]=4,f[12699]=6,f[12700]=5,f[12712]=4,f[12719]=6,f[12721]=5,f[12726]=6,f[12745]=5,f[12750]=6,f[12752]=4,f[12759]=6,f[12771]=6,f[12772]=5,f[12794]=6,f[12797]=7,f[12929]=4,f[12934]=4,f[12952]=4,f[12959]=6,f[12971]=6,f[12972]=5,f[12978]=5,f[12981]=6,f[13002]=5,f[13005]=6,f[13011]=6,f[13012]=5,f[13024]=4,f[13031]=6,f[13049]=6,f[13054]=7,f[13056]=3,f[13063]=5,f[13081]=5,f[13086]=6,f[13098]=5,f[13101]=6,f[13107]=6,f[13108]=5,f[13131]=6,f[13132]=5,f[13138]=5,f[13141]=6,f[13153]=5,f[13158]=6,f[13176]=6,f[13183]=8,f[13440]=3,f[13447]=5,f[13465]=5,f[13470]=6,f[13482]=5,f[13485]=6,f[13491]=6,f[13492]=5,f[13515]=6,f[13516]=5,f[13522]=5,f[13525]=6,f[13537]=5,f[13542]=6,f[13560]=6,f[13567]=8,f[13569]=4,f[13574]=4,f[13592]=4,f[13599]=6,f[13611]=6,f[13612]=5,f[13618]=5,f[13621]=6,f[13642]=5,f[13645]=6,f[13651]=6,f[13652]=5,f[13664]=4,f[13671]=6,f[13689]=6,f[13694]=7,f[13826]=4,f[13829]=4,f[13851]=6,f[13852]=5,f[13864]=4,f[13871]=6,f[13873]=5,f[13878]=6,f[13897]=5,f[13902]=6,f[13904]=4,f[13911]=6,f[13923]=6,f[13924]=5,f[13946]=6,f[13949]=7,f[14211]=6,f[14212]=5,f[14234]=6,f[14237]=7,f[14249]=6,f[14254]=7,f[14256]=6,f[14263]=8,f[14280]=6,f[14287]=8,f[14289]=6,f[14294]=7,f[14306]=6,f[14309]=7,f[14331]=8,f[14332]=8,f[14475]=5,f[14476]=4,f[14482]=4,f[14485]=5,f[14497]=4,f[14502]=5,f[14520]=5,f[14527]=7,f[14528]=4,f[14535]=6,f[14553]=6,f[14558]=6,f[14570]=6,f[14573]=6,f[14579]=6,f[14580]=6,f[14602]=4,f[14605]=5,f[14611]=5,f[14612]=4,f[14624]=4,f[14631]=6,f[14649]=6,f[14654]=6,f[14657]=4,f[14662]=5,f[14680]=5,f[14687]=7,f[14699]=6,f[14700]=6,f[14706]=6,f[14709]=6,f[14857]=4,f[14862]=5,f[14864]=4,f[14871]=6,f[14883]=5,f[14884]=4,f[14906]=6,f[14909]=6,f[14914]=4,f[14917]=5,f[14939]=6,f[14940]=6,f[14952]=5,f[14959]=7,f[14961]=6,f[14966]=6,f[15240]=5,f[15247]=7,f[15249]=6,f[15254]=6,f[15266]=6,f[15269]=6,f[15291]=8,f[15292]=7,f[15299]=6,f[15300]=6,f[15322]=7,f[15325]=8,f[15337]=7,f[15342]=8,f[15344]=6,f[15351]=8,f[15368]=4,f[15375]=6,f[15377]=4,f[15382]=5,f[15394]=4,f[15397]=5,f[15419]=6,f[15420]=6,f[15427]=5,f[15428]=4,f[15450]=6,f[15453]=6,f[15465]=6,f[15470]=6,f[15472]=5,f[15479]=7,f[15753]=6,f[15758]=6,f[15760]=5,f[15767]=7,f[15779]=6,f[15780]=6,f[15802]=7,f[15805]=8,f[15810]=6,f[15813]=6,f[15835]=8,f[15836]=7,f[15848]=6,f[15855]=8,f[15857]=7,f[15862]=8,f[16010]=6,f[16013]=6,f[16019]=6,f[16020]=6,f[16032]=5,f[16039]=7,f[16057]=7,f[16062]=8,f[16065]=6,f[16070]=6,f[16088]=6,f[16095]=8,f[16107]=8,f[16108]=7,f[16114]=7,f[16117]=8,f[16139]=6,f[16140]=6,f[16146]=6,f[16149]=6,f[16161]=6,f[16166]=6,f[16184]=6,f[16191]=8,f[16192]=5,f[16199]=7,f[16217]=7,f[16222]=8,f[16234]=7,f[16237]=8,f[16243]=8,f[16244]=7,f[16523]=4,f[16524]=3,f[16530]=3,f[16533]=4,f[16545]=3,f[16550]=4,f[16568]=4,f[16575]=6,f[16576]=2,f[16583]=4,f[16601]=4,f[16606]=5,f[16618]=4,f[16621]=5,f[16627]=5,f[16628]=4,f[16650]=3,f[16653]=4,f[16659]=4,f[16660]=3,f[16672]=2,f[16679]=4,f[16697]=4,f[16702]=5,f[16705]=3,f[16710]=4,f[16728]=4,f[16735]=6,f[16747]=5,f[16748]=4,f[16754]=4,f[16757]=5,f[16905]=3,f[16910]=4,f[16912]=2,f[16919]=4,f[16931]=4,f[16932]=3,f[16954]=4,f[16957]=5,f[16962]=3,f[16965]=4,f[16987]=5,f[16988]=4,f[17000]=4,f[17007]=6,f[17009]=4,f[17014]=5,f[17288]=4,f[17295]=6,f[17297]=4,f[17302]=5,f[17314]=4,f[17317]=5,f[17339]=6,f[17340]=6,f[17347]=5,f[17348]=4,f[17370]=6,f[17373]=6,f[17385]=6,f[17390]=6,f[17392]=5,f[17399]=7,f[17416]=2,f[17423]=4,f[17425]=3,f[17430]=4,f[17442]=3,f[17445]=4,f[17467]=5,f[17468]=4,f[17475]=4,f[17476]=3,f[17498]=4,f[17501]=5,f[17513]=4,f[17518]=5,f[17520]=4,f[17527]=6,f[17801]=4,f[17806]=5,f[17808]=4,f[17815]=6,f[17827]=5,f[17828]=4,f[17850]=6,f[17853]=6,f[17858]=4,f[17861]=5,f[17883]=6,f[17884]=6,f[17896]=5,f[17903]=7,f[17905]=6,f[17910]=6,f[18058]=4,f[18061]=5,f[18067]=5,f[18068]=4,f[18080]=4,f[18087]=6,f[18105]=6,f[18110]=6,f[18113]=4,f[18118]=5,f[18136]=5,f[18143]=7,f[18155]=6,f[18156]=6,f[18162]=6,f[18165]=6,f[18187]=5,f[18188]=4,f[18194]=4,f[18197]=5,f[18209]=4,f[18214]=5,f[18232]=5,f[18239]=7,f[18240]=4,f[18247]=6,f[18265]=6,f[18270]=6,f[18282]=6,f[18285]=6,f[18291]=6,f[18292]=6,f[18435]=3,f[18436]=2,f[18458]=4,f[18461]=4,f[18473]=4,f[18478]=4,f[18480]=3,f[18487]=5,f[18504]=3,f[18511]=5,f[18513]=4,f[18518]=4,f[18530]=4,f[18533]=4,f[18555]=6,f[18556]=5,f[18818]=4,f[18821]=4,f[18843]=6,f[18844]=5,f[18856]=4,f[18863]=6,f[18865]=5,f[18870]=6,f[18889]=5,f[18894]=6,f[18896]=4,f[18903]=6,f[18915]=6,f[18916]=5,f[18938]=6,f[18941]=7,f[19073]=4,f[19078]=4,f[19096]=4,f[19103]=6,f[19115]=6,f[19116]=5,f[19122]=5,f[19125]=6,f[19146]=5,f[19149]=6,f[19155]=6,f[19156]=5,f[19168]=4,f[19175]=6,f[19193]=6,f[19198]=7,f[19200]=3,f[19207]=5,f[19225]=5,f[19230]=6,f[19242]=5,f[19245]=6,f[19251]=6,f[19252]=5,f[19275]=6,f[19276]=5,f[19282]=5,f[19285]=6,f[19297]=5,f[19302]=6,f[19320]=6,f[19327]=8,f[19584]=3,f[19591]=5,f[19609]=5,f[19614]=6,f[19626]=5,f[19629]=6,f[19635]=6,f[19636]=5,f[19659]=6,f[19660]=5,f[19666]=5,f[19669]=6,f[19681]=5,f[19686]=6,f[19704]=6,f[19711]=8,f[19713]=4,f[19718]=4,f[19736]=4,f[19743]=6,f[19755]=6,f[19756]=5,f[19762]=5,f[19765]=6,f[19786]=5,f[19789]=6,f[19795]=6,f[19796]=5,f[19808]=4,f[19815]=6,f[19833]=6,f[19838]=7,f[19970]=4,f[19973]=4,f[19995]=6,f[19996]=5,f[20008]=4,f[20015]=6,f[20017]=5,f[20022]=6,f[20041]=5,f[20046]=6,f[20048]=4,f[20055]=6,f[20067]=6,f[20068]=5,f[20090]=6,f[20093]=7,f[20355]=6,f[20356]=5,f[20378]=6,f[20381]=7,f[20393]=6,f[20398]=7,f[20400]=6,f[20407]=8,f[20424]=6,f[20431]=8,f[20433]=6,f[20438]=7,f[20450]=6,f[20453]=7,f[20475]=8,f[20476]=8,f[20482]=2,f[20485]=3,f[20507]=4,f[20508]=4,f[20520]=3,f[20527]=5,f[20529]=4,f[20534]=4,f[20553]=4,f[20558]=4,f[20560]=3,f[20567]=5,f[20579]=4,f[20580]=4,f[20602]=5,f[20605]=6,f[20867]=4,f[20868]=4,f[20890]=5,f[20893]=6,f[20905]=5,f[20910]=6,f[20912]=4,f[20919]=6,f[20936]=4,f[20943]=6,f[20945]=5,f[20950]=6,f[20962]=5,f[20965]=6,f[20987]=7,f[20988]=6,f[21120]=3,f[21127]=5,f[21145]=5,f[21150]=6,f[21162]=5,f[21165]=6,f[21171]=6,f[21172]=5,f[21195]=6,f[21196]=5,f[21202]=5,f[21205]=6,f[21217]=5,f[21222]=6,f[21240]=6,f[21247]=8,f[21249]=4,f[21254]=4,f[21272]=4,f[21279]=6,f[21291]=6,f[21292]=5,f[21298]=5,f[21301]=6,f[21322]=5,f[21325]=6,f[21331]=6,f[21332]=5,f[21344]=4,f[21351]=6,f[21369]=6,f[21374]=7,f[21633]=4,f[21638]=4,f[21656]=4,f[21663]=6,f[21675]=6,f[21676]=5,f[21682]=5,f[21685]=6,f[21706]=5,f[21709]=6,f[21715]=6,f[21716]=5,f[21728]=4,f[21735]=6,f[21753]=6,f[21758]=7,f[21760]=3,f[21767]=5,f[21785]=5,f[21790]=6,f[21802]=5,f[21805]=6,f[21811]=6,f[21812]=5,f[21835]=6,f[21836]=5,f[21842]=5,f[21845]=6,f[21857]=5,f[21862]=6,f[21880]=6,f[21887]=8,f[22019]=4,f[22020]=4,f[22042]=5,f[22045]=6,f[22057]=5,f[22062]=6,f[22064]=4,f[22071]=6,f[22088]=4,f[22095]=6,f[22097]=5,f[22102]=6,f[22114]=5,f[22117]=6,f[22139]=7,f[22140]=6,f[22402]=5,f[22405]=6,f[22427]=7,f[22428]=6,f[22440]=6,f[22447]=8,f[22449]=6,f[22454]=7,f[22473]=6,f[22478]=7,f[22480]=6,f[22487]=8,f[22499]=7,f[22500]=6,f[22522]=8,f[22525]=8,f[22666]=4,f[22669]=5,f[22675]=5,f[22676]=4,f[22688]=4,f[22695]=6,f[22713]=6,f[22718]=6,f[22721]=4,f[22726]=5,f[22744]=5,f[22751]=7,f[22763]=6,f[22764]=6,f[22770]=6,f[22773]=6,f[22795]=5,f[22796]=4,f[22802]=4,f[22805]=5,f[22817]=4,f[22822]=5,f[22840]=5,f[22847]=7,f[22848]=4,f[22855]=6,f[22873]=6,f[22878]=6,f[22890]=6,f[22893]=6,f[22899]=6,f[22900]=6,f[23048]=4,f[23055]=6,f[23057]=4,f[23062]=5,f[23074]=4,f[23077]=5,f[23099]=6,f[23100]=6,f[23107]=5,f[23108]=4,f[23130]=6,f[23133]=6,f[23145]=6,f[23150]=6,f[23152]=5,f[23159]=7,f[23433]=6,f[23438]=6,f[23440]=5,f[23447]=7,f[23459]=6,f[23460]=6,f[23482]=7,f[23485]=8,f[23490]=6,f[23493]=6,f[23515]=8,f[23516]=7,f[23528]=6,f[23535]=8,f[23537]=7,f[23542]=8,f[23561]=4,f[23566]=5,f[23568]=4,f[23575]=6,f[23587]=5,f[23588]=4,f[23610]=6,f[23613]=6,f[23618]=4,f[23621]=5,f[23643]=6,f[23644]=6,f[23656]=5,f[23663]=7,f[23665]=6,f[23670]=6,f[23944]=5,f[23951]=7,f[23953]=6,f[23958]=6,f[23970]=6,f[23973]=6,f[23995]=8,f[23996]=7,f[24003]=6,f[24004]=6,f[24026]=7,f[24029]=8,f[24041]=7,f[24046]=8,f[24048]=6,f[24055]=8,f[24203]=6,f[24204]=6,f[24210]=6,f[24213]=6,f[24225]=6,f[24230]=6,f[24248]=6,f[24255]=8,f[24256]=5,f[24263]=7,f[24281]=7,f[24286]=8,f[24298]=7,f[24301]=8,f[24307]=8,f[24308]=7,f[24330]=6,f[24333]=6,f[24339]=6,f[24340]=6,f[24352]=5,f[24359]=7,f[24377]=7,f[24382]=8,f[24385]=6,f[24390]=6,f[24408]=6,f[24415]=8,f[24427]=8,f[24428]=7,f[24434]=7,f[24437]=8,f[24577]=2,f[24582]=3,f[24600]=3,f[24607]=5,f[24619]=4,f[24620]=4,f[24626]=4,f[24629]=4,f[24650]=4,f[24653]=4,f[24659]=4,f[24660]=4,f[24672]=3,f[24679]=5,f[24697]=5,f[24702]=6,f[24960]=3,f[24967]=5,f[24985]=5,f[24990]=6,f[25002]=5,f[25005]=6,f[25011]=6,f[25012]=5,f[25035]=6,f[25036]=5,f[25042]=5,f[25045]=6,f[25057]=5,f[25062]=6,f[25080]=6,f[25087]=8,f[25219]=4,f[25220]=4,f[25242]=5,f[25245]=6,f[25257]=5,f[25262]=6,f[25264]=4,f[25271]=6,f[25288]=4,f[25295]=6,f[25297]=5,f[25302]=6,f[25314]=5,f[25317]=6,f[25339]=7,f[25340]=6,f[25346]=4,f[25349]=4,f[25371]=6,f[25372]=5,f[25384]=4,f[25391]=6,f[25393]=5,f[25398]=6,f[25417]=5,f[25422]=6,f[25424]=4,f[25431]=6,f[25443]=6,f[25444]=5,f[25466]=6,f[25469]=7,f[25730]=4,f[25733]=4,f[25755]=6,f[25756]=5,f[25768]=4,f[25775]=6,f[25777]=5,f[25782]=6,f[25801]=5,f[25806]=6,f[25808]=4,f[25815]=6,f[25827]=6,f[25828]=5,f[25850]=6,f[25853]=7,f[25859]=4,f[25860]=4,f[25882]=5,f[25885]=6,f[25897]=5,f[25902]=6,f[25904]=4,f[25911]=6,f[25928]=4,f[25935]=6,f[25937]=5,f[25942]=6,f[25954]=5,f[25957]=6,f[25979]=7,f[25980]=6,f[26112]=3,f[26119]=5,f[26137]=5,f[26142]=6,f[26154]=5,f[26157]=6,f[26163]=6,f[26164]=5,f[26187]=6,f[26188]=5,f[26194]=5,f[26197]=6,f[26209]=5,f[26214]=6,f[26232]=6,f[26239]=8,f[26497]=5,f[26502]=6,f[26520]=6,f[26527]=8,f[26539]=7,f[26540]=6,f[26546]=6,f[26549]=7,f[26570]=6,f[26573]=7,f[26579]=7,f[26580]=6,f[26592]=6,f[26599]=8,f[26617]=8,f[26622]=8,f[26761]=4,f[26766]=5,f[26768]=4,f[26775]=6,f[26787]=5,f[26788]=4,f[26810]=6,f[26813]=6,f[26818]=4,f[26821]=5,f[26843]=6,f[26844]=6,f[26856]=5,f[26863]=7,f[26865]=6,f[26870]=6,f[26888]=4,f[26895]=6,f[26897]=4,f[26902]=5,f[26914]=4,f[26917]=5,f[26939]=6,f[26940]=6,f[26947]=5,f[26948]=4,f[26970]=6,f[26973]=6,f[26985]=6,f[26990]=6,f[26992]=5,f[26999]=7,f[27147]=5,f[27148]=4,f[27154]=4,f[27157]=5,f[27169]=4,f[27174]=5,f[27192]=5,f[27199]=7,f[27200]=4,f[27207]=6,f[27225]=6,f[27230]=6,f[27242]=6,f[27245]=6,f[27251]=6,f[27252]=6,f[27530]=6,f[27533]=6,f[27539]=6,f[27540]=6,f[27552]=5,f[27559]=7,f[27577]=7,f[27582]=8,f[27585]=6,f[27590]=6,f[27608]=6,f[27615]=8,f[27627]=8,f[27628]=7,f[27634]=7,f[27637]=8,f[27658]=4,f[27661]=5,f[27667]=5,f[27668]=4,f[27680]=4,f[27687]=6,f[27705]=6,f[27710]=6,f[27713]=4,f[27718]=5,f[27736]=5,f[27743]=7,f[27755]=6,f[27756]=6,f[27762]=6,f[27765]=6,f[28043]=6,f[28044]=6,f[28050]=6,f[28053]=6,f[28065]=6,f[28070]=6,f[28088]=6,f[28095]=8,f[28096]=5,f[28103]=7,f[28121]=7,f[28126]=8,f[28138]=7,f[28141]=8,f[28147]=8,f[28148]=7,f[28296]=5,f[28303]=7,f[28305]=6,f[28310]=6,f[28322]=6,f[28325]=6,f[28347]=8,f[28348]=7,f[28355]=6,f[28356]=6,f[28378]=7,f[28381]=8,f[28393]=7,f[28398]=8,f[28400]=6,f[28407]=8,f[28425]=6,f[28430]=6,f[28432]=5,f[28439]=7,f[28451]=6,f[28452]=6,f[28474]=7,f[28477]=8,f[28482]=6,f[28485]=6,f[28507]=8,f[28508]=7,f[28520]=6,f[28527]=8,f[28529]=7,f[28534]=8,f[28808]=4,f[28815]=6,f[28817]=4,f[28822]=5,f[28834]=4,f[28837]=5,f[28859]=6,f[28860]=6,f[28867]=5,f[28868]=4,f[28890]=6,f[28893]=6,f[28905]=6,f[28910]=6,f[28912]=5,f[28919]=7,f[28937]=4,f[28942]=5,f[28944]=4,f[28951]=6,f[28963]=5,f[28964]=4,f[28986]=6,f[28989]=6,f[28994]=4,f[28997]=5,f[29019]=6,f[29020]=6,f[29032]=5,f[29039]=7,f[29041]=6,f[29046]=6,f[29194]=4,f[29197]=5,f[29203]=5,f[29204]=4,f[29216]=4,f[29223]=6,f[29241]=6,f[29246]=6,f[29249]=4,f[29254]=5,f[29272]=5,f[29279]=7,f[29291]=6,f[29292]=6,f[29298]=6,f[29301]=6,f[29579]=6,f[29580]=6,f[29586]=6,f[29589]=6,f[29601]=6,f[29606]=6,f[29624]=6,f[29631]=8,f[29632]=5,f[29639]=7,f[29657]=7,f[29662]=8,f[29674]=7,f[29677]=8,f[29683]=8,f[29684]=7,f[29707]=5,f[29708]=4,f[29714]=4,f[29717]=5,f[29729]=4,f[29734]=5,f[29752]=5,f[29759]=7,f[29760]=4,f[29767]=6,f[29785]=6,f[29790]=6,f[29802]=6,f[29805]=6,f[29811]=6,f[29812]=6,f[30090]=6,f[30093]=6,f[30099]=6,f[30100]=6,f[30112]=5,f[30119]=7,f[30137]=7,f[30142]=8,f[30145]=6,f[30150]=6,f[30168]=6,f[30175]=8,f[30187]=8,f[30188]=7,f[30194]=7,f[30197]=8,f[30345]=6,f[30350]=6,f[30352]=5,f[30359]=7,f[30371]=6,f[30372]=6,f[30394]=7,f[30397]=8,f[30402]=6,f[30405]=6,f[30427]=8,f[30428]=7,f[30440]=6,f[30447]=8,f[30449]=7,f[30454]=8,f[30472]=5,f[30479]=7,f[30481]=6,f[30486]=6,f[30498]=6,f[30501]=6,f[30523]=8,f[30524]=7,f[30531]=6,f[30532]=6,f[30554]=7,f[30557]=8,f[30569]=7,f[30574]=8,f[30576]=6,f[30583]=8,f[30720]=3,f[30727]=5,f[30745]=5,f[30750]=6,f[30762]=5,f[30765]=6,f[30771]=6,f[30772]=5,f[30795]=6,f[30796]=5,f[30802]=5,f[30805]=6,f[30817]=5,f[30822]=6,f[30840]=6,f[30847]=8,f[31105]=5,f[31110]=6,f[31128]=6,f[31135]=8,f[31147]=7,f[31148]=6,f[31154]=6,f[31157]=7,f[31178]=6,f[31181]=7,f[31187]=7,f[31188]=6,f[31200]=6,f[31207]=8,f[31225]=8,f[31230]=8,f[31362]=5,f[31365]=6,f[31387]=7,f[31388]=6,f[31400]=6,f[31407]=8,f[31409]=6,f[31414]=7,f[31433]=6,f[31438]=7,f[31440]=6,f[31447]=8,f[31459]=7,f[31460]=6,f[31482]=8,f[31485]=8,f[31491]=6,f[31492]=5,f[31514]=6,f[31517]=7,f[31529]=6,f[31534]=7,f[31536]=6,f[31543]=8,f[31560]=6,f[31567]=8,f[31569]=6,f[31574]=7,f[31586]=6,f[31589]=7,f[31611]=8,f[31612]=8,f[31875]=6,f[31876]=5,f[31898]=6,f[31901]=7,f[31913]=6,f[31918]=7,f[31920]=6,f[31927]=8,f[31944]=6,f[31951]=8,f[31953]=6,f[31958]=7,f[31970]=6,f[31973]=7,f[31995]=8,f[31996]=8,f[32002]=5,f[32005]=6,f[32027]=7,f[32028]=6,f[32040]=6,f[32047]=8,f[32049]=6,f[32054]=7,f[32073]=6,f[32078]=7,f[32080]=6,f[32087]=8,f[32099]=7,f[32100]=6,f[32122]=8,f[32125]=8,f[32257]=5,f[32262]=6,f[32280]=6,f[32287]=8,f[32299]=7,f[32300]=6,f[32306]=6,f[32309]=7,f[32330]=6,f[32333]=7,f[32339]=7,f[32340]=6,f[32352]=6,f[32359]=8,f[32377]=8,f[32382]=8,f[32640]=6,f[32647]=8,f[32665]=8,f[32670]=8,f[32682]=8,f[32685]=8,f[32691]=8,f[32692]=8,f[32715]=8,f[32716]=8,f[32722]=8,f[32725]=8,f[32737]=8,f[32742]=8,f[32760]=8,f[32767]=10;
	scanf("%d",&n);
	for(int i=1,x,y,z;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);++x,++y;
		a[x]^=z;a[y]^=z;
	}
	for(int i=1;i<=n;i++)
		if(a[i])
		{
			if((m>>a[i]-1)&1)ans++;
			m^=(1<<a[i]-1);
		}
	printf("%d",ans+f[m]);
	return 0;
}


Measured memory_bytes: 640