提交时间:2022-08-08 11:23:10

运行 ID: 54907

#include<bits/stdc++.h> using namespace std; template<typename T>void in(T &a) { T ans=0; char c=getchar(); for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar())ans=ans*10+c-'0'; a=ans; } template<typename T,typename... Args>void in(T &a,Args&...args) { in(a),in(args...); } bool check(int k){ for(int i=2;i*i<=k;i++)if(k%(i*i)==0)return 1; return 0; } int t; const int ans[2005]={0,12,26,40,54,69,81,95,109,122,137,152,164,176,190,204,219,232,246,259,272,287,300,313,327,344,356,370,384,396,411,427,439,452,466,480,493,506,519,532,546,559,574,587,601,614,626,640,655,671,686,699,714,728,743,757,770,782,796,811,824,837,851,865,878,891,905,918,933,945,959,971,984,1001,1014,1028,1042,1056,1069,1083,1098,1111,1124,1141,1153,1166,1179,1193,1207,1218,1232,1247,1260,1274,1288,1301,1314,1327,1341,1354,1368,1381,1395,1409,1425,1438,1452,1467,1484,1495,1509,1523,1536,1549,1563,1578,1591,1604,1618,1632,1645,1660,1674,1686,1700,1714,1727,1740,1756,1768,1782,1796,1810,1824,1837,1851,1864,1876,1891,1904,1917,1931,1945,1959,1972,1991,2004,2018,2031,2044,2060,2073,2086,2101,2114,2128,2142,2155,2168,2183,2199,2212,2225,2238,2251,2266,2279,2294,2307,2320,2335,2349,2360,2374,2387,2400,2414,2427,2441,2456,2469,2482,2497,2510,2526,2539,2551,2564,2579,2591,2606,2620,2633,2646,2660,2674,2689,2703,2719,2733,2745,2759,2772,2787,2801,2815,2828,2841,2855,2867,2881,2895,2909,2922,2935,2950,2964,2978,2991,3003,3017,3029,3043,3058,3071,3084,3096,3113,3127,3140,3154,3168,3181,3195,3209,3222,3235,3248,3262,3276,3290,3305,3319,3333,3346,3358,3371,3385,3401,3412,3427,3440,3452,3466,3480,3494,3510,3525,3538,3552,3565,3578,3591,3604,3616,3631,3645,3659,3674,3687,3701,3714,3727,3742,3757,3771,3786,3797,3810,3824,3836,3850,3864,3878,3892,3907,3919,3934,3949,3964,3977,3990,4003,4017,4032,4046,4059,4071,4084,4099,4115,4129,4142,4155,4170,4184,4198,4211,4226,4237,4253,4267,4279,4294,4309,4322,4335,4349,4364,4379,4393,4406,4420,4434,4449,4463,4475,4489,4503,4516,4530,4543,4556,4570,4584,4598,4612,4626,4641,4656,4670,4682,4695,4709,4722,4736,4749,4763,4777,4789,4804,4818,4830,4845,4857,4871,4886,4902,4916,4929,4943,4957,4971,4986,4999,5013,5025,5039,5053,5065,5080,5094,5107,5120,5134,5147,5160,5175,5188,5201,5215,5228,5243,5257,5272,5287,5299,5312,5326,5338,5353,5367,5381,5394,5409,5424,5438,5451,5465,5478,5491,5505,5520,5534,5547,5560,5572,5585,5601,5613,5627,5642,5657,5671,5684,5696,5710,5722,5735,5750,5763,5776,5792,5807,5819,5832,5845,5859,5873,5884,5900,5913,5925,5940,5955,5968,5982,5994,6008,6023,6039,6051,6064,6077,6091,6104,6118,6132,6146,6157,6173,6186,6198,6214,6229,6243,6256,6270,6284,6298,6311,6325,6339,6352,6367,6380,6392,6406,6421,6435,6448,6462,6475,6488,6503,6518,6530,6542,6556,6570,6583,6598,6612,6625,6638,6653,6666,6678,6695,6707,6721,6736,6748,6762,6775,6789,6802,6815,6830,6844,6858,6870,6884,6898,6912,6927,6940,6955,6968,6981,6995,7009,7023,7037,7051,7064,7078,7091,7105,7118,7132,7143,7157,7171,7185,7198,7210,7225,7239,7254,7268,7282,7295,7309,7322,7337,7352,7367,7381,7395,7408,7421,7434,7448,7461,7476,7490,7504,7520,7531,7545,7560,7573,7588,7602,7615,7630,7643,7657,7670,7683,7695,7710,7724,7738,7752,7764,7777,7791,7803,7820,7834,7846,7859,7874,7889,7903,7916,7931,7944,7957,7970,7984,7998,8012,8025,8037,8053,8069,8080,8097,8112,8124,8137,8151,8163,8176,8190,8203,8218,8231,8244,8259,8273,8286,8299,8311,8326,8341,8354,8368,8380,8395,8408,8423,8437,8451,8463,8476,8491,8505,8518,8530,8545,8557,8573,8587,8600,8615,8627,8642,8654,8669,8684,8697,8713,8728,8740,8754,8767,8782,8794,8809,8823,8837,8851,8864,8879,8894,8906,8920,8934,8947,8962,8976,8990,9002,9016,9029,9042,9056,9069,9083,9096,9110,9124,9136,9149,9164,9175,9190,9206,9219,9233,9247,9261,9273,9286,9300,9316,9329,9343,9357,9370,9383,9397,9412,9426,9441,9452,9466,9481,9495,9508,9520,9535,9550,9564,9578,9593,9606,9618,9634,9647,9660,9676,9688,9702,9715,9728,9743,9758,9770,9785,9799,9812,9826,9838,9851,9865,9880,9896,9910,9924,9938,9951,9965,9978,9992,10003,10020,10033,10045,10059,10072,10086,10099,10113,10127,10139,10153,10166,10180,10193,10209,10224,10236,10250,10264,10277,10291,10305,10319,10332,10347,10361,10374,10386,10401,10415,10429,10442,10456,10471,10485,10499,10511,10524,10541,10552,10567,10582,10595,10608,10621,10634,10648,10662,10675,10688,10702,10714,10728,10742,10754,10768,10781,10795,10810,10822,10836,10849,10862,10878,10891,10905,10919,10935,10949,10963,10977,10990,11004,11019,11032,11046,11059,11074,11089,11100,11114,11127,11139,11153,11167,11182,11195,11210,11223,11236,11249,11264,11279,11293,11307,11321,11334,11348,11363,11374,11387,11401,11414,11428,11443,11456,11470,11483,11496,11510,11523,11537,11551,11565,11578,11591,11604,11617,11631,11643,11658,11673,11686,11700,11715,11728,11742,11755,11768,11782,11797,11812,11825,11838,11852,11867,11880,11895,11909,11920,11934,11948,11960,11974,11987,12002,12016,12031,12045,12060,12073,12085,12099,12112,12129,12142,12154,12168,12183,12196,12211,12224,12239,12252,12266,12279,12293,12305,12321,12337,12351,12365,12378,12393,12406,12420,12434,12447,12461,12474,12489,12502,12515,12528,12543,12557,12572,12587,12602,12614,12627,12639,12655,12670,12684,12697,12710,12724,12737,12749,12764,12778,12791,12803,12819,12832,12845,12861,12877,12890,12904,12916,12931,12945,12960,12972,12983,12997,13013,13024,13040,13054,13067,13080,13094,13107,13120,13133,13146,13160,13174,13189,13204,13217,13229,13242,13255,13268,13283,13294,13309,13322,13336,13350,13363,13378,13393,13405,13419,13434,13448,13462,13476,13491,13503,13518,13532,13546,13560,13573,13588,13600,13612,13627,13641,13656,13669,13680,13694,13708,13722,13736,13749,13763,13778,13791,13804,13819,13834,13847,13863,13877,13889,13905,13919,13932,13946,13960,13973,13988,14002,14014,14028,14040,14054,14067,14079,14092,14107,14120,14134,14148,14161,14174,14190,14203,14215,14227,14241,14256,14269,14283,14296,14312,14327,14342,14354,14367,14382,14395,14409,14422,14435,14450,14462,14477,14491,14505,14520,14533,14547,14558,14573,14587,14601,14615,14630,14644,14658,14671,14686,14700,14713,14729,14744,14757,14771,14785,14799,14812,14826,14838,14852,14868,14881,14894,14907,14919,14934,14945,14959,14973,14986,14998,15013,15029,15043,15056,15069,15083,15096,15109,15123,15137,15152,15168,15183,15197,15211,15223,15239,15254,15267,15280,15294,15307,15322,15335,15349,15363,15376,15388,15401,15415,15429,15443,15456,15470,15485,15497,15513,15527,15542,15556,15569,15584,15598,15610,15623,15637,15652,15666,15679,15692,15705,15720,15733,15746,15761,15772,15788,15801,15813,15827,15841,15856,15869,15882,15896,15910,15923,15936,15949,15963,15978,15992,16006,16020,16035,16048,16062,16074,16087,16101,16116,16130,16144,16155,16169,16185,16197,16213,16226,16240,16253,16266,16279,16293,16308,16320,16333,16346,16359,16374,16387,16402,16415,16428,16441,16454,16470,16482,16496,16510,16524,16537,16551,16565,16579,16591,16605,16619,16632,16647,16661,16673,16686,16699,16714,16727,16741,16754,16767,16780,16795,16808,16821,16835,16851,16862,16877,16892,16905,16918,16931,16945,16958,16971,16985,16999,17013,17026,17041,17053,17066,17080,17094,17108,17121,17135,17149,17164,17177,17191,17203,17218,17232,17244,17258,17273,17286,17298,17313,17327,17341,17355,17369,17382,17396,17411,17426,17439,17452,17465,17480,17493,17507,17519,17532,17545,17561,17574,17587,17602,17616,17631,17643,17657,17670,17681,17698,17714,17726,17741,17754,17767,17780,17794,17807,17820,17834,17847,17861,17875,17890,17903,17914,17928,17943,17956,17971,17985,17998,18012,18026,18040,18053,18065,18079,18094,18107,18121,18135,18148,18161,18175,18189,18202,18216,18228,18244,18258,18271,18284,18297,18312,18325,18338,18352,18365,18379,18392,18405,18420,18432,18447,18462,18476,18490,18502,18515,18528,18542,18556,18570,18583,18596,18609,18624,18638,18651,18663,18677,18693,18707,18721,18734,18748,18763,18775,18790,18805,18818,18832,18846,18860,18874,18888,18901,18916,18930,18944,18958,18973,18986,19000,19013,19026,19041,19053,19068,19082,19095,19111,19126,19138,19152,19164,19178,19191,19204,19218,19231,19245,19260,19274,19288,19302,19316,19329,19344,19358,19370,19384,19399,19413,19427,19439,19454,19468,19482,19497,19510,19522,19536,19550,19563,19577,19591,19603,19618,19632,19643,19657,19670,19684,19698,19711,19725,19739,19752,19767,19782,19795,19810,19823,19836,19849,19865,19877,19890,19903,19917,19929,19944,19959,19974,19986,20001,20016,20028,20041,20055,20069,20083,20098,20112,20126,20139,20151,20166,20180,20193,20208,20221,20235,20249,20263,20276,20289,20303,20315,20329,20344,20358,20370,20382,20397,20411,20425,20440,20455,20468,20483,20497,20510,20524,20539,20552,20566,20579,20592,20606,20621,20635,20647,20660,20673,20688,20699,20714,20729,20743,20756,20770,20785,20799,20813,20827,20842,20855,20868,20881,20895,20907,20921,20935,20949,20965,20977,20990,21004,21018,21033,21046,21059,21075,21087,21100,21115,21127,21140,21156,21170,21183,21198,21211,21225,21239,21251,21265,21278,21291,21306,21320,21334,21347,21360,21373,21387,21403,21416,21430,21442,21456,21469,21483,21497,21511,21523,21539,21553,21565,21580,21593,21606,21618,21631,21646,21660,21674,21687,21700,21713,21728,21745,21758,21773,21786,21800,21814,21827,21840,21854,21871,21886,21899,21911,21926,21942,21955,21967,21981,21995,22009,22023,22036,22049,22063,22076,22091,22105,22118,22133,22145,22160,22174,22187,22202,22215,22231,22243,22258,22272,22285,22299,22311,22325,22340,22353,22367,22381,22393,22409,22423,22436,22451,22465,22479,22492,22506,22519,22532,22547,22562,22575,22587,22601,22616,22627,22642,22655,22667,22680,22694,22708,22722,22736,22750,22763,22778,22792,22806,22821,22834,22847,22860,22874,22891,22902,22917,22932,22945,22959,22972,22986,23000,23014,23028,23042,23055,23068,23085,23099,23112,23125,23139,23153,23167,23178,23193,23207,23219,23234,23248,23261,23275,23287,23302,23316,23330,23343,23356,23370,23383,23398,23411,23426,23442,23453,23468,23482,23494,23509,23522,23536,23549,23561,23575,23589,23601,23614,23629,23643,23659,23672,23686,23699,23714,23727,23740,23753,23766,23780,23796,23810,23823,23835,23848,23863,23876,23889,23902,23916,23931,23945,23959,23971,23986,23999,24014,24027,24039,24053,24067,24081,24094,24107,24120,24134,24149,24161,24174,24189,24203,24216,24230,24245,24260,24272,24286,24300,24312,24327,24340,24353,24367,24380,24395,24409,24423,24435,24448,24461,24477,24492,24504,24518,24533,24544,24558,24573,24586,24599,24612,24628,24642,24656,24669,24684,24698,24713,24728,24741,24754,24768,24782,24794,24810,24823,24836,24850,24863,24877,24890,24903,24917,24929,24943,24958,24970,24983,24998,25012,25025,25041,25055,25068,25081,25094,25109,25125,25137,25151,25166,25179,25194,25206,25219,25233,25248,25261,25275,25289,25304,25317,25330,25346,25360,25372,25389,25404,25416,25429,25442,25454,25467,25481,25494,25508,25523,25536,25550,25563,25577,25589,25601,25617,25632,25644,25658,25671,25684,25699,25715,25731,25744,25756,25771,25786,25799,25812,25825,25839,25852,25867,25880,25893,25911,25923,25937,25950,25964,25977,25991,26006,26020,26032,26046,26060,26074,26086,26100,26115,26128,26142,26155,26169,26185,26198,26211,26225,26238,26252,26266,26279,26292,26306,26319,26334,26349,26361,26376,26389,26405,26418,26431,26444,26458,26470,26485,26499,26511,26525,26539,26552,26564,26578,26591,26605,26619,26632,26646,26660,26673,26687,26701,26715,26729,26740,26756,26770,26783,26796,26809,26824,26838,26853,26867,26881,26895,26907,26922,26936,26949,26964,26978,26992,27006,27019,27035,27051,27062,27076,27090,27105,27119,27132,27145,27158,27175,27189,27202,27215,27229,27244,27257,27270,27284,27295,27310,27324,27336,27349,27362,27379,27392,27405,27419,27432,27444}; int solve(int n){ int num=ans[n/35]; for(int i=n-(n%35)+1;i<=n;i++)num+=check(i); return num; } int main(){ in(t); for(int i=1,n;i<=t;i++)in(n),printf("%d\n",solve(n)); return 0; }