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