#include <bits/stdc++.h>
using namespace std;
int a;
int b;
int c = 2;
int x[100000] = {0};
int prec[] = {
    0,        4784,     8978,     12981,    16901,    20732,    24523,
    28249,    31916,    35585,    39176,    42818,    46430,    49962,
    53516,    57023,    60523,    64040,    67489,    70985,    74417,
    77879,    81285,    84679,    88055,    91433,    94878,    98240,
    101608,   104979,   108284,   111653,   115039,   118375,   121695,
    124997,   128270,   131626,   134912,   138219,   141503,   144830,
    148121,   151368,   154619,   157925,   161166,   164444,   167675,
    170946,   174194,   177433,   180617,   183844,   187048,   190283,
    193493,   196709,   199900,   203111,   206333,   209526,   212732,
    215966,   219123,   222272,   225463,   228651,   231844,   235069,
    238261,   241443,   244581,   247733,   250868,   253974,   257141,
    260352,   263482,   266623,   269760,   272885,   276014,   279149,
    282271,   285396,   288556,   291710,   294878,   297984,   301101,
    304177,   307326,   310444,   313579,   316642,   319813,   322904,
    326007,   329106,   332181,   335268,   338394,   341465,   344551,
    347665,   350739,   353840,   356909,   360000,   363080,   366160,
    369261,   372328,   375439,   378518,   381635,   384728,   387817,
    390920,   393993,   397033,   400087,   403209,   406288,   409309,
    412333,   415431,   418499,   421556,   424569,   427583,   430660,
    433680,   436753,   439791,   442818,   445857,   448901,   451962,
    454974,   457972,   461015,   464069,   467135,   470153,   473178,
    476215,   479250,   482265,   485275,   488279,   491293,   494311,
    497242,   500236,   503251,   506276,   509308,   512383,   515414,
    518404,   521398,   524428,   527422,   530472,   533469,   536442,
    539450,   542467,   545501,   548499,   551461,   554513,   557493,
    560489,   563514,   566514,   569508,   572481,   575503,   578464,
    581445,   584484,   587448,   590416,   593357,   596373,   599365,
    602379,   605357,   608340,   611346,   614316,   617284,   620283,
    623219,   626204,   629187,   632137,   635171,   638124,   641088,
    644018,   646968,   649933,   652929,   655897,   658857,   661819,
    664771,   667743,   670676,   673688,   676670,   679672,   682576,
    685541,   688504,   691478,   694490,   697405,   700326,   703273,
    706181,   709115,   712113,   715038,   717989,   720960,   723896,
    726882,   729831,   732782,   735740,   738676,   741606,   744563,
    747458,   750384,   753318,   756217,   759188,   762199,   765150,
    768087,   771012,   773928,   776896,   779827,   782754,   785698,
    788611,   791513,   794449,   797361,   800286,   803241,   806180,
    809116,   812028,   814963,   817868,   820796,   823752,   826720,
    829643,   832596,   835498,   838436,   841364,   844292,   847194,
    850080,   853022,   855895,   858875,   861761,   864672,   867592,
    870514,   873482,   876358,   879282,   882186,   885138,   888023,
    890933,   893857,   896758,   899686,   902573,   905460,   908421,
    911332,   914214,   917110,   920007,   922881,   925822,   928780,
    931678,   934604,   937520,   940453,   943326,   946295,   949181,
    952088,   955026,   957871,   960726,   963624,   966507,   969407,
    972309,   975196,   978085,   980962,   983867,   986746,   989647,
    992538,   995405,   998272,   1001141,  1004047,  1006935,  1009828,
    1012698,  1015619,  1018497,  1021407,  1024321,  1027185,  1030064,
    1032962,  1035803,  1038722,  1041665,  1044521,  1047338,  1050175,
    1053074,  1055897,  1058798,  1061676,  1064500,  1067388,  1070268,
    1073174,  1076029,  1078883,  1081790,  1084692,  1087554,  1090413,
    1093331,  1096221,  1099056,  1101903,  1104801,  1107645,  1110568,
    1113425,  1116309,  1119226,  1122066,  1124941,  1127772,  1130652,
    1133559,  1136475,  1139334,  1142195,  1145026,  1147867,  1150738,
    1153592,  1156490,  1159339,  1162244,  1165140,  1168043,  1170911,
    1173746,  1176591,  1179444,  1182370,  1185244,  1188093,  1190925,
    1193801,  1196660,  1199545,  1202432,  1205285,  1208198,  1211026,
    1213868,  1216688,  1219588,  1222393,  1225259,  1228119,  1230996,
    1233830,  1236682,  1239605,  1242422,  1245272,  1248112,  1250996,
    1253792,  1256652,  1259537,  1262363,  1265205,  1268047,  1270890,
    1273689,  1276506,  1279377,  1282286,  1285127,  1287980,  1290771,
    1293580,  1296434,  1299249,  1302081,  1304899,  1307765,  1310565,
    1313437,  1316314,  1319179,  1321953,  1324799,  1327680,  1330570,
    1333417,  1336222,  1339091,  1341880,  1344730,  1347558,  1350402,
    1353252,  1356098,  1358925,  1361746,  1364529,  1367411,  1370266,
    1373089,  1375934,  1378787,  1381608,  1384448,  1387240,  1390062,
    1392850,  1395709,  1398555,  1401374,  1404179,  1407069,  1409899,
    1412745,  1415626,  1418381,  1421271,  1424100,  1426913,  1429775,
    1432595,  1435430,  1438258,  1441129,  1443939,  1446779,  1449605,
    1452383,  1455248,  1458083,  1460920,  1463729,  1466529,  1469369,
    1472195,  1475031,  1477838,  1480667,  1483501,  1486323,  1489166,
    1491981,  1494787,  1497648,  1500453,  1503239,  1506081,  1508873,
    1511686,  1514527,  1517367,  1520184,  1523011,  1525806,  1528622,
    1531402,  1534201,  1536997,  1539894,  1542683,  1545503,  1548241,
    1551093,  1553884,  1556702,  1559565,  1562352,  1565117,  1567943,
    1570716,  1573536,  1576359,  1579176,  1581960,  1584772,  1587542,
    1590356,  1593212,  1596005,  1598783,  1601564,  1604386,  1607165,
    1609974,  1612824,  1615617,  1618452,  1621217,  1624007,  1626767,
    1629636,  1632421,  1635222,  1637991,  1640857,  1643718,  1646485,
    1649297,  1652064,  1654854,  1657619,  1660460,  1663265,  1666081,
    1668892,  1671700,  1674594,  1677356,  1680125,  1682935,  1685691,
    1688539,  1691341,  1694101,  1696863,  1699639,  1702441,  1705278,
    1708110,  1710912,  1713725,  1716510,  1719267,  1722095,  1724880,
    1727671,  1730436,  1733217,  1736052,  1738807,  1741642,  1744421,
    1747205,  1750007,  1752772,  1755537,  1758337,  1761093,  1763839,
    1766647,  1769444,  1772246,  1775046,  1777876,  1780671,  1783464,
    1786236,  1789019,  1791841,  1794680,  1797448,  1800274,  1803074,
    1805871,  1808647,  1811416,  1814143,  1816933,  1819707,  1822528,
    1825244,  1828005,  1830793,  1833548,  1836360,  1839214,  1841996,
    1844792,  1847581,  1850327,  1853089,  1855856,  1858663,  1861433,
    1864207,  1866991,  1869796,  1872540,  1875345,  1878117,  1880878,
    1883646,  1886490,  1889297,  1892075,  1894867,  1897679,  1900521,
    1903296,  1906069,  1908797,  1911589,  1914346,  1917129,  1919906,
    1922737,  1925489,  1928318,  1931029,  1933873,  1936618,  1939421,
    1942195,  1944975,  1947727,  1950518,  1953327,  1956076,  1958882,
    1961653,  1964430,  1967231,  1969999,  1972724,  1975510,  1978238,
    1981017,  1983809,  1986618,  1989438,  1992205,  1994950,  1997721,
    2000489,  2003304,  2006033,  2008816,  2011607,  2014373,  2017180,
    2019933,  2022702,  2025513,  2028256,  2031020,  2033803,  2036610,
    2039323,  2042136,  2044905,  2047682,  2050502,  2053230,  2055971,
    2058719,  2061484,  2064275,  2067035,  2069780,  2072561,  2075349,
    2078104,  2080845,  2083584,  2086330,  2089097,  2091864,  2094672,
    2097407,  2100185,  2102972,  2105738,  2108433,  2111259,  2113990,
    2116784,  2119527,  2122304,  2125069,  2127838,  2130618,  2133419,
    2136173,  2138962,  2141713,  2144481,  2147172,  2149924,  2152702,
    2155442,  2158237,  2161008,  2163758,  2166537,  2169247,  2171965,
    2174706,  2177470,  2180269,  2183018,  2185806,  2188547,  2191332,
    2194100,  2196835,  2199596,  2202324,  2205083,  2207860,  2210669,
    2213444,  2216182,  2218953,  2221739,  2224515,  2227246,  2230006,
    2232708,  2235482,  2238231,  2240991,  2243756,  2246480,  2249227,
    2252025,  2254788,  2257554,  2260312,  2263079,  2265828,  2268545,
    2271245,  2274003,  2276736,  2279483,  2282217,  2284983,  2287747,
    2290512,  2293240,  2295997,  2298702,  2301494,  2304177,  2306931,
    2309704,  2312443,  2315163,  2317910,  2320691,  2323417,  2326186,
    2328942,  2331676,  2334374,  2337139,  2339871,  2342642,  2345411,
    2348163,  2350887,  2353608,  2356373,  2359139,  2361872,  2364678,
    2367432,  2370149,  2372878,  2375651,  2378388,  2381162,  2383896,
    2386653,  2389450,  2392222,  2394902,  2397618,  2400363,  2403099,
    2405857,  2408603,  2411351,  2414127,  2416904,  2419627,  2422296,
    2425056,  2427745,  2430503,  2433251,  2436001,  2438719,  2441528,
    2444352,  2447016,  2449765,  2452482,  2455256,  2458031,  2460744,
    2463429,  2466187,  2468912,  2471679,  2474403,  2477113,  2479832,
    2482617,  2485399,  2488154,  2490869,  2493631,  2496331,  2499026,
    2501804,  2504528,  2507234,  2509986,  2512726,  2515473,  2518175,
    2520875,  2523614,  2526330,  2529122,  2531839,  2534604,  2537308,
    2540008,  2542791,  2545541,  2548284,  2551055,  2553802,  2556546,
    2559256,  2562021,  2564750,  2567510,  2570148,  2572929,  2575664,
    2578403,  2581128,  2583836,  2586615,  2589384,  2592090,  2594819,
    2597536,  2600254,  2602944,  2605706,  2608394,  2611086,  2613806,
    2616565,  2619321,  2622048,  2624787,  2627470,  2630206,  2632916,
    2635613,  2638344,  2641068,  2643874,  2646581,  2649274,  2651923,
    2654664,  2657389,  2660089,  2662840,  2665564,  2668329,  2671039,
    2673788,  2676540,  2679254,  2682014,  2684761,  2687515,  2690185,
    2692884,  2695614,  2698331,  2701067,  2703798,  2706497,  2709174,
    2711871,  2714585,  2717374,  2720152,  2722854,  2725559,  2728236,
    2730937,  2733698,  2736447,  2739146,  2741927,  2744682,  2747379,
    2750078,  2752811,  2755521,  2758290,  2761026,  2763725,  2766426,
    2769153,  2771910,  2774616,  2777363,  2780032,  2782759,  2785459,
    2788181,  2790935,  2793661,  2796375,  2799109,  2801844,  2804531,
    2807261,  2809930,  2812655,  2815400,  2818088,  2820817,  2823539,
    2826276,  2828967,  2831689,  2834417,  2837100,  2839799,  2842571,
    2845296,  2847955,  2850686,  2853362,  2856131,  2858814,  2861494,
    2864215,  2866912,  2869649,  2872353,  2875061,  2877770,  2880505,
    2883226,  2885940,  2888661,  2891324,  2894042,  2896737,  2899482,
    2902173,  2904857,  2907606,  2910319,  2913026,  2915749,  2918453,
    2921165,  2923834,  2926597,  2929265,  2931966,  2934703,  2937422,
    2940118,  2942867,  2945636,  2948312,  2951035,  2953764,  2956447,
    2959193,  2961881,  2964616,  2967240,  2969938,  2972638,  2975367,
    2978051,  2980755,  2983431,  2986123,  2988902,  2991612,  2994331,
    2997075,  2999799,  3002504,  3005203,  3007900,  3010597,  3013324,
    3016009,  3018743,  3021417,  3024129,  3026843,  3029542,  3032258,
    3034938,  3037647,  3040326,  3043022,  3045754,  3048458,  3051170,
    3053831,  3056533,  3059268,  3061963,  3064626,  3067352,  3069997,
    3072755,  3075490,  3078186,  3080941,  3083637,  3086305,  3089049,
    3091766,  3094461,  3097083,  3099791,  3102503,  3105214,  3107929,
    3110676,  3113376,  3116121,  3118822,  3121506,  3124226,  3126914,
    3129663,  3132389,  3135041,  3137800,  3140465,  3143179,  3145895,
    3148595,  3151359,  3154060,  3156704,  3159381,  3162037,  3164764,
    3167422,  3170165,  3172860,  3175583,  3178276,  3180981,  3183679,
    3186336,  3189067,  3191741,  3194439,  3197144,  3199905,  3202633,
    3205350,  3208093,  3210815,  3213514,  3216212,  3218845,  3221531,
    3224234,  3226984,  3229664,  3232326,  3235040,  3237756,  3240412,
    3243108,  3245793,  3248448,  3251142,  3253794,  3256465,  3259118,
    3261786,  3264499,  3267184,  3269881,  3272566,  3275208,  3277990,
    3280684,  3283348,  3286023,  3288733,  3291422,  3294158,  3296809,
    3299511,  3302209,  3304882,  3307587,  3310219,  3312951,  3315658,
    3318340,  3321024,  3323750,  3326372,  3329060,  3331730,  3334387,
    3337067,  3339778,  3342472,  3345126,  3347848,  3350545,  3353226,
    3355956,  3358630,  3361303,  3363969,  3366670,  3369387,  3372104,
    3374796,  3377477,  3380175,  3382885,  3385555,  3388181,  3390855,
    3393551,  3396270,  3398959,  3401658,  3404348,  3407022,  3409749,
    3412424,  3415112,  3417799,  3420476,  3423164,  3425804,  3428513,
    3431140,  3433831,  3436495,  3439209,  3441873,  3444597,  3447272,
    3450005,  3452685,  3455326,  3458010,  3460716,  3463433,  3466044,
    3468740,  3471402,  3474095,  3476807,  3479443,  3482094,  3484813,
    3487498,  3490171,  3492860,  3495568,  3498297,  3500974,  3503652,
    3506387,  3509080,  3511783,  3514444,  3517154,  3519834,  3522520,
    3525176,  3527908,  3530582,  3533256,  3535969,  3538668,  3541338,
    3543978,  3546667,  3549376,  3552022,  3554739,  3557385,  3560090,
    3562780,  3565457,  3568117,  3570777,  3573441,  3576162,  3578838,
    3581527,  3584202,  3586899,  3589608,  3592224,  3594895,  3597609,
    3600284,  3602937,  3605598,  3608315,  3611057,  3613719,  3616375,
    3619063,  3621779,  3624437,  3627138,  3629813,  3632494,  3635172,
    3637897,  3640546,  3643225,  3645881,  3648522,  3651242,  3653950,
    3656685,  3659419,  3662084,  3664727,  3667446,  3670105,  3672775,
    3675493,  3678172,  3680848,  3683590,  3686168,  3688865,  3691503,
    3694149,  3696775,  3699495,  3702151,  3704779,  3707476,  3710195,
    3712861,  3715571,  3718229,  3720907,  3723622,  3726326,  3729014,
    3731697,  3734399,  3737057,  3739687,  3742387,  3745052,  3747736,
    3750447,  3753093,  3755763,  3758470,  3761125,  3763798,  3766488,
    3769101,  3771838,  3774512,  3777096,  3779799,  3782494,  3785161,
    3787804,  3790455,  3793100,  3795810,  3798471,  3801142,  3803841,
    3806532,  3809252,  3811893,  3814570,  3817240,  3819899,  3822594,
    3825303,  3827949,  3830626,  3833257,  3835966,  3838551,  3841206,
    3843893,  3846531,  3849184,  3851821,  3854488,  3857123,  3859809,
    3862541,  3865213,  3867908,  3870566,  3873197,  3875855,  3878498,
    3881127,  3883820,  3886491,  3889196,  3891882,  3894547,  3897254,
    3899883,  3902460,  3905110,  3907779,  3910369,  3913050,  3915712,
    3918400,  3921049,  3923696,  3926401,  3929085,  3931738,  3934443,
    3937079,  3939772,  3942498,  3945191,  3947875,  3950555,  3953194,
    3955921,  3958645,  3961297,  3963906,  3966568,  3969211,  3971880,
    3974536,  3977155,  3979753,  3982460,  3985072,  3987720,  3990416,
    3993126,  3995735,  3998438,  4001109,  4003807,  4006464,  4009128,
    4011827,  4014469,  4017140,  4019846,  4022481,  4025096,  4027765,
    4030424,  4033095,  4035734,  4038441,  4041068,  4043777,  4046464,
    4049121,  4051770,  4054424,  4057114,  4059771,  4062451,  4065123,
    4067794,  4070475,  4073176,  4075821,  4078473,  4081177,  4083782,
    4086435,  4089090,  4091774,  4094421,  4097099,  4099748,  4102417,
    4105056,  4107702,  4110356,  4113050,  4115722,  4118385,  4121052,
    4123728,  4126380,  4129050,  4131700,  4134353,  4137024,  4139686,
    4142364,  4145061,  4147677,  4150324,  4153011,  4155686,  4158364,
    4160967,  4163597,  4166236,  4168923,  4171606,  4174224,  4176870,
    4179522,  4182183,  4184850,  4187489,  4190141,  4192811,  4195422,
    4198063,  4200732,  4203355,  4206045,  4208687,  4211357,  4213982,
    4216686,  4219357,  4221985,  4224628,  4227283,  4229915,  4232565,
    4235233,  4237862,  4240503,  4243170,  4245785,  4248402,  4251066,
    4253702,  4256360,  4259015,  4261661,  4264294,  4266922,  4269625,
    4272264,  4274957,  4277598,  4280202,  4282798,  4285399,  4288065,
    4290688,  4293351,  4296021,  4298654,  4301295,  4303982,  4306609,
    4309218,  4311887,  4314529,  4317235,  4319923,  4322593,  4325294,
    4327912,  4330591,  4333234,  4335879,  4338516,  4341144,  4343802,
    4346451,  4349053,  4351735,  4354389,  4357049,  4359663,  4362342,
    4364926,  4367588,  4370299,  4372936,  4375553,  4378193,  4380845,
    4383575,  4386240,  4388879,  4391542,  4394200,  4396851,  4399521,
    4402187,  4404832,  4407487,  4410086,  4412694,  4415371,  4418023,
    4420721,  4423372,  4425992,  4428609,  4431243,  4433902,  4436580,
    4439170,  4441823,  4444490,  4447138,  4449673,  4452307,  4454923,
    4457555,  4460241,  4462894,  4465544,  4468140,  4470785,  4473457,
    4476148,  4478750,  4481417,  4484076,  4486724,  4489312,  4492007,
    4494652,  4497293,  4499966,  4502619,  4505253,  4507856,  4510573,
    4513194,  4515919,  4518560,  4521186,  4523774,  4526427,  4529073,
    4531708,  4534347,  4536968,  4539593,  4542204,  4544861,  4547523,
    4550196,  4552844,  4555492,  4558141,  4560804,  4563438,  4566061,
    4568706,  4571337,  4574015,  4576657,  4579285,  4581977,  4584687,
    4587326,  4589993,  4592654,  4595266,  4597877,  4600572,  4603201,
    4605817,  4608469,  4611140,  4613737,  4616385,  4619006,  4621593,
    4624232,  4626876,  4629508,  4632187,  4634797,  4637399,  4640031,
    4642678,  4645360,  4647919,  4650560,  4653231,  4655889,  4658586,
    4661190,  4663804,  4666451,  4669055,  4671705,  4674351,  4676997,
    4679633,  4682243,  4684949,  4687533,  4690161,  4692790,  4695463,
    4698103,  4700735,  4703363,  4706007,  4708643,  4711274,  4713900,
    4716608,  4719202,  4721853,  4724481,  4727184,  4729855,  4732496,
    4735168,  4737851,  4740486,  4743083,  4745721,  4748367,  4750950,
    4753627,  4756289,  4758913,  4761561,  4764205,  4766823,  4769430,
    4772013,  4774673,  4777296,  4779967,  4782597,  4785262,  4787905,
    4790546,  4793167,  4795770,  4798436,  4801064,  4803668,  4806333,
    4808985,  4811623,  4814267,  4816891,  4819529,  4822161,  4824805,
    4827436,  4830058,  4832685,  4835379,  4838000,  4840681,  4843322,
    4845982,  4848640,  4851212,  4853838,  4856492,  4859127,  4861763,
    4864388,  4867028,  4869676,  4872296,  4874854,  4877529,  4880180,
    4882798,  4885427,  4888078,  4890746,  4893365,  4896011,  4898673,
    4901286,  4903891,  4906512,  4909157,  4911785,  4914384,  4917033,
    4919690,  4922306,  4924919,  4927573,  4930213,  4932818,  4935488,
    4938140,  4940775,  4943379,  4946070,  4948680,  4951297,  4953911,
    4956558,  4959210,  4961878,  4964538,  4967185,  4969806,  4972410,
    4975039,  4977662,  4980311,  4982941,  4985647,  4988226,  4990898,
    4993516,  4996145,  4998802,  5001443,  5004057,  5006709,  5009406,
    5012065,  5014695,  5017340,  5019950,  5022572,  5025179,  5027802,
    5030447,  5033047,  5035681,  5038280,  5040863,  5043508,  5046095,
    5048766,  5051412,  5054025,  5056629,  5059278,  5061913,  5064512,
    5067205,  5069825,  5072492,  5075114,  5077659,  5080256,  5082860,
    5085500,  5088135,  5090728,  5093333,  5095989,  5098616,  5101203,
    5103826,  5106459,  5109090,  5111744,  5114362,  5116967,  5119591,
    5122214,  5124845,  5127515,  5130154,  5132783,  5135431,  5138076,
    5140731,  5143346,  5145981,  5148606,  5151275,  5153900,  5156547,
    5159150,  5161734,  5164342,  5166954,  5169574,  5172232,  5174885,
    5177522,  5180106,  5182723,  5185364,  5187966,  5190596,  5193213,
    5195881,  5198500,  5201126,  5203797,  5206415,  5209050,  5211713,
    5214289,  5216846,  5219488,  5222091,  5224741,  5227387,  5230075,
    5232642,  5235256,  5237883,  5240497,  5243171,  5245787,  5248349,
    5250964,  5253604,  5256295,  5258925,  5261560,  5264198,  5266812,
    5269432,  5272057,  5274678,  5277359,  5279981,  5282588,  5285176,
    5287825,  5290378,  5292984,  5295576,  5298144,  5300709,  5303300,
    5305965,  5308565,  5311160,  5313783,  5316423,  5319019,  5321597,
    5324214,  5326785,  5329410,  5332021,  5334623,  5337228,  5339868,
    5342497,  5345130,  5347796,  5350422,  5353090,  5355703,  5358368,
    5360987,  5363545,  5366148,  5368777,  5371412,  5374088,  5376687,
    5379310,  5381929,  5384561,  5387172,  5389785,  5392412,  5395046,
    5397629,  5400260,  5402887,  5405527,  5408176,  5410794,  5413434,
    5415999,  5418615,  5421235,  5423862,  5426485,  5429133,  5431730,
    5434359,  5436989,  5439576,  5442164,  5444785,  5447430,  5450050,
    5452630,  5455226,  5457874,  5460458,  5463064,  5465636,  5468292,
    5470840,  5473438,  5476040,  5478624,  5481234,  5483862,  5486492,
    5489062,  5491685,  5494277,  5496930,  5499560,  5502195,  5504849,
    5507484,  5510039,  5512631,  5515229,  5517813,  5520451,  5523148,
    5525740,  5528354,  5530960,  5533526,  5536136,  5538821,  5541485,
    5544171,  5546787,  5549334,  5551962,  5554594,  5557156,  5559794,
    5562401,  5564989,  5567668,  5570318,  5572922,  5575559,  5578173,
    5580735,  5583348,  5585968,  5588600,  5591257,  5593883,  5596537,
    5599126,  5601766,  5604343,  5606978,  5609544,  5612150,  5614795,
    5617364,  5619974,  5622604,  5625220,  5627890,  5630520,  5633085,
    5635731,  5638332,  5640958,  5643587,  5646179,  5648777,  5651328,
    5653955,  5656616,  5659237,  5661891,  5664467,  5667110,  5669724,
    5672315,  5674898,  5677516,  5680112,  5682698,  5685283,  5687873,
    5690537,  5693138,  5695725,  5698354,  5700962,  5703597,  5706173,
    5708793,  5711418,  5713948,  5716608,  5719236,  5721870,  5724432,
    5727030,  5729670,  5732291,  5734927,  5737555,  5740151,  5742760,
    5745303,  5747922,  5750484,  5753109,  5755700,  5758284,  5760903,
    5763488,  5766103,  5768742,  5771329,  5773921,  5776526,  5779099,
    5781662,  5784324,  5786983,  5789590,  5792263,  5794904,  5797482,
    5800089,  5802685,  5805349,  5807963,  5810588,  5813145,  5815758,
    5818375,  5820930,  5823533,  5826127,  5828742,  5831423,  5834055,
    5836688,  5839332,  5841893,  5844529,  5847110,  5849741,  5852352,
    5854947,  5857519,  5860154,  5862786,  5865406,  5868021,  5870662,
    5873255,  5875845,  5878520,  5881140,  5883729,  5886329,  5888952,
    5891561,  5894167,  5896791,  5899352,  5901946,  5904577,  5907199,
    5909822,  5912399,  5914980,  5917583,  5920157,  5922796,  5925412,
    5928032,  5930672,  5933314,  5935941,  5938528,  5941165,  5943777,
    5946380,  5949001,  5951600,  5954206,  5956845,  5959490,  5962107,
    5964740,  5967358,  5969954,  5972550,  5975142,  5977742,  5980358,
    5982939,  5985529,  5988135,  5990733,  5993379,  5995955,  5998500,
    6001091,  6003727,  6006283,  6008887,  6011523,  6014158,  6016757,
    6019332,  6021859,  6024475,  6027082,  6029692,  6032264,  6034853,
    6037496,  6040041,  6042691,  6045299,  6047914,  6050499,  6053126,
    6055662,  6058265,  6060852,  6063464,  6066107,  6068704,  6071358,
    6073902,  6076512,  6079117,  6081675,  6084293,  6086846,  6089462,
    6092066,  6094754,  6097313,  6099890,  6102471,  6105113,  6107732,
    6110282,  6112891,  6115533,  6118146,  6120762,  6123306,  6125905,
    6128580,  6131219,  6133813,  6136360,  6139005,  6141600,  6144218,
    6146820,  6149371,  6152008,  6154675,  6157271,  6159871,  6162461,
    6164976,  6167591,  6170168,  6172803,  6175450,  6178055,  6180645,
    6183213,  6185805,  6188462,  6191134,  6193761,  6196339,  6198883,
    6201446,  6204006,  6206615,  6209208,  6211825,  6214485,  6217047,
    6219685,  6222252,  6224827,  6227426,  6230025,  6232618,  6235254,
    6237903,  6240568,  6243137,  6245745,  6248383,  6250968,  6253594,
    6256157,  6258704,  6261229,  6263772,  6266353,  6268950,  6271545,
    6274153,  6276725,  6279295,  6281850,  6284431,  6287079,  6289703,
    6292248,  6294880,  6297458,  6300083,  6302647,  6305225,  6307854,
    6310423,  6313002,  6315578,  6318146,  6320783,  6323413,  6326011,
    6328577,  6331172,  6333770,  6336395,  6339009,  6341630,  6344208,
    6346739,  6349347,  6351927,  6354521,  6357116,  6359727,  6362295,
    6364935,  6367512,  6370124,  6372759,  6375330,  6377932,  6380538,
    6383126,  6385750,  6388317,  6390928,  6393566,  6396156,  6398760,
    6401309,  6403894,  6406444,  6409020,  6411621,  6414240,  6416840,
    6419444,  6421985,  6424585,  6427175,  6429774,  6432352,  6434905,
    6437478,  6440084,  6442694,  6445293,  6447930,  6450524,  6453111,
    6455682,  6458326,  6460917,  6463538,  6466171,  6468741,  6471304,
    6473882,  6476474,  6479075,  6481719,  6484300,  6486895,  6489472,
    6492070,  6494656,  6497314,  6499923,  6502519,  6505097,  6507692,
    6510279,  6512873,  6515451,  6518114,  6520675,  6523259,  6525868,
    6528444,  6531066,  6533690,  6536273,  6538887,  6541470,  6544021,
    6546672,  6549285,  6551864,  6554452,  6556996,  6559587,  6562188,
    6564770,  6567411,  6569951,  6572574,  6575116,  6577700,  6580260,
    6582892,  6585456,  6588087,  6590708,  6593326,  6595957,  6598515,
    6601071,  6603686,  6606273,  6608834,  6611498,  6614095,  6616698,
    6619295,  6621894,  6624418,  6627012,  6629605,  6632211,  6634763,
    6637327,  6639847,  6642444,  6645043,  6647598,  6650124,  6652723,
    6655351,  6657923,  6660525,  6663028,  6665670,  6668208,  6670804,
    6673402,  6676025,  6678603,  6681238,  6683806,  6686331,  6688966,
    6691555,  6694117,  6696711,  6699329,  6701946,  6704527,  6707200,
    6709795,  6712367,  6714983,  6717599,  6720189,  6722794,  6725391,
    6727968,  6730547,  6733134,  6735695,  6738207,  6740828,  6743394,
    6745968,  6748552,  6751153,  6753724,  6756299,  6758910,  6761489,
    6764062,  6766666,  6769185,  6771775,  6774395,  6776965,  6779497,
    6782076,  6784634,  6787249,  6789787,  6792400,  6795031,  6797654,
    6800239,  6802810,  6805406,  6807999,  6810601,  6813192,  6815770,
    6818374,  6820939,  6823539,  6826057,  6828648,  6831224,  6833809,
    6836379,  6838975,  6841545,  6844146,  6846743,  6849310,  6851866,
    6854427,  6857053,  6859666,  6862301,  6864928,  6867491,  6870031,
    6872597,  6875182,  6877737,  6880327,  6882924,  6885471,  6888050,
    6890595,  6893240,  6895824,  6898361,  6900909,  6903508,  6906086,
    6908592,  6911194,  6913799,  6916351,  6918938,  6921532,  6924153,
    6926760,  6929345,  6932010,  6934558,  6937122,  6939699,  6942266,
    6944833,  6947433,  6950048,  6952622,  6955229,  6957811,  6960447,
    6963003,  6965624,  6968229,  6970814,  6973374,  6975908,  6978553,
    6981142,  6983701,  6986303,  6988895,  6991452,  6994053,  6996636,
    6999239,  7001827,  7004386,  7006943,  7009509,  7012092,  7014637,
    7017247,  7019911,  7022468,  7025101,  7027733,  7030312,  7032873,
    7035446,  7038006,  7040537,  7043119,  7045744,  7048342,  7050888,
    7053483,  7056063,  7058671,  7061274,  7063885,  7066487,  7069099,
    7071649,  7074208,  7076794,  7079414,  7081992,  7084585,  7087182,
    7089730,  7092253,  7094829,  7097378,  7099975,  7102560,  7105136,
    7107734,  7110341,  7112923,  7115505,  7118105,  7120687,  7123329,
    7125909,  7128529,  7131104,  7133676,  7136261,  7138851,  7141412,
    7143963,  7146532,  7149099,  7151678,  7154306,  7156895,  7159502,
    7162172,  7164744,  7167291,  7169862,  7172477,  7175070,  7177687,
    7180299,  7182859,  7185447,  7188010,  7190543,  7193111,  7195725,
    7198306,  7200837,  7203410,  7206026,  7208623,  7211221,  7213777,
    7216339,  7218922,  7221467,  7224118,  7226696,  7229224,  7231835,
    7234448,  7237074,  7239661,  7242248,  7244831,  7247438,  7250010,
    7252624,  7255179,  7257777,  7260342,  7262872,  7265456,  7267970,
    7270545,  7273095,  7275708,  7278251,  7280851,  7283410,  7285994,
    7288560,  7291115,  7293745,  7296316,  7298848,  7301442,  7304018,
    7306655,  7309180,  7311705,  7314293,  7316887,  7319531,  7322112,
    7324659,  7327260,  7329881,  7332442,  7335022,  7337604,  7340210,
    7342739,  7345280,  7347817,  7350378,  7352945,  7355504,  7358025,
    7360615,  7363210,  7365832,  7368429,  7371013,  7373605,  7376145,
    7378732,  7381276,  7383811,  7386365,  7388933,  7391502,  7394032,
    7396642,  7399245,  7401866,  7404457,  7406982,  7409538,  7412102,
    7414691,  7417288,  7419884,  7422441,  7424989,  7427522,  7430101,
    7432639,  7435216,  7437740,  7440294,  7442912,  7445516,  7448114,
    7450684,  7453261,  7455841,  7458445,  7461027,  7463635,  7466198,
    7468787,  7471320,  7473930,  7476552,  7479118,  7481641,  7484264,
    7486781,  7489342,  7491952,  7494521,  7497063,  7499688,  7502254,
    7504815,  7507392,  7509988,  7512553,  7515087,  7517707,  7520308,
    7522824,  7525392,  7527945,  7530543,  7533105,  7535700,  7538260,
    7540804,  7543418,  7545943,  7548535,  7551130,  7553729,  7556313,
    7558844,  7561435,  7563980,  7566505,  7569080,  7571641,  7574170,
    7576783,  7579338,  7581897,  7584422,  7587022,  7589577,  7592151,
    7594705,  7597276,  7599794,  7602390,  7604973,  7607619,  7610137,
    7612748,  7615269,  7617858,  7620416,  7622960,  7625549,  7628196,
    7630753,  7633277,  7635834,  7638354,  7640910,  7643496,  7646121,
    7648660,  7651279,  7653833,  7656431,  7659011,  7661580,  7664134,
    7666612,  7669193,  7671776,  7674356,  7676915,  7679488,  7682031,
    7684595,  7687146,  7689731,  7692293,  7694861,  7697419,  7700031,
    7702574,  7705205,  7707783,  7710348,  7712918,  7715474,  7718028,
    7720597,  7723207,  7725778,  7728305,  7730889,  7733442,  7736038,
    7738641,  7741178,  7743670,  7746199,  7748766,  7751407,  7753967,
    7756540,  7759095,  7761686,  7764213,  7766793,  7769379,  7771905,
    7774461,  7777035,  7779545,  7782119,  7784671,  7787226,  7789834,
    7792385,  7795028,  7797627,  7800194,  7802758,  7805346,  7807903,
    7810459,  7813000,  7815577,  7818155,  7820761,  7823285,  7825842,
    7828445,  7830988,  7833550,  7836167,  7838714,  7841312,  7843890,
    7846422,  7848885,  7851434,  7854000,  7856583,  7859172,  7861776,
    7864364,  7866909,  7869478,  7872018,  7874591,  7877131,  7879768,
    7882314,  7884851,  7887428,  7890024,  7892632,  7895233,  7897844,
    7900429,  7902975,  7905546,  7908066,  7910582,  7913125,  7915728,
    7918312,  7920913,  7923470,  7926037,  7928634,  7931211,  7933766,
    7936281,  7938828,  7941378,  7943902,  7946432,  7949032,  7951602,
    7954217,  7956760,  7959316,  7961868,  7964451,  7967003,  7969567,
    7972124,  7974694,  7977293,  7979866,  7982413,  7985018,  7987569,
    7990128,  7992722,  7995266,  7997861,  8000394,  8002935,  8005473,
    8008047,  8010615,  8013200,  8015753,  8018323,  8020862,  8023413,
    8025983,  8028499,  8031030,  8033583,  8036158,  8038758,  8041400,
    8043966,  8046482,  8049029,  8051591,  8054132,  8056748,  8059305,
    8061849,  8064377,  8066944,  8069508,  8072033,  8074668,  8077206,
    8079782,  8082323,  8084914,  8087510,  8090092,  8092568,  8095135,
    8097678,  8100189,  8102726,  8105256,  8107767,  8110337,  8112936,
    8115467,  8118011,  8120631,  8123161,  8125719,  8128340,  8130913,
    8133510,  8136062,  8138640,  8141221,  8143766,  8146315,  8148899,
    8151475,  8154006,  8156553,  8159149,  8161682,  8164237,  8166798,
    8169333,  8171871,  8174471,  8177049,  8179597,  8182152,  8184715,
    8187265,  8189803,  8192380,  8194955,  8197509,  8200053,  8202628,
    8205178,  8207747,  8210300,  8212897,  8215438,  8218009,  8220555,
    8223077,  8225651,  8228237,  8230810,  8233377,  8235958,  8238572,
    8241140,  8243741,  8246301,  8248881,  8251454,  8254026,  8256613,
    8259131,  8261667,  8264240,  8266830,  8269356,  8271916,  8274486,
    8277018,  8279614,  8282184,  8284713,  8287297,  8289884,  8292469,
    8294982,  8297520,  8300046,  8302603,  8305158,  8307709,  8310301,
    8312863,  8315381,  8317950,  8320474,  8323008,  8325584,  8328111,
    8330688,  8333340,  8335893,  8338506,  8341000,  8343633,  8346208,
    8348756,  8351317,  8353848,  8356348,  8358942,  8361506,  8364041,
    8366629,  8369178,  8371727,  8374313,  8376865,  8379427,  8382007,
    8384577,  8387076,  8389647,  8392215,  8394724,  8397278,  8399803,
    8402346,  8404899,  8407510,  8410082,  8412570,  8415078,  8417605,
    8420133,  8422700,  8425218,  8427789,  8430366,  8432906,  8435454,
    8438006,  8440574,  8443171,  8445789,  8448389,  8450958,  8453472,
    8456041,  8458625,  8461216,  8463754,  8466289,  8468858,  8471319,
    8473925,  8476523,  8479059,  8481588,  8484127,  8486680,  8489226,
    8491766,  8494394,  8496926,  8499472,  8502032,  8504585,  8507180,
    8509733,  8512277,  8514802,  8517340,  8519922,  8522499,  8525047,
    8527661,  8530185,  8532813,  8535326,  8537855,  8540382,  8542924,
    8545505,  8548084,  8550639,  8553179,  8555754,  8558303,  8560840,
    8563373,  8565932,  8568476,  8571009,  8573558,  8576129,  8578700,
    8581245,  8583783,  8586364,  8588878,  8591480,  8593985,  8596518,
    8599014,  8601559,  8604070,  8606632,  8609185,  8611722,  8614281,
    8616821,  8619396,  8621972,  8624520,  8627083,  8629687,  8632228,
    8634820,  8637401,  8639975,  8642529,  8645006,  8647552,  8650102,
    8652633,  8655215,  8657758,  8660316,  8662862,  8665420,  8667979,
    8670495,  8673051,  8675543,  8678125,  8680642,  8683221,  8685758,
    8688296,  8690864,  8693382,  8695939,  8698526,  8701080,  8703658,
    8706192,  8708727,  8711244,  8713827,  8716380,  8718851,  8721433,
    8723964,  8726530,  8729046,  8731683,  8734269,  8736820,  8739371,
    8741863,  8744351,  8746792,  8749195,  8751613,  8754043,  8756450,
    8758825,  8761189,  8763587,  8765964,  8768316,  8770661,  8773049,
    8775398,  8777724,  8780054,  8782359,  8784673,  8786971,  8789292,
    8791635,  8793924,  8796134,  8798404,  8800669,  8802939,  8805215,
    8807447,  8809728,  8811971,  8814177,  8816361,  8818554,  8820757,
    8823014,  8825261,  8827454,  8829633,  8831850,  8834046,  8836190,
    8838428,  8840589,  8842781,  8844940,  8847071,  8849197,  8851337,
    8853456,  8855611,  8857740,  8859913,  8862035,  8864198,  8866342,
    8868443,  8870590,  8872726,  8874831,  8876933,  8879005,  8881114,
    8883183,  8885262,  8887372,  8889412,  8891463,  8893523,  8895630,
    8897658,  8899699,  8901773,  8903853,  8905924,  8907930,  8909989,
    8912075,  8914151,  8916230,  8918252,  8920337,  8922379,  8924389,
    8926440,  8928485,  8930560,  8932598,  8934580,  8936571,  8938563,
    8940536,  8942557,  8944601,  8946593,  8948585,  8950528,  8952560,
    8954546,  8956538,  8958566,  8960513,  8962518,  8964461,  8966423,
    8968388,  8970339,  8972326,  8974323,  8976301,  8978296,  8980265,
    8982190,  8984132,  8986067,  8987976,  8989948,  8991871,  8993783,
    8995669,  8997620,  8999577,  9001473,  9003341,  9005293,  9007221,
    9009152,  9011073,  9012936,  9014809,  9016721,  9018620,  9020474,
    9022374,  9024241,  9026157,  9028032,  9029930,  9031866,  9033772,
    9035661,  9037586,  9039467,  9041364,  9043180,  9045060,  9046940,
    9048794,  9050666,  9052568,  9054436,  9056290,  9058103,  9059982,
    9061839,  9063654,  9065482,  9067332,  9069156,  9070995,  9072854,
    9074710,  9076538,  9078414,  9080271,  9082097,  9083905,  9085691,
    9087560,  9089394,  9091201,  9092982,  9094783,  9096580,  9098406,
    9100258,  9102078,  9103907,  9105665,  9107458,  9109295,  9111085,
    9112915,  9114700,  9116437,  9118193,  9120020,  9121779,  9123563,
    9125264,  9127013,  9128834,  9130591,  9132334,  9134113,  9135906,
    9137697,  9139463,  9141237,  9142976,  9144739,  9146475,  9148248,
    9150016,  9151769,  9153580,  9155322,  9157052,  9158759,  9160524,
    9162176,  9163939,  9165646,  9167425,  9169101,  9170837,  9172568,
    9174269,  9175957,  9177720,  9179425,  9181169,  9182933,  9184652,
    9186339,  9187991,  9189701,  9191409,  9193153,  9194846,  9196538,
    9198218,  9199861,  9201556,  9203218,  9204912,  9206622,  9208255,
    9210023,  9211680,  9213307,  9214972,  9216661,  9218305,  9219939,
    9221587,  9223257,  9224953,  9226596,  9228253,  9229948,  9231613,
    9233252,  9234857,  9236534,  9238223,  9239891,  9241536,  9243233,
    9244882,  9246557,  9248185,  9249863,  9251480,  9253069,  9254721,
    9256358,  9257980,  9259629,  9261218,  9262841,  9264499,  9266126,
    9267742,  9269372,  9270964,  9272611,  9274199,  9275860,  9277459,
    9279058,  9280715,  9282271,  9283903,  9285518,  9287181,  9288749,
    9290347,  9291909,  9293521,  9295101,  9296673,  9298250,  9299861,
    9301433,  9303051,  9304620,  9306223,  9307807,  9309418,  9311034,
    9312584,  9314171,  9315756,  9317297,  9318899,  9320469,  9322047,
    9323636,  9325176,  9326719,  9328280,  9329830,  9331441,  9333000,
    9334573,  9336102,  9337619,  9339222,  9340776,  9342286,  9343837,
    9345382,  9346924,  9348483,  9350035,  9351608,  9353141,  9354665,
    9356214,  9357765,  9359330,  9360881,  9362407,  9363986,  9365544,
    9367049,  9368571,  9370066,  9371598,  9373136,  9374708,  9376201,
    9377705,  9379202,  9380735,  9382259,  9383773,  9385330,  9386861,
    9388367,  9389912,  9391411,  9392924,  9394436,  9395903,  9397386,
    9398893,  9400389,  9401864,  9403363,  9404843,  9406303,  9407792,
    9409289,  9410791,  9412253,  9413751,  9415240,  9416719,  9418165,
    9419618,  9421105,  9422552,  9423994,  9425450,  9426963,  9428496,
    9429950,  9431424,  9432917,  9434383,  9435909,  9437359,  9438840,
    9440340,  9441752,  9443236,  9444731,  9446175,  9447646,  9449138,
    9450617,  9452092,  9453507,  9454961,  9456377,  9457827,  9459279,
    9460719,  9462160,  9463624,  9465054,  9466522,  9467929,  9469379,
    9470805,  9472237,  9473674,  9475122,  9476586,  9478030,  9479448,
    9480872,  9482271,  9483747,  9485133,  9486642,  9488058,  9489484,
    9490930,  9492365,  9493798,  9495191,  9496575,  9498025,  9499453,
    9500880,  9502250,  9503671,  9505028,  9506449,  9507815,  9509245,
    9510654,  9512049,  9513459,  9514834,  9516193,  9517552,  9518979,
    9520332,  9521728,  9523096,  9524515,  9525877,  9527274,  9528675,
    9530099,  9531488,  9532842,  9534254,  9535640,  9537005,  9538439,
    9539810,  9541160,  9542547,  9543986,  9545373,  9546728,  9548082,
    9549449,  9550794,  9552143,  9553454,  9554830,  9556162,  9557544,
    9558902,  9560282,  9561654,  9563034,  9564415,  9565772,  9567094,
    9568438,  9569786,  9571146,  9572511,  9573868,  9575224,  9576602,
    9577959,  9579252,  9580565,  9581909,  9583221,  9584515,  9585852,
    9587206,  9588547,  9589857,  9591234,  9592558,  9593914,  9595242,
    9596580,  9597855,  9599192,  9600493,  9601853,  9603150,  9604491,
    9605827,  9607160,  9608478,  9609817,  9611121,  9612411,  9613731,
    9615027,  9616333,  9617643,  9618969,  9620230,  9621545,  9622891,
    9624176,  9625501,  9626832,  9628129,  9629417,  9630708,  9631980,
    9633302,  9634598,  9635897,  9637221,  9638582,  9639870,  9641165,
    9642451,  9643744,  9645061,  9646354,  9647577,  9648869,  9650144,
    9651439,  9652704,  9654009,  9655308,  9656608,  9657890,  9659176,
    9660454,  9661761,  9663035,  9664286,  9665580,  9666850,  9668132,
    9669401,  9670655,  9671953,  9673191,  9674446,  9675683,  9676916,
    9678195,  9679456,  9680717,  9681980,  9683224,  9684482,  9685719,
    9686992,  9688243,  9689514,  9690734,  9691968,  9693246,  9694568,
    9695790,  9697060,  9698306,  9699535,  9700782,  9701954,  9703179,
    9704395,  9705617,  9706860,  9708139,  9709320,  9710560,  9711798,
    9712992,  9714175,  9715408,  9716674,  9717887,  9719131,  9720357,
    9721597,  9722825,  9724031,  9725247,  9726431,  9727715,  9728896,
    9730144,  9731347,  9732559,  9733768,  9735006,  9736215,  9737398,
    9738595,  9739796,  9740963,  9742208,  9743410,  9744582,  9745754,
    9746979,  9748191,  9749403,  9750612,  9751823,  9753058,  9754258,
    9755529,  9756729,  9757902,  9759080,  9760229,  9761466,  9762649,
    9763845,  9765076,  9766308,  9767506,  9768717,  9769917,  9771136,
    9772322,  9773493,  9774662,  9775862,  9777055,  9778239,  9779390,
    9780558,  9781725,  9782863,  9784049,  9785209,  9786373,  9787564,
    9788741,  9789870,  9791040,  9792209,  9793365,  9794536,  9795697,
    9796812,  9797946,  9799114,  9800249,  9801398,  9802558,  9803694,
    9804855,  9805980,  9807165,  9808315,  9809508,  9810636,  9811819,
    9813000,  9814135,  9815294,  9816470,  9817566,  9818716,  9819884,
    9821050,  9822174,  9823335,  9824456,  9825624,  9826793,  9827929,
    9828988,  9830153,  9831305,  9832456,  9833522,  9834685,  9835819,
    9836968,  9838141,  9839258,  9840376,  9841535,  9842707,  9843848,
    9844954,  9846066,  9847201,  9848308,  9849435,  9850522,  9851682,
    9852794,  9853941,  9855091,  9856198,  9857294,  9858394,  9859550,
    9860649,  9861712,  9862815,  9863931,  9865041,  9866172,  9867252,
    9868363,  9869455,  9870534,  9871651,  9872767,  9873909,  9875006,
    9876094,  9877179,  9878301,  9879358,  9880475,  9881603,  9882709,
    9883802,  9884893,  9885997,  9887073,  9888174,  9889262,  9890338,
    9891409,  9892507,  9893591,  9894650,  9895746,  9896830,  9897922,
    9898974,  9900074,  9901186,  9902285,  9903345,  9904434,  9905562,
    9906651,  9907774,  9908814,  9909873,  9910943,  9912014,  9913046,
    9914116,  9915157,  9916227,  9917302,  9918425,  9919493,  9920513,
    9921574,  9922631,  9923735,  9924799,  9925912,  9926967,  9928018,
    9929075,  9930136,  9931183,  9932269,  9933343,  9934431,  9935508,
    9936569,  9937667,  9938722,  9939715,  9940756,  9941822,  9942883,
    9943953,  9945017,  9946077,  9947149,  9948219,  9949282,  9950281,
    9951367,  9952374,  9953448,  9954478,  9955483,  9956522,  9957514,
    9958561,  9959600,  9960598,  9961653,  9962713,  9963741,  9964779,
    9965828,  9966875,  9967912,  9968902,  9969934,  9970930,  9971963,
    9972965,  9973952,  9974971,  9976021,  9977044,  9978025,  9979036,
    9980013,  9981024,  9982049,  9983129,  9984181,  9985164,  9986182,
    9987204,  9988172,  9989235,  9990219,  9991219,  9992216,  9993257,
    9994310,  9995290,  9996286,  9997341,  9998325,  9999299,  10000316,
    10001344, 10002360, 10003376, 10004370, 10005387, 10006396, 10007401,
    10008432, 10009421, 10010346, 10011385, 10012392, 10013350, 10014333,
    10015323, 10016305, 10017330, 10018321, 10019328, 10020316, 10021282,
    10022315, 10023317, 10024295, 10025242, 10026179, 10027197, 10028189,
    10029225, 10030203, 10031195, 10032131, 10033129, 10034084, 10035081,
    10036062, 10036997, 10037972, 10038957, 10039954, 10040895, 10041850,
    10042841, 10043778, 10044746, 10045695, 10046687, 10047676, 10048625,
    10049585, 10050529, 10051507, 10052484, 10053453, 10054441, 10055422,
    10056365, 10057335, 10058328, 10059277, 10060236, 10061200, 10062157,
    10063106, 10064051, 10064985, 10065970, 10066919, 10067891, 10068831,
    10069813, 10070756, 10071722, 10072638, 10073554, 10074530, 10075496,
    10076469, 10077388, 10078344, 10079309, 10080235, 10081164, 10082101,
    10083050, 10084028, 10084998, 10085971, 10086882, 10087742, 10088708,
    10089628, 10090601, 10091530, 10092514, 10093437, 10094354, 10095236,
    10096162, 10097100, 10098027, 10098968, 10099914, 10100849, 10101748,
    10102663, 10103556, 10104508, 10105418, 10106351, 10107263, 10108144,
    10109063, 10109962, 10110877, 10111774, 10112690, 10113591, 10114501,
    10115448, 10116365, 10117228, 10118124, 10119051, 10119955, 10120841,
    10121790, 10122705, 10123656, 10124533, 10125437, 10126380, 10127326,
    10128265, 10129176, 10130078, 10131001, 10131892, 10132795, 10133656,
    10134554, 10135446, 10136371, 10137254, 10138169, 10139077, 10139973,
    10140874, 10141711, 10142652, 10143560, 10144442, 10145367, 10146276,
    10147147, 10148079, 10148934, 10149848, 10150751, 10151657, 10152540,
    10153420, 10154256, 10155170, 10156059, 10156913, 10157796, 10158647,
    10159543, 10160380, 10161229, 10162092, 10163002, 10163864, 10164738,
    10165625, 10166498, 10167401, 10168249, 10169120, 10169954, 10170867,
    10171718, 10172557, 10173370, 10174244, 10175133, 10176000, 10176864,
    10177785, 10178656, 10179543, 10180420, 10181269, 10182151, 10183003,
    10183856, 10184741, 10185621, 10186466, 10187325, 10188190, 10189061,
    10189947, 10190826, 10191629, 10192439, 10193319, 10194208, 10195061,
    10195935, 10196790, 10197640, 10198461, 10199325, 10200197, 10201026,
    10201879, 10202731, 10203572, 10204413, 10205245, 10206136, 10206994,
    10207850, 10208729, 10209566, 10210404, 10211237, 10212113, 10212968,
    10213845, 10214670, 10215501, 10216350, 10217153, 10218008, 10218874,
    10219706, 10220538, 10221365, 10222228, 10223074, 10223882, 10224757,
    10225560, 10226394, 10227234, 10228076, 10228899, 10229736, 10230588,
    10231372, 10232175, 10232960, 10233812, 10234624, 10235494, 10236342,
    10237144, 10237980, 10238773, 10239587, 10240417, 10241271, 10242077,
    10242902, 10243726, 10244559, 10245383, 10246202, 10247010, 10247832,
    10248579, 10249414, 10250257, 10251061, 10251854, 10252663, 10253461,
    10254256, 10255068, 10255866, 10256651, 10257430, 10258231, 10259024,
    10259830, 10260617, 10261412, 10262207, 10262996, 10263773, 10264574,
    10265346, 10266107, 10266940, 10267741, 10268559, 10269300, 10270084,
    10270903, 10271728, 10272467, 10273241, 10274057, 10274856, 10275607,
    10276465, 10277277, 10278037, 10278807, 10279539, 10280311, 10281123,
    10281857, 10282678, 10283499, 10284299, 10285083, 10285876, 10286647,
    10287433, 10288213, 10288999, 10289793, 10290568, 10291347, 10292080,
    10292874, 10293670, 10294408, 10295242, 10296018, 10296772, 10297499,
    10298300, 10299063, 10299842, 10300611, 10301397, 10302166, 10302946,
    10303684, 10304485, 10305304, 10306049, 10306812, 10307560, 10308302,
    10309067, 10309839, 10310642, 10311441, 10312203, 10312954, 10313696,
    10314503, 10315274, 10316037, 10316797, 10317594, 10318357, 10319102,
    10319874, 10320634, 10321403, 10322151, 10322894, 10323644, 10324407,
    10325163, 10325904, 10326698, 10327414, 10328189, 10328951, 10329710,
    10330462, 10331164, 10331901, 10332674, 10333391, 10334157, 10334918,
    10335663, 10336382, 10337093, 10337821, 10338577, 10339275, 10340021,
    10340783, 10341557, 10342302, 10343013, 10343762, 10344482, 10345237,
    10345954, 10346671, 10347393, 10348121, 10348830, 10349554, 10350271,
    10351002, 10351745, 10352466, 10353180, 10353935, 10354663, 10355373,
    10356115, 10356813, 10357512, 10358265, 10359002, 10359737, 10360423,
    10361154, 10361856, 10362605, 10363298, 10364003, 10364755, 10365483,
    10366182, 10366893, 10367593, 10368310, 10369054, 10369767, 10370453,
    10371137, 10371855, 10372585, 10373293, 10373979, 10374704, 10375449,
    10376210, 10376921, 10377613, 10378316, 10379049, 10379739, 10380455,
    10381229, 10381940, 10382643, 10383371, 10384045, 10384765, 10385475,
    10386168, 10386865, 10387562, 10388264, 10388979, 10389667, 10390359,
    10391035, 10391756, 10392455, 10393175, 10393846, 10394565, 10395291,
    10395983, 10396653, 10397353, 10398048, 10398713, 10399441, 10400106,
    10400850, 10401551, 10402253, 10402954, 10403628, 10404309, 10404985,
    10405694, 10406386, 10407081, 10407774, 10408445, 10409133, 10409805,
    10410474, 10411185, 10411841, 10412536, 10413271, 10413933, 10414618,
    10415314, 10416002, 10416686, 10417361, 10418066, 10418752, 10419413,
    10420053, 10420714, 10421408, 10422099, 10422771, 10423418, 10424067,
    10424778, 10425419, 10426100, 10426759, 10427449, 10428107, 10428771,
    10429436, 10430097, 10430798, 10431455, 10432133, 10432801, 10433487,
    10434163, 10434834, 10435463, 10436137, 10436822, 10437473, 10438156,
    10438829, 10439460, 10440133, 10440797, 10441453, 10442138, 10442792,
    10443426, 10444036, 10444691, 10445347, 10446032, 10446687, 10447360,
    10448012, 10448655, 10449322, 10449980, 10450618, 10451299, 10451942,
    10452589, 10453238, 10453856, 10454502, 10455137, 10455760, 10456434,
    10457079, 10457721, 10458394, 10459006, 10459660, 10460282, 10460927,
    10461570, 10462223, 10462898, 10463500, 10464160, 10464765, 10465402,
    10466021, 10466660, 10467305, 10467962, 10468583, 10469240, 10469863,
    10470494, 10471145, 10471771, 10472422, 10473062, 10473680, 10474315,
    10474979, 10475592, 10476215, 10476811, 10477468, 10478109, 10478734,
    10479346, 10479999, 10480590, 10481220, 10481822, 10482459, 10483118,
    10483722, 10484368, 10484986, 10485592, 10486229, 10486888, 10487547,
    10488156, 10488763, 10489377, 10490023, 10490632, 10491281, 10491934,
    10492516, 10493156, 10493753, 10494386, 10494996, 10495597, 10496211,
    10496836, 10497441, 10498059, 10498674, 10499327, 10499945, 10500526,
    10501115, 10501730, 10502324, 10502933, 10503464, 10504051, 10504678,
    10505249, 10505856, 10506460, 10507056, 10507631, 10508290, 10508901,
    10509468, 10510049, 10510644, 10511236, 10511899, 10512478, 10513096,
    10513674, 10514290, 10514893, 10515496, 10516054, 10516652, 10517236,
    10517840, 10518439, 10519022, 10519663, 10520271, 10520893, 10521454,
    10522045, 10522620, 10523212, 10523834, 10524422, 10525031, 10525608,
    10526235, 10526842, 10527398, 10527989, 10528572, 10529171, 10529776,
    10530401, 10530972, 10531531, 10532142, 10532771, 10533362, 10533953,
    10534504, 10535111, 10535702, 10536240, 10536880, 10537468, 10538084,
    10538652, 10539254, 10539817, 10540388, 10540925, 10541524, 10542101,
    10542679, 10543239, 10543812, 10544402, 10545004, 10545581, 10546162,
    10546718, 10547266, 10547856, 10548451, 10548993, 10549584, 10550142,
    10550727, 10551317, 10551890, 10552489, 10553035, 10553584, 10554147,
    10554754, 10555337, 10555895, 10556484, 10557028, 10557583, 10558137,
    10558702, 10559262, 10559806, 10560323, 10560883, 10561433, 10561940,
    10562536, 10563064, 10563636, 10564202, 10564768, 10565345, 10565889,
    10566452, 10567007, 10567589, 10568123, 10568654, 10569193, 10569781,
    10570277, 10570813, 10571331, 10571889, 10572432, 10573006, 10573573,
    10574135, 10574686, 10575246, 10575777, 10576326, 10576855, 10577387,
    10577887, 10578416, 10578963, 10579499, 10580020, 10580541, 10581057,
    10581560, 10582094, 10582613, 10583152, 10583691, 10584206, 10584756,
    10585267, 10585826, 10586396, 10586965, 10587515, 10588063, 10588572,
    10589112, 10589648, 10590189, 10590695, 10591248, 10591804, 10592319,
    10592858, 10593383, 10593913, 10594415, 10594938, 10595452, 10595999,
    10596500, 10597037, 10597578, 10598103, 10598636, 10599173, 10599711,
    10600229, 10600782, 10601302, 10601873, 10602386, 10602929, 10603459,
    10603977, 10604539, 10605062, 10605594, 10606135, 10606629, 10607151,
    10607689, 10608233, 10608743, 10609243, 10609766, 10610281, 10610747,
    10611246, 10611801, 10612301, 10612794, 10613297, 10613805, 10614301,
    10614815, 10615304, 10615812, 10616313, 10616813, 10617351, 10617874,
    10618381, 10618880, 10619393, 10619913, 10620400, 10620908, 10621402,
    10621910, 10622438, 10622938, 10623464, 10623985, 10624494, 10624989,
    10625495, 10626042, 10626538, 10627035, 10627496, 10628011, 10628500,
    10628988, 10629459, 10629990, 10630456, 10630945, 10631433, 10631942,
    10632456, 10632954, 10633458, 10633940, 10634443, 10634927, 10635451,
    10635930, 10636393, 10636898, 10637357, 10637858, 10638361, 10638850,
    10639365, 10639842, 10640310, 10640792, 10641261, 10641734, 10642196,
    10642675, 10643139, 10643664, 10644142, 10644634, 10645150, 10645635,
    10646116, 10646585, 10647094, 10647568, 10648056, 10648554, 10649066,
    10649534, 10650046, 10650512, 10650971, 10651441, 10651929, 10652437,
    10652926, 10653397, 10653883, 10654346, 10654804, 10655268, 10655762,
    10656221, 10656709, 10657200, 10657688, 10658147, 10658637, 10659099,
    10659552, 10660006, 10660467, 10660924, 10661370, 10661855, 10662346,
    10662811, 10663294, 10663740, 10664185, 10664638, 10665109, 10665586,
    10666044, 10666516, 10666985, 10667456, 10667889, 10668370, 10668846,
    10669294, 10669759, 10670185, 10670650, 10671107, 10671573, 10672038,
    10672529, 10672998, 10673460, 10673892, 10674335, 10674784, 10675223,
    10675697, 10676134, 10676603, 10677032, 10677529, 10677981, 10678446,
    10678885, 10679381, 10679830, 10680266, 10680720, 10681166, 10681616,
    10682093, 10682569, 10683031, 10683473, 10683949, 10684389, 10684802,
    10685235, 10685712, 10686154, 10686598, 10687052, 10687465, 10687920,
    10688325, 10688768, 10689224, 10689657, 10690090, 10690541, 10690958,
    10691396, 10691828, 10692285, 10692725, 10693167, 10693635, 10694095,
    10694497, 10694952, 10695402, 10695818, 10696272, 10696726, 10697176,
    10697628, 10698050, 10698470, 10698897, 10699361, 10699789, 10700264,
    10700698, 10701154, 10701599, 10701998, 10702439, 10702859, 10703279,
    10703678, 10704126, 10704553, 10704961, 10705375, 10705822, 10706236,
    10706656, 10707074, 10707513, 10707967, 10708387, 10708813, 10709209,
    10709621, 10710055, 10710478, 10710905, 10711356, 10711772, 10712168,
    10712569, 10713007, 10713380, 10713822, 10714251, 10714698, 10715098,
    10715486, 10715916, 10716343, 10716771, 10717186, 10717577, 10717990,
    10718449, 10718867, 10719278, 10719688, 10720117, 10720538, 10720951,
    10721371, 10721766, 10722158, 10722582, 10722974, 10723379, 10723803,
    10724196, 10724612, 10725035, 10725457, 10725875, 10726295, 10726716,
    10727124, 10727558, 10727960, 10728366, 10728782, 10729193, 10729579,
    10729988, 10730387, 10730816, 10731208, 10731613, 10732010, 10732421,
    10732814, 10733234, 10733643, 10734049, 10734446, 10734840, 10735233,
    10735621, 10735999, 10736372, 10736816, 10737210, 10737624, 10738057,
    10738463, 10738875, 10739271, 10739651, 10740028, 10740449, 10740805,
    10741202, 10741586, 10741977, 10742372, 10742783, 10743156, 10743571,
    10743946, 10744332, 10744732, 10745123, 10745509, 10745921, 10746311,
    10746704, 10747081, 10747471, 10747865, 10748257, 10748637, 10748983,
    10749375, 10749755, 10750180, 10750558, 10750952, 10751331, 10751733,
    10752130, 10752521, 10752907, 10753322, 10753712, 10754086, 10754464,
    10754838, 10755207, 10755557, 10755945, 10756311, 10756689, 10757047,
    10757412, 10757789, 10758173, 10758555, 10758910, 10759284, 10759651,
    10760047, 10760409, 10760778, 10761161, 10761528, 10761917, 10762290,
    10762681, 10763079, 10763456, 10763814, 10764193, 10764587, 10764964,
    10765319, 10765708, 10766062, 10766433, 10766789, 10767165, 10767513,
    10767853, 10768213, 10768578, 10768955, 10769335, 10769702, 10770047,
    10770451, 10770823, 10771180, 10771529, 10771874, 10772215, 10772596,
    10772960, 10773313, 10773654, 10774011, 10774383, 10774761, 10775141,
    10775503, 10775868, 10776238, 10776583, 10776938, 10777298, 10777677,
    10778017, 10778414, 10778753, 10779124, 10779494, 10779866, 10780221,
    10780574, 10780924, 10781268, 10781637, 10782012, 10782345, 10782661,
    10783001, 10783350, 10783695, 10784057, 10784406, 10784730, 10785091,
    10785427, 10785780, 10786136, 10786480, 10786843, 10787155, 10787500,
    10787820, 10788184, 10788518, 10788899, 10789251, 10789621, 10789969,
    10790314, 10790657, 10791012, 10791380, 10791733, 10792087, 10792438,
    10792784, 10793094, 10793437, 10793768, 10794103, 10794437, 10794805,
    10795114, 10795466, 10795810, 10796136, 10796474, 10796818, 10797150,
    10797503, 10797827, 10798150, 10798486, 10798818, 10799171, 10799487,
    10799813, 10800159, 10800494, 10800842, 10801202, 10801541, 10801906,
    10802247, 10802585, 10802871, 10803203, 10803550, 10803854, 10804168,
    10804492, 10804810, 10805155, 10805491, 10805805, 10806131, 10806466,
    10806780, 10807096, 10807434, 10807776, 10808081, 10808385, 10808717,
    10809032, 10809343, 10809660, 10809987, 10810308, 10810624, 10810920,
    10811225, 10811559, 10811885, 10812190, 10812485, 10812794, 10813114,
    10813442, 10813760, 10814070, 10814396, 10814729, 10815036, 10815342,
    10815662, 10815971, 10816288, 10816607, 10816907, 10817238, 10817532,
    10817862, 10818166, 10818484, 10818800, 10819121, 10819434, 10819741,
    10820064, 10820332, 10820649, 10820954, 10821286, 10821591, 10821905,
    10822216, 10822514, 10822827, 10823151, 10823461, 10823773, 10824060,
    10824342, 10824654, 10824966, 10825277, 10825572, 10825890, 10826204,
    10826487, 10826764, 10827093, 10827377, 10827662, 10827973, 10828264,
    10828570, 10828884, 10829171, 10829473, 10829764, 10830077, 10830362,
    10830672, 10830962, 10831274, 10831566, 10831867, 10832155, 10832452,
    10832736, 10833040, 10833325, 10833603, 10833913, 10834208, 10834479,
    10834788, 10835053, 10835358, 10835669, 10835966, 10836255, 10836554,
    10836830, 10837118, 10837418, 10837715, 10837992, 10838254, 10838549,
    10838842, 10839141, 10839403, 10839679, 10839962, 10840248, 10840543,
    10840811, 10841107, 10841415, 10841697, 10841996, 10842241, 10842533,
    10842815, 10843096, 10843393, 10843646, 10843921, 10844214, 10844520,
    10844820, 10845060, 10845357, 10845640, 10845907, 10846216, 10846494,
    10846765, 10847034, 10847315, 10847600, 10847877, 10848150, 10848415,
    10848688, 10848955, 10849237, 10849505, 10849777, 10850075, 10850360,
    10850628, 10850897, 10851154, 10851452, 10851719, 10851960, 10852205,
    10852505, 10852771, 10853040, 10853313, 10853592, 10853844, 10854129,
    10854390, 10854643, 10854886, 10855179, 10855433, 10855742, 10855998,
    10856277, 10856529, 10856821, 10857081, 10857341, 10857596, 10857863,
    10858142, 10858424, 10858668, 10858927, 10859194, 10859452, 10859710,
    10860004, 10860257, 10860538, 10860810, 10861056, 10861309, 10861579,
    10861847, 10862112, 10862377, 10862646, 10862880, 10863155, 10863395,
    10863653, 10863908, 10864174, 10864412, 10864687, 10864939, 10865182,
    10865430, 10865694, 10865918, 10866184, 10866436, 10866682, 10866936,
    10867187, 10867446, 10867685, 10867925, 10868196, 10868439, 10868708,
    10868957, 10869197, 10869446, 10869700, 10869945, 10870210, 10870462,
    10870693, 10870926, 10871152, 10871385, 10871636, 10871880, 10872131,
    10872380, 10872630, 10872885, 10873141, 10873376, 10873618, 10873863,
    10874086, 10874344, 10874574, 10874841, 10875092, 10875332, 10875566,
    10875808, 10876037, 10876296, 10876548, 10876802, 10877021, 10877262,
    10877491, 10877728, 10877993, 10878247, 10878479, 10878706, 10878935,
    10879162, 10879390, 10879626, 10879854, 10880066, 10880289, 10880539,
    10880790, 10881028, 10881251, 10881474, 10881709, 10881948, 10882188,
    10882433, 10882643, 10882883, 10883096, 10883319, 10883561, 10883768,
    10884006, 10884246, 10884476, 10884706, 10884940, 10885164, 10885396,
    10885601, 10885822, 10886067, 10886290, 10886538, 10886768, 10886981,
    10887169, 10887384, 10887606, 10887827, 10888058, 10888283, 10888517,
    10888750, 10888980, 10889176, 10889402, 10889636, 10889853, 10890066,
    10890292, 10890521, 10890732, 10890954, 10891146, 10891369, 10891577,
    10891780, 10891994, 10892199, 10892404, 10892624, 10892832, 10893048,
    10893257, 10893490, 10893704, 10893927, 10894144, 10894371, 10894592,
    10894802, 10895016, 10895218, 10895426, 10895627, 10895869, 10896101,
    10896320, 10896530, 10896732, 10896934, 10897150, 10897360, 10897604,
    10897816, 10898031, 10898252, 10898486, 10898692, 10898925, 10899123,
    10899331, 10899530, 10899770, 10899965, 10900186, 10900389, 10900582,
    10900777, 10900975, 10901157, 10901365, 10901576, 10901774, 10901980,
    10902186, 10902418, 10902626, 10902834, 10903067, 10903278, 10903464,
    10903647, 10903841, 10904042, 10904217, 10904415, 10904607, 10904814,
    10905009, 10905183, 10905399, 10905590, 10905796, 10905994, 10906209,
    10906396, 10906605, 10906816, 10907002, 10907217, 10907410, 10907600,
    10907802, 10907992, 10908190, 10908369, 10908588, 10908781, 10908955,
    10909147, 10909322, 10909508, 10909678, 10909879, 10910076, 10910275,
    10910470, 10910659, 10910827, 10911031, 10911231, 10911430, 10911610,
    10911815, 10911988, 10912165, 10912349, 10912537, 10912715, 10912902,
    10913098, 10913273, 10913462, 10913649, 10913822, 10913994, 10914187,
    10914363, 10914532, 10914743, 10914917, 10915094, 10915282, 10915457,
    10915622, 10915803, 10915974, 10916159, 10916342, 10916550, 10916723,
    10916924, 10917120, 10917292, 10917462, 10917634, 10917807, 10917991,
    10918172, 10918356, 10918535, 10918715, 10918884, 10919068, 10919258,
    10919435, 10919594, 10919760, 10919924, 10920099, 10920252, 10920444,
    10920622, 10920780, 10920958, 10921139, 10921298, 10921458, 10921646,
    10921796, 10921962, 10922112, 10922284, 10922449, 10922620, 10922780,
    10922948, 10923102, 10923297, 10923474, 10923656, 10923821, 10923991,
    10924156, 10924308, 10924491, 10924635, 10924810, 10924971, 10925142,
    10925301, 10925476, 10925647, 10925810, 10925972, 10926139, 10926293,
    10926466, 10926616, 10926752, 10926902, 10927049, 10927189, 10927340,
    10927499, 10927660, 10927812, 10927972, 10928134, 10928300, 10928438,
    10928605, 10928758, 10928913, 10929080, 10929244, 10929409, 10929575,
    10929706, 10929875, 10930034, 10930165, 10930327, 10930478, 10930626,
    10930770, 10930939, 10931081, 10931228, 10931386, 10931532, 10931661,
    10931810, 10931953, 10932085, 10932242, 10932385, 10932546, 10932702,
    10932848, 10933015, 10933153, 10933304, 10933438, 10933580, 10933719,
    10933869, 10934030, 10934173, 10934310, 10934448, 10934575, 10934725,
    10934853, 10934996, 10935151, 10935289, 10935449, 10935591, 10935720,
    10935855, 10935999, 10936159, 10936298, 10936442, 10936569, 10936723,
    10936871, 10937016, 10937153, 10937295, 10937458, 10937595, 10937741,
    10937887, 10938032, 10938170, 10938330, 10938459, 10938578, 10938703,
    10938845, 10938971, 10939097, 10939249, 10939377, 10939499, 10939627,
    10939786, 10939919, 10940059, 10940204, 10940337, 10940469, 10940590,
    10940734, 10940872, 10941003, 10941155, 10941259, 10941398, 10941523,
    10941652, 10941795, 10941923, 10942051, 10942200, 10942324, 10942439,
    10942562, 10942678, 10942831, 10942944, 10943077, 10943186, 10943323,
    10943455};
void prime() {
  x[0] = 2;
  x[1] = 3;
  for (int i = 5; i <= 30000; i += 2) {
    bool prima = true;
    for (int j = 0; x[j] * x[j] <= i && j < c; j++) {
      if (i % x[j] == 0) {
        prima = false;
        break;
      }
    }
    if (prima) x[c++] = i;
  }
}
vector<int> prpr;
bool cekprima(int pp) {
  if (pp < 2) return 0;
  if (pp == 2) return 1;
  if (pp % 4 != 1) return 0;
  for (int i = 0; x[i] * x[i] <= pp && i < c; i++) {
    if (pp % x[i] == 0) return 0;
  }
  return 1;
}
int l, r;
int main() {
  prime();
  scanf("%d %d", &l, &r);
  l--;
  int lef = l / 100000 * 100000 + 1;
  int righ = r / 100000 * 100000 + 1;
  int coun = 0;
  for (int i = lef; i <= l; i++) {
    if (cekprima(i)) {
      coun--;
    }
  }
  for (int i = r; i >= righ; i--) {
    if (cekprima(i)) {
      coun++;
    }
  }
  l /= 100000;
  r /= 100000;
  coun += (prec[r] - prec[l]);
  printf("%d\n", coun);
  return 0;
}
