http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1242
题意：
求1~n的区间内，有几个数的因子是2,3,5,7,11,13 ，且个数为偶数
思路：
打表，分开20W作为一个区间，求出边界值，然后每次枚举区间即可
之前好像是代码长度过长，打了2遍表，导致编译不过，删掉就好了！
#include<bits/stdc++.h>
using namespace std;
int a[5005]={0,105946,211914,317854,423808,529768,635741,741665,847626,953566,1059525,1165456,1271374,1377373,1483346,1589303,1695194,1801183,1907098,2013069,2119020,2225036,2330992,2436892,2542875,2648807,2754788,2860705,2966642,3072646,3178504,3284550,3390493,3496471,3602393,3708331,3814333,3920183,4026213,4132171,4238085,4344022,4449918,4555977,4661846,4767857,4873848,4979706,5085728,5191666,5297603,5403610,5509494,5615527,5721484,5827422,5933335,6039296,6145231,6251179,6357233,6463167,6569024,6674954,6780975,6886903,6992765,7098833,7204784,7310732,7416638,7522678,7628575,7734486,7840482,7946407,8052403,8158363,8264212,8370261,8476244,8582182,8688139,8794053,8900106,9005974,9111914,9217817,9323857,9429798,9535780,9641673,9747558,9853551,9959582,10065536,10171441,10277358,10383329,10489256,10595272,10701158,10807098,10913041,11019045,11124957,11230951,11336910,11442810,11548792,11654687,11760776,11866702,11972691,12078584,12184486,12290428,12396375,12502421,12608337,12714257,12820241,12926086,13032131,13138084,13244036,13350119,13455977,13561909,13667868,13773789,13879812,13985851,14091715,14197691,14303599,14409496,14515475,14621382,14727391,14833404,14939294,15045222,15151213,15257110,15363107,15469036,15574972,15680968,15786991,15892936,15998777,16104753,16210698,16316601,16422620,16528675,16634574,16740491,16846414,16952350,17058298,17164219,17270253,17376122,17482064,17588111,17694093,17799946,17905940,18011869,18117812,18223756,18329729,18435723,18541664,18647598,18753619,18859508,18965429,19071352,19177370,19283292,19389211,19495329,19601288,19707194,19813155,19919016,20025013,20130909,20236866,20342807,20448786,20554767,20660670,20766676,20872633,20978670,21084590,21190493,21296428,21402400,21508331,21614274,21720298,21826253,21932173,22038159,22144091,22250116,22356055,22461912,22567813,22673826,22779750,22885726,22991655,23097623,23203667,23309638,23415506,23521440,23627413,23733340,23839260,23945197,24051103,24157082,24263146,24369075,24474951,24581011,24686921,24792984,24898868,25004747,25110703,25216653,25322610,25428556,25534492,25640414,25746415,25852476,25958340,26064312,26170242,26276234,26382167,26488138,26594016,26699884,26805938,26911881,27017813,27123768,27229734,27335690,27441732,27547661,27653568,27759517,27865417,27971347,28077332,28183299,28289228,28395126,28501051,28607056,28713088,28819052,28924950,29030921,29136831,29242965,29348931,29454819,29560740,29666637,29772560,29878592,29984463,30090477,30196371,30302297,30408305,30514292,30620264,30726187,30832220,30938130,31044013,31150065,31255987,31361934,31467887,31573727,31679735,31785640,31891626,31997582,32103555,32209522,32315377,32421485,32527440,32633421,32739316,32845277,32951182,33057112,33163099,33269041,33375010,33480966,33586863,33692833,33798788,33904736,34010738,34116665,34222625,34328637,34434555,34540472,34646499,34752523,34858460,34964445,35070318,35176225,35282143,35388073,35494062,35600033,35705933,35811888,35917773,36023811,36129756,36235738,36341724,36447693,36553635,36659578,36765477,36871499,36977437,37083381,37189363,37295304,37401106,37507091,37613036,37719023,37824978,37930957,38036848,38142865,38248774,38354781,38460690,38566714,38672661,38778681,38884576,38990405,39096448,39202347,39308261,39414295,39520277,39626108,39732173,39838146,39944043,40049910,40155896,40261886,40367872,40473820,40579852,40685763,40791635,40897665,41003592,41109578,41215471,41321539,41427484,41533368,41639303,41745256,41851127,41957035,42063066,42168960,42274966,42380873,42486801,42592763,42698712,42804722,42910676,43016663,43122639,43228597,43334529,43440408,43546430,43652375,43758294,43864310,43970250,44076193,44182108,44288055,44394000,44499852,44605915,44711795,44817795,44923730,45029721,45135704,45241605,45347576,45453523,45559520,45665459,45771459,45877458,45983376,46089300,46195296,46301152,46407121,46513051,46618964,46725056,46830945,46936859,47042832,47148811,47254678,47360640,47466582,47572610,47678541,47784532,47890472,47996493,48102480,48208346,48314360,48420321,48526172,48632173,48738133,48844050,48950124,49055923,49161932,49267886,49373784,49479696,49585591,49691581,49797559,49903527,50009525,50115401,50221395,50327322,50433303,50539261,50645240,50751175,50857163,50963207,51069091,51174992,51281046,51386922,51492887,51598829,51704734,51810687,51916698,52022655,52128595,52234624,52340487,52446484,52552326,52658267,52764239,52870192,52976139,53082058,53188106,53294045,53400052,53506008,53611884,53717847,53823825,53929772,54035786,54141674,54247707,54353688,54459616,54565583,54671518,54777483,54883353,54989336,55095262,55201277,55307217,55413118,55519068,55625054,55731058,55836935,55942909,56048789,56154735,56260687,56366660,56472622,56578601,56684561,56790546,56896516,57002516,57108352,57214409,57320328,57426198,57532145,57638128,57744099,57850121,57956024,58062024,58167974,58273926,58379709,58485602,58591617,58697493,58803483,58909481,59015347,59121369,59227349,59333311,59439177,59545242,59651194,59757097,59863047,59969062,60074976,60180917,60286914,60392903,60498889,60604863,60710742,60816678,60922697,61028608,61134545,61240498,61346465,61452469,61558349,61664225,61770251,61876163,61982202,62088139,62194042,62299934,62405913,62511824,62617829,62723727,62829725,62935615,63041643,63147629,63253549,63359478,63465495,63571454,63677346,63783343,63889315,63995275,64101181,64207196,64313079,64419062,64525086,64631119,64737034,64842870,64948854,65054727,65160714,65266619,65372664,65478553,65584491,65690490,65796462,65902432,66008332,66114265,66220248,66326133,66432127,66538043,66643975,66749902,66855813,66961822,67067756,67173803,67279748,67385734,67491638,67597626,67703632,67809545,67915441,68021388,68127377,68233365,68339270,68445271,68551225,68657139,68763152,68869061,68975000,69080969,69186848,69292820,69398665,69504608,69610545,69716529,69822497,69928376,70034438,70140343,70246329,70352271,70458290,70564200,70670091,70776141,70882093,70987980,71093911,71199931,71305970,71411912,71517851,71623824,71729783,71835758,71941698,72047652,72153632,72259531,72365483,72471467,72577403,72683298,72789208,72895205,73001111,73107115,73213059,73318988,73425056,73530988,73636848,73742785,73848784,73954697,74060673,74166576,74272489,74378420,74484437,74590348,74696421,74802406,74908308,75014334,75120223,75226201,75332185,75438100,75544037,75650047,75755920,75861895,75967859,76073874,76179815,76285767,76391699,76497751,76603632,76709582,76815479,76921552,77027393,77133347,77239346,77345273,77451147,77557068,77663005,77769025,77875024,77981000,78086857,78192847,78298851,78404775,78510726,78616676,78722555,78828508,78934509,79040381,79146365,79252396,79358281,79464207,79570233,79676077,79782208,79888051,79994105,80100091,80206038,80311941,80417834,80523812,80629740,80735695,80841660,80947671,81053627,81159496,81265514,81371445,81477414,81583422,81689297,81795222,81901175,82007141,82113060,82218987,82324911,82430962,82536827,82642726,82748723,82854624,82960632,83066597,83172584,83278500,83384525,83490382,83596465,83702404,83808275,83914317,84020246,84126160,84232160,84338174,84444071,84550004,84655988,84761963,84867932,84973910,85079877,85185848,85291795,85397725,85503722,85609593,85715579,85821531,85927485,86033421,86139281,86245284,86351143,86457155,86563077,86669096,86775102,86881070,86986984,87092902,87198833,87304736,87410816,87516675,87622636,87728481,87834492,87940416,88046347,88152266,88258281,88364244,88470183,88576144,88682144,88788056,88894123,89000090,89106056,89211898,89317973,89423881,89529847,89635767,89741679,89847718,89953707,90059595,90165527,90271477,90377476,90483457,90589408,90695355,90801268,90907294,91013204,91119096,91225108,91331052,91436950,91542899,91648862,91754703,91860747,91966698,92072581,92178575,92284459,92390425,92496356,92602421,92708324,92814285,92920282,93026181,93132204,93238137,93343902,93449886,93555892,93661849,93767796,93873763,93979693,94085677,94191620,94297606,94403537,94509593,94615565,94721508,94827464,94933412,95039303,95145247,95251250,95357182,95463135,95569027,95675039,95780980,95886920,95992885,96098765,96204728,96310746,96416703,96522621,96628535,96734612,96840445,96946533,97052422,97158287,97264213,97370171,97476106,97582073,97688065,97793927,97899835,98005855,98111862,98217784,98323704,98429651,98535630,98641622,98747584,98853541,98959501,99065422,99171456,99277439,99383303,99489273,99595250,99701188,99807140,99913125,100018992,100125026,100230988,100336864,100442850,100548897,100654821,100760848,100866720,100972725,101078619,101184502,101290516,101396497,101502457,101608399,101714331,101820301,101926140,102032132,102138108,102244049,102350072,102456011,102561842,102667906,102773821,102879700,102985703,103091615,103197571,103303600,103409547,103515435,103621459,103727325,103833270,103939227,104045161,104151087,104257041,104363042,104468849,104574928,104680858,104786842,104892707,104998764,105104777,105210663,105316658,105422543,105528564,105634556,105740502,105846472,105952392,106058318,106164353,106270325,106376147,106482168,106588089,106694005,106799981,106905919,107011894,107117907,107223903,107329778,107435782,107541664,107647663,107753698,107859592,107965517,108071443,108177486,108283393,108389275,108495181,108601076,108707075,108813044,108918984,109024956,109130821,109236763,109342769,109448706,109554657,109660630,109766602,109872550,109978499,110084504,110190393,110296365,110402240,110508234,110614107,110720157,110826064,110932021,111038014,111143899,111249869,111355855,111461733,111567716,111673701,111779615,111885622,111991615,112097622,112203619,112309565,112415375,112521441,112627357,112733313,112839319,112945219,113051180,113157144,113263058,113369031,113474991,113580932,113686799,113792816,113898796,114004678,114110749,114216676,114322555,114428517,114534444,114640465,114746439,114852378,114958327,115064247,115170178,115276128,115382182,115488058,115593919,115699858,115805837,115911820,116017717,116123665,116229611,116335560,116441543,116547462,116653468,116759531,116865380,116971502,117077355,117183329,117289266,117395298,117501203,117607154,117713182,117819036,117925048,118031063,118136922,118242844,118348830,118454736,118560671,118666661,118772643,118878705,118984565,119090472,119196455,119302400,119408328,119514293,119620278,119726254,119832193,119938143,120044145,120150095,120256044,120361977,120467927,120573887,120679735,120785756,120891659,120997599,121103565,121209455,121315487,121421449,121527364,121633362,121739227,121845204,121951101,122057107,122163046,122269035,122375058,122480959,122586835,122692816,122798773,122904657,123010706,123116618,123222553,123328581,123434507,123540383,123646465,123752339,123858171,123964145,124070173,124176098,124282006,124388028,124494041,124600001,124705939,124811864,124917836,125023882,125129833,125235670,125341710,125447675,125553662,125659550,125765536,125871520,125977374,126083397,126189278,126295249,126401202,126507187,126613154,126719142,126825027,126931001,127036902,127142913,127248932,127354915,127460818,127566736,127672733,127778669,127884633,127990535,128096508,128202477,128308399,128414274,128520203,128626270,128732144,128838116,128944036,129049934,129155884,129261781,129367806,129473690,129579644,129685692,129791622,129897572,130003510,130109559,130215421,130321409,130427357,130533346,130639225,130745145,130851124,130957075,131063066,131168997,131274990,131380904,131486860,131592765,131698784,131804635,131910684,132016615,132122558,132228510,132334487,132440418,132546411,132652417,132758388,132864277,132970303,133076220,133182158,133288177,133394231,133500129,133606096,133712085,133817922,133923923,134029818,134135817,134241750,134347692,134453603,134559567,134665455,134771491,134877531,134983399,135089331,135195323,135301173,135407162,135513145,135619067,135725062,135831014,135936962,136042924,136148843,136254748,136360779,136466649,136572705,136678597,136784623,136890470,136996411,137102343,137208257,137314231,137420214,137526074,137632032,137738042,137843945,137949944,138055951,138161855,138267867,138373811,138479629,138585671,138691653,138797685,138903654,139009580,139115542,139221504,139327503,139433418,139539353,139645295,139751277,139857268,139963193,140069063,140174999,140281030,140386953,140492925,140598920,140704817,140810855,140916715,141022644,141128655,141234585,141340625,141446461,141552438,141658389,141764368,141870354,141976374,142082276,142188314,142294145,142400151,142506129,142611937,142717874,142823882,142929865,143035778,143141716,143247652,143353626,143459575,143565482,143671459,143777427,143883328,143989245,144095240,144201177,144307097,144413047,144519090,144625059,144730952,144836957,144942819,145048816,145154750,145260634,145366694,145472613,145578602,145684600,145790472,145896404,146002380,146108381,146214222,146320225,146426171,146532104,146638090,146743941,146849847,146955913,147061746,147167846,147273777,147379665,147485674,147591605,147697562,147803554,147909532,148015418,148121456,148227501,148333376,148439355,148545303,148651274,148757268,148863230,148969155,149075073,149181070,149286939,149392848,149498814,149604732,149710701,149816720,149922682,150028522,150134508,150240518,150346489,150452418,150558379,150664310,150770319,150876280,150982224,151088191,151194141,151300029,151406035,151512011,151617866,151723863,151829732,151935739,152041646,152147574,152253578,152359501,152465476,152571387,152677380,152783300,152889154,152995088,153101122,153207099,153313026,153418987,153524964,153630933,153736795,153842682,153948713,154054689,154160612,154266579,154372532,154478472,154584409,154690369,154796346,154902345,155008304,155114288,155220231,155326201,155432099,155538026,155643909,155749907,155855886,155961771,156067808,156173744,156279656,156385655,156491553,156597525,156703436,156809452,156915436,157021374,157127412,157233322,157339205,157445249,157551188,157657197,157763152,157869064,157975117,158081017,158186964,158292922,158398857,158504767,158610735,158716732,158822756,158928649,159034543,159140540,159246505,159352525,159458405,159564255,159670254,159776308,159882166,159988143,160094030,160199974,160305880,160411890,160517813,160623797,160729685,160835787,160941715,161047610,161153641,161259570,161365530,161471463,161577504,161683392,161789313,161895186,162001180,162107050,162213050,162319053,162424959,162530882,162636781,162742799,162848743,162954643,163060583,163166515,163272488,163378482,163484499,163590391,163696343,163802307,163908247,164014234,164120097,164226135,164332123,164438049,164544044,164650009,164755959,164861779,164967820,165073802,165179831,165285736,165391640,165497594,165603544,165709557,165815456,165921410,166027381,166133332,166239299,166345223,166451213,166557200,166663072,166769018,166875024,166980996,167086840,167192735,167298739,167404700,167510715,167616693,167722642,167828569,167934566,168040500,168146507,168252473,168358400,168464350,168570211,168676160,168782184,168888127,168994018,169100067,169205975,169311981,169417894,169523833,169629696,169735684,169841560,169947593,170053551,170159495,170265375,170371355,170477210,170583237,170689164,170795200,170901049,171007008,171113027,171218974,171325002,171430869,171536760,171642728,171748683,171854645,171960652,172066547,172172570,172278581,172384527,172490397,172596454,172702401,172808321,172914229,173020180,173126144,173232045,173337962,173443881,173549800,173655828,173761673,173867655,173973669,174079625,174185540,174291562,174397495,174503441,174609434,174715329,174821238,174927278,175033298,175139333,175245170,175351090,175457224,175563111,175669042,175775056,175880962,175986881,176092918,176198887,176304856,176410740,176516726,176622558,176728568,176834552,176940513,177046490,177152456,177258369,177364311,177470239,177576238,177682136,177788049,177893969,177999959,178105952,178211863,178317921,178423870,178529798,178635661,178741641,178847641,178953529,179059500,179165442,179271413,179377395,179483382,179589328,179695191,179801123,179907058,180013198,180119010,180224989,180330966,180436893,180542852,180648767,180754668,180860609,180966560,181072491,181178465,181284399,181390347,181496321,181602305,181708195,181814096,181920082,182026029,182131987,182237996,182343834,182449888,182555826,182661762,182767733,182873729,182979655,183085599,183191578,183297513,183403503,183509520,183615415,183721325,183827385,183933233,184039196,184145215,184251105,184357041,184463061,184568985,184674926,184780904,184886856,184992875,185098728,185204667,185310619,185416622,185522609,185628551,185734434,185840402,185946324,186052351,186158240,186264207,186370181,186476110,186582151,186688233,186794158,186900099,187006068,187111969,187217989,187323875,187429834,187535806,187641686,187747654,187853605,187959595,188065556,188171511,188277467,188383411,188489327,188595336,188701248,188807245,188913140,189019004,189125057,189230881,189336882,189442850,189548811,189654758,189760731,189866650,189972562,190078635,190184569,190290500,190396455,190502388,190608334,190714303,190820237,190926218,191032155,191138177,191244106,191349987,191455963,191561884,191667832,191773779,191879780,191985662,192091636,192197634,192303630,192409536,192515449,192621347,192727252,192833260,192939284,193045212,193151174,193257171,193363026,193468924,193574940,193680907,193786793,193892685,193998676,194104648,194210635,194316646,194422529,194528576,194634518,194740447,194846323,194952430,195058342,195164314,195270227,195376142,195482128,195588141,195694087,195800087,195906066,196011927,196117863,196223793,196329797,196435763,196541753,196647701,196753634,196859616,196965469,197071441,197177407,197283348,197389249,197495257,197601148,197707093,197813163,197919074,198024977,198131049,198236930,198342870,198448853,198554735,198660669,198766747,198872712,198978650,199084641,199190479,199296462,199402458,199508450,199614356,199720216,199826258,199932234,200038258,200144208,200250076,200356086,200461939,200568019,200673926,200779851,200885831,200991734,201097636,201203626,201309546,201415467,201521373,201627391,201733332,201839284,201945125,202051143,202157113,202263103,202369106,202475048,202580955,202686855,202792830,202898695,203004672,203110616,203216651,203322615,203428531,203534529,203640406,203746424,203852411,203958384,204064316,204170225,204276140,204382100,204488063,204594053,204699863,204805899,204911823,205017835,205123819,205229726,205335597,205441506,205547514,205653446,205759501,205865385,205971356,206077413,206183296,206289154,206395178,206501059,206607023,206713029,206818961,206924953,207030939,207136763,207242784,207348840,207454768,207560767,207666680,207772619,207878557,207984556,208090506,208196511,208302418,208408455,208514372,208620354,208726203,208832280,208938262,209044159,209150042,209256047,209362004,209467914,209573897,209679863,209785875,209891837,209997702,210103686,210209567,210315549,210421511,210527447,210633375,210739374,210845349,210951233,211057218,211163179,211269086,211375030,211481004,211586936,211692923,211798912,211904833,212010858,212116771,212222706,212328594,212434581,212540439,212646452,212752520,212858404,212964363,213070338,213176267,213282264,213388234,213494151,213600057,213706032,213811951,213917828,214023818,214129739,214235659,214341701,214447499,214553577,214659573,214765463,214871339,214977372,215083325,215189181,215295176,215401036,215507039,215613016,215718956,215824876,215930868,216036762,216142793,216248708,216354584,216460633,216566568,216672539,216778542,216884544,216990478,217096418,217202458,217308400,217414270,217520275,217626159,217732115,217838084,217944000,218049998,218155988,218261934,218367893,218473865,218579845,218685718,218791713,218897648,219003622,219109596,219215537,219321453,219427416,219533354,219639333,219745253,219851239,219957174,220063122,220169006,220274966,220380952,220486950,220592858,220698899,220804865,220910793,221016745,221122720,221228752,221334650,221440548,221546484,221652535,221758407,221864397,221970336,222076261,222182235,222288280,222394189,222500158,222606084,222712069,222818048,222924024,223029936,223135906,223241835,223347791,223453686,223559699,223665623,223771587,223877581,223983506,224089354,224195279,224301255,224407152,224513155,224619111,224725109,224831116,224936938,225042848,225148890,225254843,225360805,225466742,225572624,225678611,225784598,225890545,225996472,226102436,226208448,226314302,226420345,226526240,226632190,226738122,226844027,226949955,227055952,227161930,227267946,227373925,227479782,227585756,227691619,227797619,227903606,228009577,228115458,228221380,228327357,228433317,228539220,228645269,228751181,228857123,228963141,229069045,229174983,229280900,229386826,229492769,229598835,229704669,229810635,229916594,230022569,230128541,230234474,230340448,230446426,230552382,230658276,230764128,230870141,230976145,231082102,231188156,231294126,231400039,231506009,231611915,231717882,231823777,231929719,232035746,232141686,232247702,232353657,232459593,232565502,232671523,232777418,232883397,232989440,233095352,233201250,233307188,233413086,233518991,233625025,233730993,233836945,233942787,234048784,234154753,234260781,234366646,234472569,234578576,234684548,234790444,234896412,235002405,235108360,235214293,235320264,235426132,235532185,235638153,235744026,235850014,235955928,236061829,236167917,236273881,236379820,236485806,236591752,236697691,236803589,236909622,237015594,237121556,237227525,237333459,237439389,237545336,237651225,237757112,237863092,237969112,238075043,238181071,238286974,238392891,238498789,238604778,238710720,238816730,238922570,239028631,239134556,239240467,239346341,239452351,239558345,239664296,239770194,239876175,239982067,240088005,240193914,240299911,240405756,240511783,240617758,240723764,240829773,240935657,241041618,241147548,241253561,241359539,241465428,241571385,241677397,241783319,241889243,241995218,242101120,242207119,242313152,242419043,242524973,242630881,242736802,242842748,242948717,243054687,243160629,243266537,243372527,243478536,243584526,243690388,243796325,243902358,244008263,244114226,244220211,244326163,244432079,244538002,244643887,244749839,244855782,244961828,245067792,245173842,245279826,245385676,245491594,245597586,245703544,245809537,245915345,246021381,246127307,246233311,246339281,246445264,246551239,246657112,246763142,246869064,246975065,247081026,247186900,247292772,247398867,247504760,247610731,247716829,247822675,247928708,248034612,248140556,248246550,248352457,248458382,248564433,248670342,248776260,248882236,248988104,249094054,249200020,249305970,249411948,249517860,249623911,249729805,249835788,249941685,250047594,250153585,250259534,250365495,250471549,250577481,250683328,250789243,250895231,251001219,251107104,251213095,251319089,251425093,251530965,251636900,251742834,251848826,251954844,252060723,252166649,252272596,252378637,252484581,252590459,252696429,252802358,252908313,253014228,253120182,253226146,253332162,253437993,253544033,253650003,253755902,253861881,253967793,254073843,254179767,254285641,254391542,254497474,254603504,254709359,254815313,254921301,255027216,255133253,255239106,255345093,255451002,255556990,255662963,255768881,255874894,255980816,256086809,256192735,256298682,256404595,256510549,256616576,256722557,256828536,256934486,257040395,257146285,257252200,257358271,257464222,257570111,257676088,257782053,257888034,257993983,258099963,258205971,258311873,258417858,258523818,258629739,258735683,258841599,258947670,259053593,259159532,259265394,259371382,259477344,259583311,259689306,259795213,259901168,260007120,260113015,260218936,260324927,260430879,260536906,260642796,260748743,260854719,260960650,261066588,261172543,261278552,261384545,261490542,261596490,261702402,261808430,261914372,262020233,262126214,262232116,262338139,262444057,262550009,262655992,262761953,262867860,262973848,263079780,263185837,263291766,263397637,263503624,263609650,263715590,263821510,263927530,264033443,264139369,264245386,264351308,264457329,264563232,264669174,264775122,264881052,264986869,265092952,265198869,265304824,265410807,265516703,265622738,265728683,265834567,265940466,266046481,266152452,266258422,266364365,266470260,266576143,266682103,266787980,266893931,266999951,267105881,267211802,267317754,267423716,267529690,267635703,267741640,267847523,267953453,268059499,268165373,268271355,268377354,268483249,268589241,268695163,268801108,268907112,269013079,269118991,269225034,269330986,269436838,269542761,269648740,269754611,269860553,269966607,270072559,270178477,270284472,270390350,270496388,270602355,270708311,270814222,270920107,271026080,271132048,271238009,271343922,271449881,271555857,271661760,271767698,271873677,271979671,272085573,272191541,272297482,272403485,272509430,272615353,272721235,272827265,272933278,273039100,273145037,273251009,273357052,273462979,273568843,273674853,273780831,273886804,273992763,274098704,274204683,274310649,274416631,274522516,274628522,274734482,274840394,274946368,275052440,275158365,275264342,275370279,275476171,275582103,275688164,275794009,275899940,276005927,276111850,276217894,276323829,276429679,276535642,276641646,276747549,276853570,276959657,277065483,277171440,277277387,277383372,277489317,277595173,277701161,277807037,277913046,278018962,278124945,278230904,278336905,278442805,278548791,278654595,278760634,278866552,278972508,279078547,279184459,279290432,279396366,279502332,279608246,279714221,279820236,279926185,280032263,280138197,280244150,280350080,280456073,280561938,280667857,280773902,280879767,280985735,281091669,281197621,281303609,281409575,281515480,281621383,281727438,281833344,281939291,282045308,282151176,282257149,282363040,282469057,282574973,282680835,282786832,282892859,282998714,283104760,283210721,283316660,283422578,283528514,283634474,283740403,283846313,283952241,284058165,284164134,284270102,284375994,284482006,284588024,284693895,284799839,284905789,285011718,285117766,285223782,285329755,285435677,285541642,285647532,285753407,285859370,285965369,286071306,286177280,286283227,286389176,286495143,286601025,286707075,286812941,286918979,287024889,287130934,287236873,287342773,287448708,287554672,287660621,287766600,287872556,287978503,288084462,288190383,288296385,288402315,288508400,288614238,288720219,288826148,288932070,289037975,289143874,289249850,289355818,289461846,289567734,289673670,289779692,289885677,289991547,290097496,290203411,290309434,290415453,290521407,290627278,290733224,290839118,290945170,291051071,291157037,291262975,291368925,291474933,291580910,291686886,291792898,291898818,292004770,292110655,292216588,292322571,292428651,292534634,292640477,292746476,292852416,292958393,293064329,293170269,293276199,293382273,293488199,293594216,293700155,293806108,293911939,294017934,294124011,294229877,294335756,294441684,294547649,294653647,294759626,294865521,294971516,295077496,295183399,295289355,295395346,295501233,295607219,295713238,295819046,295925049,296031044,296136920,296242890,296348828,296454746,296560724,296666701,296772627,296878606,296984601,297090517,297196511,297302395,297408316,297514247,297620228,297726108,297832126,297938110,298044061,298150041,298255916,298361860,298467842,298573821,298679774,298785771,298891726,298997681,299103601,299209625,299315500,299421495,299527418,299633302,299739225,299845200,299951176,300057263,300163100,300269129,300374977,300480986,300586898,300692813,300798847,300904755,301010695,301116637,301222583,301328551,301434498,301540397,301646306,301752296,301858241,301964193,302070147,302176060,302281991,302387969,302493931,302599941,302705870,302811791,302917742,303023677,303129645,303235668,303341584,303447554,303553624,303659508,303765458,303871347,303977270,304083347,304189250,304295266,304401182,304507078,304613002,304719009,304824934,304930886,305036785,305142819,305248804,305354683,305460634,305566621,305672659,305778627,305884532,305990534,306096426,306202371,306308356,306414255,306520249,306626195,306732121,306838115,306944050,307049954,307155898,307261809,307367809,307473852,307579747,307685795,307791683,307897658,308003584,308109516,308215441,308321494,308427321,308533348,308639356,308745283,308851210,308957194,309063206,309169148,309275051,309381028,309486972,309592954,309698867,309804793,309910719,310016670,310122633,310228543,310334556,310440468,310546476,310652331,310758319,310864282,310970296,311076265,311182220,311288212,311394137,311500111,311606093,311712034,311817945,311924004,312029897,312135796,312241743,312347778,312453727,312559727,312665645,312771550,312877554,312983456,313089363,313195373,313301349,313407368,313513327,313619196,313725098,313831054,313937013,314043009,314148913,314254805,314360848,314466785,314572789,314678751,314784691,314890565,314996477,315102440,315208390,315314293,315420213,315526220,315632191,315738151,315844004,315949971,316055968,316161921,316267901,316373820,316479799,316585702,316691630,316797630,316903533,317009542,317115484,317221411,317327295,317433288,317539239,317645101,317751145,317857089,317963070,318069038,318175023,318280933,318386892,318492802,318598769,318704651,318810658,318916605,319022575,319128645,319234525,319340503,319446340,319552247,319658333,319764260,319870234,319976138,320082117,320188038,320294108,320399966,320505996,320611949,320717871,320823796,320929802,321035688,321141522,321247533,321353542,321459552,321565507,321671249,321777284,321883226,321989197,322095183,322201122,322307004,322412958,322518935,322624887,322730801,322836690,322942709,323048671,323154511,323260553,323366514,323472525,323578437,323684391,323790401,323896347,324002282,324108299,324214264,324320143,324426086,324532025,324637965,324744003,324849925,324955911,325061890,325167844,325273852,325379737,325485683,325591592,325697624,325803621,325909565,326015477,326121492,326227472,326333437,326439348,326545332,326651226,326757147,326863032,326969019,327074975,327180989,327286970,327392939,327498878,327604801,327710770,327816747,327922693,328028576,328134579,328240591,328346485,328452373,328558402,328664282,328770261,328876233,328982138,329088095,329194088,329300012,329405983,329511856,329617912,329723946,329829867,329935754,330041627,330147675,330253545,330359495,330465470,330571466,330677484,330783434,330889292,330995318,331101261,331207233,331313191,331419098,331525062,331631056,331737013,331842992,331948864,332054851,332160795,332266764,332372660,332478674,332584587,332690573,332796493,332902443,333008384,333114301,333220316,333326326,333432247,333538232,333644111,333750059,333856083,333961927,334067927,334173950,334279899,334385923,334491714,334597770,334703706,334809651,334915574,335021520,335127444,335233398,335339430,335445250,335551245,335657195,335763098,335869039,335975008,336081001,336186878,336292813,336398812,336504717,336610596,336716585,336822529,336928480,337034559,337140545,337246537,337352423,337458384,337564247,337670199,337776114,337882163,337988104,338094022,338199927,338305919,338411837,338517745,338623708,338729684,338835661,338941571,339047565,339153531,339259584,339365443,339471414,339577460,339683417,339789302,339895242,340001083,340107114,340213122,340319017,340425002,340530989,340636938,340742849,340848835,340954862,341060801,341166680,341272692,341378656,341484588,341590461,341696465,341802445,341908437,342014342,342120273,342226165,342332082,342438106,342543983,342649935,342755903,342861835,342967919,343073845,343179803,343285736,343391780,343497644,343603597,343709518,343815411,343921355,344027360,344133338,344239248,344345214,344451192,344557100,344663045,344768990,344874981,344980969,345086895,345192820,345298790,345404721,345510759,345616684,345722660,345828624,345934553,346040484,346146348,346252366,346358399,346464339,346570380,346676279,346782326,346888226,346994266,347100186,347206117,347312048,347418043,347524042,347629969,347735910,347841789,347947751,348053773,348159644,348265647,348371588,348477471,348583448,348689444,348795375,348901377,349007285,349113231,349219172,349325163,349431168,349537006,349643071,349748981,349854882,349960867,350066759,350172695,350278589,350384584,350490600,350596608,350702543,350808472,350914257,351020235,351126230,351232192,351338151,351444068,351550012,351655988,351761975,351867942,351973970,352079769,352185731,352291638,352397641,352503592,352609488,352715509,352821488,352927438,353033349,353139294,353245369,353351319,353457215,353563130,353669069,353775019,353880988,353986963,354092813,354198822,354304715,354410721,354516677,354622684,354728609,354834616,354940549,355046442,355152434,355258389,355364353,355470408,355576306,355682259,355788212,355894132,356000046,356106003,356211922,356317864,356423876,356529692,356635596,356741567,356847561,356953544,357059451,357165456,357271461,357377327,357483323,357589287,357695199,357801129,357907142,358013134,358119039,358225069,358330967,358436934,358542901,358648787,358754750,358860693,358966576,359072501,359178513,359284538,359390475,359496429,359602421,359708348,359814313,359920188,360025983,360132095,360238039,360343876,360449959,360555815,360661790,360767805,360873747,360979611,361085681,361191648,361297599,361403557,361509549,361615463,361721424,361827357,361933335,362039379,362145269,362251215,362357127,362463213,362569093,362675014,362780971,362886900,362992860,363098775,363204730,363310782,363416744,363522637,363628672,363734614,363840551,363946449,364052450,364158364,364264368,364370287,364476204,364582216,364688226,364794095,364900043,365006042,365111953,365217987,365323937,365429799,365535751,365641653,365747641,365853679,365959578,366065571,366171524,366277493,366383388,366489398,366595350,366701183,366807189,366913093,367019038,367124976,367230939,367336936,367442901,367548842,367654709,367760734,367866754,367972686,368078617,368184590,368290492,368396446,368502460,368608419,368714385,368820306,368926200,369032201,369138196,369244115,369350123,369456081,369562007,369667990,369773915,369879831,369985736,370091787,370197763,370303641,370409717,370515685,370621608,370727504,370833422,370939317,371045268,371151321,371257228,371363245,371469241,371575231,371681117,371787022,371893038,371999013,372104854,372210806,372316831,372422722,372528719,372634668,372740549,372846600,372952549,373058411,373164356,373270272,373376126,373482136,373588067,373693963,373799968,373905975,374011864,374117849,374223842,374329677,374435649,374541632,374647609,374753590,374859505,374965464,375071324,375177316,375283349,375389198,375495239,375601163,375707171,375813088,375918985,376024988,376130909,376236849,376342823,376448818,376554721,376660614,376766608,376872588,376978550,377084535,377190401,377296361,377402350,377508270,377614188,377720161,377826153,377932131,378038138,378143949,378249890,378355951,378461971,378567852,378673781,378779779,378885677,378991688,379097581,379203472,379309502,379415408,379521373,379627294,379733281,379839255,379945259,380051154,380156991,380263004,380368935,380474866,380580872,380686879,380792755,380898668,381004637,381110688,381216553,381322515,381428453,381534419,381640356,381746282,381852213,381958212,382064131,382170073,382275985,382381948,382487891,382593902,382699910,382805812,382911746,383017691,383123662,383229598,383335574,383441515,383547487,383653418,383759373,383865389,383971347,384077294,384183255,384289191,384395106,384501105,384606938,384712908,384818871,384924920,385030914,385136862,385242851,385348842,385454827,385560717,385666659,385772479,385878468,385984517,386090394,386196389,386302282,386408256,386514179,386620216,386726157,386832133,386938131,387044080,387149989,387255967,387361902,387467867,387573869,387679857,387785807,387891785,387997695,388103591,388209597,388315590,388421464,388527394,388633335,388739349,388845287,388951155,389057120,389163082,389269033,389375009,389480941,389586938,389692928,389798868,389904743,390010746,390116613,390222661,390328502,390434528,390540464,390646439,390752443,390858359,390964305,391070321,391176157,391282134,391388107,391494006,391599949,391705892,391811828,391917906,392023819,392129767,392235755,392341672,392447693,392553630,392659577,392765407,392871472,392977434,393083335,393189334,393295238,393401139,393507170,393613165,393719024,393825030,393931030,394036896,394142898,394248793,394354809,394460729,394566696,394672611,394778680,394884645,394990564,395096502,395202489,395308373,395414427,395520323,395626233,395732183,395838126,395944132,396050082,396155939,396261875,396367903,396473879,396579814,396685801,396791752,396897621,397003647,397109601,397215548,397321528,397427421,397533320,397639299,397745165,397851085,397957087,398063059,398168909,398274944,398381000,398486913,398592859,398698777,398804675,398910584,399016548,399122539,399228491,399334551,399440521,399546386,399652293,399758304,399864167,399970110,400076010,400181896,400287911,400393841,400499855,400605730,400711725,400817643,400923741,401029613,401135489,401241555,401347485,401453455,401559432,401665354,401771262,401877243,401983252,402089240,402195184,402301118,402407060,402513115,402618996,402724947,402830909,402936909,403042816,403148800,403254689,403360719,403466633,403572593,403678530,403784542,403890554,403996413,404102340,404208317,404314211,404420199,404526126,404632007,404737936,404843885,404949889,405055870,405161802,405267781,405373763,405479673,405585611,405691596,405797628,405903552,406009504,406115410,406221397,406327307,406433210,406539238,406645134,406751096,406857092,406963094,407068952,407174934,407280889,407386851,407492766,407598708,407704653,407810659,407916543,408022498,408128463,408234532,408340449,408446386,408552434,408658335,408764311,408870252,408976167,409082065,409188005,409294055,409400104,409505943,409611881,409717848,409823792,409929694,410035709,410141702,410247554,410353495,410459530,410565550,410671483,410777491,410883467,410989391,411095326,411201288,411307242,411413246,411519077,411625107,411731057,411836938,411942957,412048853,412154705,412260735,412366689,412472665,412578732,412684631,412790575,412896625,413002538,413108519,413214416,413320329,413426261,413532269,413638240,413744143,413850111,413955999,414061949,414167934,414273993,414379900,414485807,414591769,414697649,414803624,414909594,415015474,415121431,415227500,415333387,415439418,415545317,415651237,415757250,415863106,415969149,416075084,416180999,416286890,416392858,416498874,416604805,416710614,416816607,416922587,417028593,417134550,417240435,417346420,417452472,417558311,417664248,417770132,417876072,417982039,418088049,418193962,418300021,418406016,418511860,418617870,418723760,418829751,418935731,419041695,419147609,419253539,419359509,419465437,419571356,419677258,419783232,419889212,419995221,420101194,420207122,420313120,420419076,420525035,420630971,420736885,420842829,420948711,421054689,421160681,421266662,421372504,421478488,421584431,421690359,421796339,421902342,422008263,422114255,422220155,422326067,422432014,422538042,422643915,422749966,422855894,422961803,423067890,423173750,423279713,423385637,423491593,423597510,423703547,423809444,423915334,424021279,424127293,424233223,424339250,424445135,424551095,424657086,424763049,424868965,424974981,425080977,425186840,425292795,425398707,425504578,425610591,425716586,425822458,425928431,426034439,426140313,426246283,426352217,426458177,426564091,426670058,426775973,426882038,426987951,427093865,427199869,427305839,427411752,427517688,427623656,427729586,427835677,427941550,428047554,428153587,428259443,428365461,428471385,428577263,428683196,428789190,428895283,429001053,429107061,429212932,429318900,429424941,429530886,429636794,429742860,429848790,429954658,430060680,430166556,430272577,430378577,430484489,430590447,430696451,430802437,430908346,431014276,431120206,431226180,431332106,431438096,431544074,431650093,431755974,431861890,431967900,432073871,432179773,432285718,432391737,432497655,432603633,432709681,432815605,432921462,433027362,433133396,433239330,433345251,433451119,433557093,433663040,433768979,433874925,433980877,434086838,434192817,434298745,434404623,434510576,434616563,434722512,434828561,434934431,435040405,435146394,435252386,435358308,435464279,435570236,435676184,435782222,435888174,435994062,436100011,436205920,436311881,436417849,436523840,436629804,436735747,436841585,436947600,437053476,437159498,437265448,437371454,437477402,437583342,437689327,437795275,437901175,438007159,438113059,438218964,438324950,438430928,438536847,438642921,438748890,438854810,438960777,439066726,439172694,439278589,439384550,439490515,439596490,439702427,439808333,439914328,440020356,440126283,440232267,440338243,440444171,440550142,440656108,440762070,440867857,440973871,441079798,441185859,441291743,441397615,441503568,441609488,441715432,441821464,441927431,442033383,442139358,442245267,442351187,442457074,442563097,442669015,442774991,442880993,442986887,443092878,443198817,443304669,443410713,443516688,443622577,443728512,443834525,443940482,444046425,444152342,444258242,444364225,444470100,444576065,444681964,444788020,444894011,444999894,445105855,445211804,445317789,445423713,445529628,445635602,445741569,445847468,445953491,446059395,446165295,446271269,446377226,446483163,446589117,446695058,446801067,446907003,447012951,447118908,447224879,447330809,447436760,447542686,447648658,447754570,447860581,447966512,448072492,448178494,448284437,448390453,448496365,448602304,448708279,448814273,448920206,449026125,449132073,449237966,449343965,449449824,449555746,449661685,449767683,449873737,449979699,450085714,450191595,450297470,450403494,450509390,450615309,450721297,450827241,450933218,451039165,451145170,451251112,451357015,451462993,451568929,451674844,451780825,451886774,451992705,452098653,452204579,452310553,452416442,452522400,452628449,452734350,452840253,452946240,453052211,453158163,453264116,453370179,453476062,453581999,453688024,453793932,453899952,454005817,454111771,454217706,454323673,454429599,454535498,454641497,454747397,454853482,454959427,455065315,455171289,455277333,455383340,455489260,455595197,455701026,455807016,455912879,456018912,456124918,456230880,456336818,456442831,456548710,456654700,456760635,456866615,456972529,457078578,457184444,457290335,457396354,457502308,457608222,457714244,457820166,457926116,458032022,458138041,458244017,458349985,458455924,458561935,458667889,458773874,458879790,458985774,459091641,459197541,459303558,459409590,459515612,459621442,459727452,459833342,459939298,460045266,460151147,460257139,460363203,460469067,460574972,460680981,460786912,460892848,460998836,461104785,461210769,461316684,461422675,461528746,461634656,461740581,461846481,461952448,462058367,462164365,462270296,462376166,462482248,462588064,462694044,462800015,462906006,463011890,463117891,463223833,463329779,463435728,463541723,463647718,463753631,463859603,463965498,464071469,464177395,464283386,464389276,464495227,464601231,464707125,464813132,464919034,465025005,465131024,465236855,465342831,465448806,465554806,465660663,465766666,465872581,465978486,466084566,466190421,466296471,466402392,466508398,466614353,466720444,466826307,466932303,467038249,467144143,467250060,467356124,467461993,467567893,467673861,467779818,467885887,467991836,468097746,468203649,468309611,468415573,468521471,468627407,468733467,468839405,468945406,469051251,469157207,469263176,469369136,469475132,469581033,469687020,469792932,469898893,470004776,470110792,470216718,470322662,470428625,470534552,470640468,470746516,470852487,470958364,471064294,471170166,471276122,471382063,471488119,471594085,471699980,471806054,471911984,472017921,472123958,472229802,472335691,472441697,472547546,472653520,472759489,472865378,472971322,473077278,473183233,473289174,473395147,473501090,473607089,473713018,473818970,473924851,474030833,474136791,474242750,474348778,474454647,474560633,474666519,474772491,474878469,474984450,475090373,475196348,475302320,475408313,475514293,475620173,475726155,475832118,475938015,476043952,476149937,476255829,476361747,476467741,476573710,476679640,476785648,476891584,476997605,477103521,477209440,477315457,477421345,477527272,477633189,477739222,477845267,477951144,478057064,478163060,478268998,478374931,478480897,478586866,478692879,478798801,478904747,479010687,479116588,479222554,479328478,479434442,479540457,479646351,479752319,479858294,479964200,480070242,480176156,480282086,480388144,480494150,480599975,480705968,480812028,480917922,481023828,481129702,481235688,481341607,481447568,481553551,481659400,481765358,481871422,481977360,482083316,482189341,482295251,482401187,482507066,482613092,482718956,482824942,482930946,483036875,483142844,483248775,483354681,483460608,483566604,483672509,483778547,483884480,483990428,484096367,484202383,484308299,484414262,484520220,484626032,484732002,484838007,484944001,485049948,485155980,485261922,485367828,485473855,485579829,485685795,485791806,485897664,486003615,486109576,486215587,486321531,486427466,486533477,486639385,486745358,486851301,486957198,487063103,487169054,487275112,487381074,487486952,487592972,487698923,487804823,487910840,488016754,488122667,488228640,488334622,488440505,488546486,488652449,488758433,488864419,488970362,489076359,489182314,489288316,489394221,489500216,489606218,489712119,489818071,489923954,490029882,490135867,490241797,490347663,490453650,490559547,490665469,490771567,490877511,490983491,491089415,491195363,491301307,491407268,491513209,491619154,491725129,491831142,491937039,492042959,492148971,492254933,492360881,492466791,492572789,492678669,492784658,492890550,492996503,493102419,493208370,493314410,493420330,493526230,493632189,493738170,493844072,493950035,494055941,494161972,494267908,494373923,494479912,494585935,494691820,494797681,494903662,495009600,495115462,495221511,495327446,495433269,495539267,495645263,495751143,495857134,495963061,496069064,496174973,496280961,496386858,496492874,496598796,496704784,496810738,496916751,497022656,497128555,497234557,497340468,497446454,497552363,497658411,497764318,497870265,497976234,498082144,498188147,498294091,498400043,498505976,498611906,498717859,498823846,498929712,499035746,499141592,499247536,499353539,499459493,499565441,499671367,499777370,499883348,499989327,500095300,500201247,500307148,500413078,500519069,500624978,500731021,500836867,500942793,501048763,501154696,501260747,501366694,501472754,501578678,501684602,501790501,501896478,502002392,502108293,502214373,502320323,502426228,502532136,502638074,502743974,502849935,502955931,503061885,503167789,503273782,503379709,503485692,503591648,503697563,503803482,503909379,504015336,504121386,504227266,504333287,504439173,504545223,504651088,504757032,504862923,504968912,505074919,505180941,505286780,505392783,505498688,505604762,505710684,505816651,505922664,506028603,506134473,506240481,506346406,506452340,506558269,506664217,506770298,506876261,506982123,507088061,507194029,507299910,507405947,507511830,507617784,507723724,507829679,507935640,508041606,508147491,508253483,508359407,508465394,508571393,508677395,508783365,508889369,508995268,509101177,509207143,509313223,509419122,509525103,509631011,509736881,509842875,509948847,510054851,510160733,510266654,510372627,510478625,510584622,510690523,510796588,510902490,511008429,511114346,511220297,511326273,511432293,511538209,511644103,511750036,511856043,511962006,512067948,512173840,512279739,512385734,512491737,512597703,512703719,512809668,512915571,513021538,513127491,513233399,513339295,513445270,513551150,513657146,513763072,513869060,513974924,514080971,514186933,514292934,514398987,514504920,514610779,514716709,514822684,514928626,515034675,515140609,515246548,515352484,515458426,515564366,515670350,515776244,515882186,515988192,516094051,516200060,516306062,516411883,516517854,516623878,516729782,516835722,516941671,517047637,517153538,517259565,517365535,517471483,517577482,517683395,517789233,517895176,518001170,518107128,518213218,518319106,518425019,518531066,518636953,518742931,518848883,518954844,519060759,519166728,519272639,519378619,519484652,519590615,519696516,519802520,519908529,520014412,520120406,520226347,520332336,520438320,520544238,520650174,520756106,520862108,520967951,521073927,521179879,521285897,521391831,521497833,521603743,521709674,521815551,521921569,522027555,522133541,522239431,522345453,522451424,522557302,522663217,522769113,522875049,522981000,523086888,523192886,523298903,523404858,523510766,523616687,523722630,523828598,523934531,524040587,524146520,524252493,524358416,524464402,524570398,524676237,524782208,524888141,524994045,525100009,525205978,525311913,525417819,525523811,525629711,525735779,525841723,525947670,526053633,526159554,526265507,526371332,526477384,526583306,526689272,526795293,526901187,527007141,527113089,527218973,527324899,527430891,527536839,527642823,527748840,527854648,527960682,528066584,528172541,528278495,528384486,528490357,528596331,528702291,528808214,528914092,529020144,529126063,529232033,529337959,529443875,529549854,529655904,529761823};
int ans;
int s[6]= {2,3,5,7,11,13};
int test(int t)
{
int cnt = 0;
int j;
for(j = 0; j<6; j++)
{
if(t%s[j]==0)
{
while(t%s[j]==0)
{
t/=s[j];
cnt++;
}
}
}
if(cnt%2==0)
return 1;
return 0;
}
int main()
{
/*freopen("data.out","w",stdout);
for(int i=1;i<=5000;i++){
for(int j=1;j<=200000;j++){
if(test((i-1)*200000+j)) a[i]++;
}
a[i]+=a[i-1];
//cout<<a[i]<<",";
}
for(int i=0;i<=5000;i++){
cout<<a[i]<<",";
}*/
int i,j,k,n,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ans = a[n/200000];
for(i = n/200000*200000+1; i<=n; i++)
{
if(test(i))
ans++;
}
printf("%d\n",ans);
}
return 0;
}题意：问1[,n]区间中，有多少个数，它的2,3,5,7,11,13的这几个因子数目之和为偶数
思路：预处理出所有的x，满足x只含有2,3,5,7,11,3这几个质因子，且数目为偶数。x的数目略大于10000
对于一个数n，枚举所有的x，对于一个x，f(n/x)即求出[1,n/x]中不含有2,3,5，7,11,13作为因子的数有多少个，这个是经典的容斥问题。对所有的f(n/x)求和即可，也就是说乘上那些不算在要求内的素因子后有多少个数，这样复杂度就降下来了~
这个递归方法就是从最大的数开始一直乘法，乘
暴了之后加1个3，然后继续用5乘，然后再加3.。。
然后到2，继续用 5乘，暴了之后加一个3，然后继续用5，
最后结束的状态是只用2乘暴了 ~
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[] = {2,3,5,7,11,13};
int cal(int n) {
int ans = 0;
for(int i = 0; i < 64; i ++) {
int tmp = 1;
for(int j = 0; j < 6; j ++)
if(i & (1 << j)) {
tmp *= a[j];
tmp *= -1;
}
ans += n / tmp;
}
return ans;
}
const int maxn = 1000000000;
int b[1000010];
int tot;
void pre_process(long long x,int pos,int flag) {
if(pos == 6) {
if(!flag) b[++ tot] = x;
return;
}
while(x <= maxn) {
pre_process(x,pos + 1,flag);
x *= a[pos];
flag ^= 1;
}
}
void solve() {
int n;
scanf("%d",&n);
int ans = 0;
for(int i = 1; i <= tot && b[i] <= n; i ++) {
ans += cal(n / b[i]);
}
printf("%d\n",ans);
}
int main()
{
pre_process(1,0,0);
sort(b + 1,b + tot + 1);
int t;
scanf("%d",&t);
while(t --) solve();
return 0;
}