#include <bits/stdc++.h>
using namespace std;
const int N = 3e8;
const int maxn = 2e4 + 10;
bool is_prime[maxn];
int primes[maxn];
int num = 0;
int sum[maxn] = {
    0,       8978,    16901,   24523,   31916,   39176,   46430,   53516,
    60523,   67489,   74417,   81285,   88055,   94878,   101608,  108284,
    115039,  121695,  128270,  134912,  141503,  148121,  154619,  161166,
    167675,  174194,  180617,  187048,  193493,  199900,  206333,  212732,
    219123,  225463,  231844,  238261,  244581,  250868,  257141,  263482,
    269760,  276014,  282271,  288556,  294878,  301101,  307326,  313579,
    319813,  326007,  332181,  338394,  344551,  350739,  356909,  363080,
    369261,  375439,  381635,  387817,  393993,  400087,  406288,  412333,
    418499,  424569,  430660,  436753,  442818,  448901,  454974,  461015,
    467135,  473178,  479250,  485275,  491293,  497242,  503251,  509308,
    515414,  521398,  527422,  533469,  539450,  545501,  551461,  557493,
    563514,  569508,  575503,  581445,  587448,  593357,  599365,  605357,
    611346,  617284,  623219,  629187,  635171,  641088,  646968,  652929,
    658857,  664771,  670676,  676670,  682576,  688504,  694490,  700326,
    706181,  712113,  717989,  723896,  729831,  735740,  741606,  747458,
    753318,  759188,  765150,  771012,  776896,  782754,  788611,  794449,
    800286,  806180,  812028,  817868,  823752,  829643,  835498,  841364,
    847194,  853022,  858875,  864672,  870514,  876358,  882186,  888023,
    893857,  899686,  905460,  911332,  917110,  922881,  928780,  934604,
    940453,  946295,  952088,  957871,  963624,  969407,  975196,  980962,
    986746,  992538,  998272,  1004047, 1009828, 1015619, 1021407, 1027185,
    1032962, 1038722, 1044521, 1050175, 1055897, 1061676, 1067388, 1073174,
    1078883, 1084692, 1090413, 1096221, 1101903, 1107645, 1113425, 1119226,
    1124941, 1130652, 1136475, 1142195, 1147867, 1153592, 1159339, 1165140,
    1170911, 1176591, 1182370, 1188093, 1193801, 1199545, 1205285, 1211026,
    1216688, 1222393, 1228119, 1233830, 1239605, 1245272, 1250996, 1256652,
    1262363, 1268047, 1273689, 1279377, 1285127, 1290771, 1296434, 1302081,
    1307765, 1313437, 1319179, 1324799, 1330570, 1336222, 1341880, 1347558,
    1353252, 1358925, 1364529, 1370266, 1375934, 1381608, 1387240, 1392850,
    1398555, 1404179, 1409899, 1415626, 1421271, 1426913, 1432595, 1438258,
    1443939, 1449605, 1455248, 1460920, 1466529, 1472195, 1477838, 1483501,
    1489166, 1494787, 1500453, 1506081, 1511686, 1517367, 1523011, 1528622,
    1534201, 1539894, 1545503, 1551093, 1556702, 1562352, 1567943, 1573536,
    1579176, 1584772, 1590356, 1596005, 1601564, 1607165, 1612824, 1618452,
    1624007, 1629636, 1635222, 1640857, 1646485, 1652064, 1657619, 1663265,
    1668892, 1674594, 1680125, 1685691, 1691341, 1696863, 1702441, 1708110,
    1713725, 1719267, 1724880, 1730436, 1736052, 1741642, 1747205, 1752772,
    1758337, 1763839, 1769444, 1775046, 1780671, 1786236, 1791841, 1797448,
    1803074, 1808647, 1814143, 1819707, 1825244, 1830793, 1836360, 1841996,
    1847581, 1853089, 1858663, 1864207, 1869796, 1875345, 1880878, 1886490,
    1892075, 1897679, 1903296, 1908797, 1914346, 1919906, 1925489, 1931029,
    1936618, 1942195, 1947727, 1953327, 1958882, 1964430, 1969999, 1975510,
    1981017, 1986618, 1992205, 1997721, 2003304, 2008816, 2014373, 2019933,
    2025513, 2031020, 2036610, 2042136, 2047682, 2053230, 2058719, 2064275,
    2069780, 2075349, 2080845, 2086330, 2091864, 2097407, 2102972, 2108433,
    2113990, 2119527, 2125069, 2130618, 2136173, 2141713, 2147172, 2152702,
    2158237, 2163758, 2169247, 2174706, 2180269, 2185806, 2191332, 2196835,
    2202324, 2207860, 2213444, 2218953, 2224515, 2230006, 2235482, 2240991,
    2246480, 2252025, 2257554, 2263079, 2268545, 2274003, 2279483, 2284983,
    2290512, 2295997, 2301494, 2306931, 2312443, 2317910, 2323417, 2328942,
    2334374, 2339871, 2345411, 2350887, 2356373, 2361872, 2367432, 2372878,
    2378388, 2383896, 2389450, 2394902, 2400363, 2405857, 2411351, 2416904,
    2422296, 2427745, 2433251, 2438719, 2444352, 2449765, 2455256, 2460744,
    2466187, 2471679, 2477113, 2482617, 2488154, 2493631, 2499026, 2504528,
    2509986, 2515473, 2520875, 2526330, 2531839, 2537308, 2542791, 2548284,
    2553802, 2559256, 2564750, 2570148, 2575664, 2581128, 2586615, 2592090,
    2597536, 2602944, 2608394, 2613806, 2619321, 2624787, 2630206, 2635613,
    2641068, 2646581, 2651923, 2657389, 2662840, 2668329, 2673788, 2679254,
    2684761, 2690185, 2695614, 2701067, 2706497, 2711871, 2717374, 2722854,
    2728236, 2733698, 2739146, 2744682, 2750078, 2755521, 2761026, 2766426,
    2771910, 2777363, 2782759, 2788181, 2793661, 2799109, 2804531, 2809930,
    2815400, 2820817, 2826276, 2831689, 2837100, 2842571, 2847955, 2853362,
    2858814, 2864215, 2869649, 2875061, 2880505, 2885940, 2891324, 2896737,
    2902173, 2907606, 2913026, 2918453, 2923834, 2929265, 2934703, 2940118,
    2945636, 2951035, 2956447, 2961881, 2967240, 2972638, 2978051, 2983431,
    2988902, 2994331, 2999799, 3005203, 3010597, 3016009, 3021417, 3026843,
    3032258, 3037647, 3043022, 3048458, 3053831, 3059268, 3064626, 3069997,
    3075490, 3080941, 3086305, 3091766, 3097083, 3102503, 3107929, 3113376,
    3118822, 3124226, 3129663, 3135041, 3140465, 3145895, 3151359, 3156704,
    3162037, 3167422, 3172860, 3178276, 3183679, 3189067, 3194439, 3199905,
    3205350, 3210815, 3216212, 3221531, 3226984, 3232326, 3237756, 3243108,
    3248448, 3253794, 3259118, 3264499, 3269881, 3275208, 3280684, 3286023,
    3291422, 3296809, 3302209, 3307587, 3312951, 3318340, 3323750, 3329060,
    3334387, 3339778, 3345126, 3350545, 3355956, 3361303, 3366670, 3372104,
    3377477, 3382885, 3388181, 3393551, 3398959, 3404348, 3409749, 3415112,
    3420476, 3425804, 3431140, 3436495, 3441873, 3447272, 3452685, 3458010,
    3463433, 3468740, 3474095, 3479443, 3484813, 3490171, 3495568, 3500974,
    3506387, 3511783, 3517154, 3522520, 3527908, 3533256, 3538668, 3543978,
    3549376, 3554739, 3560090, 3565457, 3570777, 3576162, 3581527, 3586899,
    3592224, 3597609, 3602937, 3608315, 3613719, 3619063, 3624437, 3629813,
    3635172, 3640546, 3645881, 3651242, 3656685, 3662084, 3667446, 3672775,
    3678172, 3683590, 3688865, 3694149, 3699495, 3704779, 3710195, 3715571,
    3720907, 3726326, 3731697, 3737057, 3742387, 3747736, 3753093, 3758470,
    3763798, 3769101, 3774512, 3779799, 3785161, 3790455, 3795810, 3801142,
    3806532, 3811893, 3817240, 3822594, 3827949, 3833257, 3838551, 3843893,
    3849184, 3854488, 3859809, 3865213, 3870566, 3875855, 3881127, 3886491,
    3891882, 3897254, 3902460, 3907779, 3913050, 3918400, 3923696, 3929085,
    3934443, 3939772, 3945191, 3950555, 3955921, 3961297, 3966568, 3971880,
    3977155, 3982460, 3987720, 3993126, 3998438, 4003807, 4009128, 4014469,
    4019846, 4025096, 4030424, 4035734, 4041068, 4046464, 4051770, 4057114,
    4062451, 4067794, 4073176, 4078473, 4083782, 4089090, 4094421, 4099748,
    4105056, 4110356, 4115722, 4121052, 4126380, 4131700, 4137024, 4142364,
    4147677, 4153011, 4158364, 4163597, 4168923, 4174224, 4179522, 4184850,
    4190141, 4195422, 4200732, 4206045, 4211357, 4216686, 4221985, 4227283,
    4232565, 4237862, 4243170, 4248402, 4253702, 4259015, 4264294, 4269625,
    4274957, 4280202, 4285399, 4290688, 4296021, 4301295, 4306609, 4311887,
    4317235, 4322593, 4327912, 4333234, 4338516, 4343802, 4349053, 4354389,
    4359663, 4364926, 4370299, 4375553, 4380845, 4386240, 4391542, 4396851,
    4402187, 4407487, 4412694, 4418023, 4423372, 4428609, 4433902, 4439170,
    4444490, 4449673, 4454923, 4460241, 4465544, 4470785, 4476148, 4481417,
    4486724, 4492007, 4497293, 4502619, 4507856, 4513194, 4518560, 4523774,
    4529073, 4534347, 4539593, 4544861, 4550196, 4555492, 4560804, 4566061,
    4571337, 4576657, 4581977, 4587326, 4592654, 4597877, 4603201, 4608469,
    4613737, 4619006, 4624232, 4629508, 4634797, 4640031, 4645360, 4650560,
    4655889, 4661190, 4666451, 4671705, 4676997, 4682243, 4687533, 4692790,
    4698103, 4703363, 4708643, 4713900, 4719202, 4724481, 4729855, 4735168,
    4740486, 4745721, 4750950, 4756289, 4761561, 4766823, 4772013, 4777296,
    4782597, 4787905, 4793167, 4798436, 4803668, 4808985, 4814267, 4819529,
    4824805, 4830058, 4835379, 4840681, 4845982, 4851212, 4856492, 4861763,
    4867028, 4872296, 4877529, 4882798, 4888078, 4893365, 4898673, 4903891,
    4909157, 4914384, 4919690, 4924919, 4930213, 4935488, 4940775, 4946070,
    4951297, 4956558, 4961878, 4967185, 4972410, 4977662, 4982941, 4988226,
    4993516, 4998802, 5004057, 5009406, 5014695, 5019950, 5025179, 5030447,
    5035681, 5040863, 5046095, 5051412, 5056629, 5061913, 5067205, 5072492,
    5077659, 5082860, 5088135, 5093333, 5098616, 5103826, 5109090, 5114362,
    5119591, 5124845, 5130154, 5135431, 5140731, 5145981, 5151275, 5156547,
    5161734, 5166954, 5172232, 5177522, 5182723, 5187966, 5193213, 5198500,
    5203797, 5209050, 5214289, 5219488, 5224741, 5230075, 5235256, 5240497,
    5245787, 5250964, 5256295, 5261560, 5266812, 5272057, 5277359, 5282588,
    5287825, 5292984, 5298144, 5303300, 5308565, 5313783, 5319019, 5324214,
    5329410, 5334623, 5339868, 5345130, 5350422, 5355703, 5360987, 5366148,
    5371412, 5376687, 5381929, 5387172, 5392412, 5397629, 5402887, 5408176,
    5413434, 5418615, 5423862, 5429133, 5434359, 5439576, 5444785, 5450050,
    5455226, 5460458, 5465636, 5470840, 5476040, 5481234, 5486492, 5491685,
    5496930, 5502195, 5507484, 5512631, 5517813, 5523148, 5528354, 5533526,
    5538821, 5544171, 5549334, 5554594, 5559794, 5564989, 5570318, 5575559,
    5580735, 5585968, 5591257, 5596537, 5601766, 5606978, 5612150, 5617364,
    5622604, 5627890, 5633085, 5638332, 5643587, 5648777, 5653955, 5659237,
    5664467, 5669724, 5674898, 5680112, 5685283, 5690537, 5695725, 5700962,
    5706173, 5711418, 5716608, 5721870, 5727030, 5732291, 5737555, 5742760,
    5747922, 5753109, 5758284, 5763488, 5768742, 5773921, 5779099, 5784324,
    5789590, 5794904, 5800089, 5805349, 5810588, 5815758, 5820930, 5826127,
    5831423, 5836688, 5841893, 5847110, 5852352, 5857519, 5862786, 5868021,
    5873255, 5878520, 5883729, 5888952, 5894167, 5899352, 5904577, 5909822,
    5914980, 5920157, 5925412, 5930672, 5935941, 5941165, 5946380, 5951600,
    5956845, 5962107, 5967358, 5972550, 5977742, 5982939, 5988135, 5993379,
    5998500, 6003727, 6008887, 6014158, 6019332, 6024475, 6029692, 6034853,
    6040041, 6045299, 6050499, 6055662, 6060852, 6066107, 6071358, 6076512,
    6081675, 6086846, 6092066, 6097313, 6102471, 6107732, 6112891, 6118146,
    6123306, 6128580, 6133813, 6139005, 6144218, 6149371, 6154675, 6159871,
    6164976, 6170168, 6175450, 6180645, 6185805, 6191134, 6196339, 6201446,
    6206615, 6211825, 6217047, 6222252, 6227426, 6232618, 6237903, 6243137,
    6248383, 6253594, 6258704, 6263772, 6268950, 6274153, 6279295, 6284431,
    6289703, 6294880, 6300083, 6305225, 6310423, 6315578, 6320783, 6326011,
    6331172, 6336395, 6341630, 6346739, 6351927, 6357116, 6362295, 6367512,
    6372759, 6377932, 6383126, 6388317, 6393566, 6398760, 6403894, 6409020,
    6414240, 6419444, 6424585, 6429774, 6434905, 6440084, 6445293, 6450524,
    6455682, 6460917, 6466171, 6471304, 6476474, 6481719, 6486895, 6492070,
    6497314, 6502519, 6507692, 6512873, 6518114, 6523259, 6528444, 6533690,
    6538887, 6544021, 6549285, 6554452, 6559587, 6564770, 6569951, 6575116,
    6580260, 6585456, 6590708, 6595957, 6601071, 6606273, 6611498, 6616698,
    6621894, 6627012, 6632211, 6637327, 6642444, 6647598, 6652723, 6657923,
    6663028, 6668208, 6673402, 6678603, 6683806, 6688966, 6694117, 6699329,
    6704527, 6709795, 6714983, 6720189, 6725391, 6730547, 6735695, 6740828,
    6745968, 6751153, 6756299, 6761489, 6766666, 6771775, 6776965, 6782076,
    6787249, 6792400, 6797654, 6802810, 6807999, 6813192, 6818374, 6823539,
    6828648, 6833809, 6838975, 6844146, 6849310, 6854427, 6859666, 6864928,
    6870031, 6875182, 6880327, 6885471, 6890595, 6895824, 6900909, 6906086,
    6911194, 6916351, 6921532, 6926760, 6932010, 6937122, 6942266, 6947433,
    6952622, 6957811, 6963003, 6968229, 6973374, 6978553, 6983701, 6988895,
    6994053, 6999239, 7004386, 7009509, 7014637, 7019911, 7025101, 7030312,
    7035446, 7040537, 7045744, 7050888, 7056063, 7061274, 7066487, 7071649,
    7076794, 7081992, 7087182, 7092253, 7097378, 7102560, 7107734, 7112923,
    7118105, 7123329, 7128529, 7133676, 7138851, 7143963, 7149099, 7154306,
    7159502, 7164744, 7169862, 7175070, 7180299, 7185447, 7190543, 7195725,
    7200837, 7206026, 7211221, 7216339, 7221467, 7226696, 7231835, 7237074,
    7242248, 7247438, 7252624, 7257777, 7262872, 7267970, 7273095, 7278251,
    7283410, 7288560, 7293745, 7298848, 7304018, 7309180, 7314293, 7319531,
    7324659, 7329881, 7335022, 7340210, 7345280, 7350378, 7355504, 7360615,
    7365832, 7371013, 7376145, 7381276, 7386365, 7391502, 7396642, 7401866,
    7406982, 7412102, 7417288, 7422441, 7427522, 7432639, 7437740, 7442912,
    7448114, 7453261, 7458445, 7463635, 7468787, 7473930, 7479118, 7484264,
    7489342, 7494521, 7499688, 7504815, 7509988, 7515087, 7520308, 7525392,
    7530543, 7535700, 7540804, 7545943, 7551130, 7556313, 7561435, 7566505,
    7571641, 7576783, 7581897, 7587022, 7592151, 7597276, 7602390, 7607619,
    7612748, 7617858, 7622960, 7628196, 7633277, 7638354, 7643496, 7648660,
    7653833, 7659011, 7664134, 7669193, 7674356, 7679488, 7684595, 7689731,
    7694861, 7700031, 7705205, 7710348, 7715474, 7720597, 7725778, 7730889,
    7736038, 7741178, 7746199, 7751407, 7756540, 7761686, 7766793, 7771905,
    7777035, 7782119, 7787226, 7792385, 7797627, 7802758, 7807903, 7813000,
    7818155, 7823285, 7828445, 7833550, 7838714, 7843890, 7848885, 7854000,
    7859172, 7864364, 7869478, 7874591, 7879768, 7884851, 7890024, 7895233,
    7900429, 7905546, 7910582, 7915728, 7920913, 7926037, 7931211, 7936281,
    7941378, 7946432, 7951602, 7956760, 7961868, 7967003, 7972124, 7977293,
    7982413, 7987569, 7992722, 7997861, 8002935, 8008047, 8013200, 8018323,
    8023413, 8028499, 8033583, 8038758, 8043966, 8049029, 8054132, 8059305,
    8064377, 8069508, 8074668, 8079782, 8084914, 8090092, 8095135, 8100189,
    8105256, 8110337, 8115467, 8120631, 8125719};
void Sieve(int n) {
  for (int i = 2; i < n; i++) is_prime[i] = true;
  for (int i = 2; i < n; i++) {
    if (is_prime[i]) primes[num++] = i;
    for (int j = 0; j < num && primes[j] * i < n; j++) {
      is_prime[i * primes[j]] = false;
      if (i % primes[j] == 0) break;
    }
  }
}
bool check(int p) {
  if (p < 2) return false;
  if (p == 2) return true;
  if (p % 4 != 1) return false;
  for (int i = 0; i < num && primes[i] < p; i++)
    if (p % primes[i] == 0) return false;
  return true;
}
int calc(int L, int R) {
  int ans = 0;
  for (int i = L; i <= R; i++)
    if (check(i)) ans++;
  return ans;
}
int getAns(int up) {
  int ans = sum[up / 200000];
  ans += calc((up / 200000) * 200000 + 1, up);
  return ans;
}
int l, r;
int main() {
  Sieve(maxn);
  scanf("%d%d", &l, &r);
  printf("%d\n", getAns(r) - getAns(l - 1));
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

On the math lesson a teacher asked each pupil to come up with his own lucky numbers. As a fan of number theory Peter chose prime numbers. Bob was more original. He said that number t is his lucky number, if it can be represented as: 

t = a2 + b2,  where a, b are arbitrary positive integers.

Now, the boys decided to find out how many days of the interval [l, r] (l ≤ r) are suitable for pair programming. They decided that the day i (l ≤ i ≤ r) is suitable for pair programming if and only if the number i is lucky for Peter and lucky for Bob at the same time. Help the boys to find the number of such days.

Input

The first line of the input contains integer numbers l, r (1 ≤ l, r ≤ 3·108).

Output

In the only line print the number of days on the segment [l, r], which are lucky for Peter and Bob at the same time.

Examples

Input

3 5


Output

1


Input

6 66


Output

7

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 3e8;
const int maxn = 2e4 + 10;
bool is_prime[maxn];
int primes[maxn];
int num = 0;
int sum[maxn] = {
    0,       8978,    16901,   24523,   31916,   39176,   46430,   53516,
    60523,   67489,   74417,   81285,   88055,   94878,   101608,  108284,
    115039,  121695,  128270,  134912,  141503,  148121,  154619,  161166,
    167675,  174194,  180617,  187048,  193493,  199900,  206333,  212732,
    219123,  225463,  231844,  238261,  244581,  250868,  257141,  263482,
    269760,  276014,  282271,  288556,  294878,  301101,  307326,  313579,
    319813,  326007,  332181,  338394,  344551,  350739,  356909,  363080,
    369261,  375439,  381635,  387817,  393993,  400087,  406288,  412333,
    418499,  424569,  430660,  436753,  442818,  448901,  454974,  461015,
    467135,  473178,  479250,  485275,  491293,  497242,  503251,  509308,
    515414,  521398,  527422,  533469,  539450,  545501,  551461,  557493,
    563514,  569508,  575503,  581445,  587448,  593357,  599365,  605357,
    611346,  617284,  623219,  629187,  635171,  641088,  646968,  652929,
    658857,  664771,  670676,  676670,  682576,  688504,  694490,  700326,
    706181,  712113,  717989,  723896,  729831,  735740,  741606,  747458,
    753318,  759188,  765150,  771012,  776896,  782754,  788611,  794449,
    800286,  806180,  812028,  817868,  823752,  829643,  835498,  841364,
    847194,  853022,  858875,  864672,  870514,  876358,  882186,  888023,
    893857,  899686,  905460,  911332,  917110,  922881,  928780,  934604,
    940453,  946295,  952088,  957871,  963624,  969407,  975196,  980962,
    986746,  992538,  998272,  1004047, 1009828, 1015619, 1021407, 1027185,
    1032962, 1038722, 1044521, 1050175, 1055897, 1061676, 1067388, 1073174,
    1078883, 1084692, 1090413, 1096221, 1101903, 1107645, 1113425, 1119226,
    1124941, 1130652, 1136475, 1142195, 1147867, 1153592, 1159339, 1165140,
    1170911, 1176591, 1182370, 1188093, 1193801, 1199545, 1205285, 1211026,
    1216688, 1222393, 1228119, 1233830, 1239605, 1245272, 1250996, 1256652,
    1262363, 1268047, 1273689, 1279377, 1285127, 1290771, 1296434, 1302081,
    1307765, 1313437, 1319179, 1324799, 1330570, 1336222, 1341880, 1347558,
    1353252, 1358925, 1364529, 1370266, 1375934, 1381608, 1387240, 1392850,
    1398555, 1404179, 1409899, 1415626, 1421271, 1426913, 1432595, 1438258,
    1443939, 1449605, 1455248, 1460920, 1466529, 1472195, 1477838, 1483501,
    1489166, 1494787, 1500453, 1506081, 1511686, 1517367, 1523011, 1528622,
    1534201, 1539894, 1545503, 1551093, 1556702, 1562352, 1567943, 1573536,
    1579176, 1584772, 1590356, 1596005, 1601564, 1607165, 1612824, 1618452,
    1624007, 1629636, 1635222, 1640857, 1646485, 1652064, 1657619, 1663265,
    1668892, 1674594, 1680125, 1685691, 1691341, 1696863, 1702441, 1708110,
    1713725, 1719267, 1724880, 1730436, 1736052, 1741642, 1747205, 1752772,
    1758337, 1763839, 1769444, 1775046, 1780671, 1786236, 1791841, 1797448,
    1803074, 1808647, 1814143, 1819707, 1825244, 1830793, 1836360, 1841996,
    1847581, 1853089, 1858663, 1864207, 1869796, 1875345, 1880878, 1886490,
    1892075, 1897679, 1903296, 1908797, 1914346, 1919906, 1925489, 1931029,
    1936618, 1942195, 1947727, 1953327, 1958882, 1964430, 1969999, 1975510,
    1981017, 1986618, 1992205, 1997721, 2003304, 2008816, 2014373, 2019933,
    2025513, 2031020, 2036610, 2042136, 2047682, 2053230, 2058719, 2064275,
    2069780, 2075349, 2080845, 2086330, 2091864, 2097407, 2102972, 2108433,
    2113990, 2119527, 2125069, 2130618, 2136173, 2141713, 2147172, 2152702,
    2158237, 2163758, 2169247, 2174706, 2180269, 2185806, 2191332, 2196835,
    2202324, 2207860, 2213444, 2218953, 2224515, 2230006, 2235482, 2240991,
    2246480, 2252025, 2257554, 2263079, 2268545, 2274003, 2279483, 2284983,
    2290512, 2295997, 2301494, 2306931, 2312443, 2317910, 2323417, 2328942,
    2334374, 2339871, 2345411, 2350887, 2356373, 2361872, 2367432, 2372878,
    2378388, 2383896, 2389450, 2394902, 2400363, 2405857, 2411351, 2416904,
    2422296, 2427745, 2433251, 2438719, 2444352, 2449765, 2455256, 2460744,
    2466187, 2471679, 2477113, 2482617, 2488154, 2493631, 2499026, 2504528,
    2509986, 2515473, 2520875, 2526330, 2531839, 2537308, 2542791, 2548284,
    2553802, 2559256, 2564750, 2570148, 2575664, 2581128, 2586615, 2592090,
    2597536, 2602944, 2608394, 2613806, 2619321, 2624787, 2630206, 2635613,
    2641068, 2646581, 2651923, 2657389, 2662840, 2668329, 2673788, 2679254,
    2684761, 2690185, 2695614, 2701067, 2706497, 2711871, 2717374, 2722854,
    2728236, 2733698, 2739146, 2744682, 2750078, 2755521, 2761026, 2766426,
    2771910, 2777363, 2782759, 2788181, 2793661, 2799109, 2804531, 2809930,
    2815400, 2820817, 2826276, 2831689, 2837100, 2842571, 2847955, 2853362,
    2858814, 2864215, 2869649, 2875061, 2880505, 2885940, 2891324, 2896737,
    2902173, 2907606, 2913026, 2918453, 2923834, 2929265, 2934703, 2940118,
    2945636, 2951035, 2956447, 2961881, 2967240, 2972638, 2978051, 2983431,
    2988902, 2994331, 2999799, 3005203, 3010597, 3016009, 3021417, 3026843,
    3032258, 3037647, 3043022, 3048458, 3053831, 3059268, 3064626, 3069997,
    3075490, 3080941, 3086305, 3091766, 3097083, 3102503, 3107929, 3113376,
    3118822, 3124226, 3129663, 3135041, 3140465, 3145895, 3151359, 3156704,
    3162037, 3167422, 3172860, 3178276, 3183679, 3189067, 3194439, 3199905,
    3205350, 3210815, 3216212, 3221531, 3226984, 3232326, 3237756, 3243108,
    3248448, 3253794, 3259118, 3264499, 3269881, 3275208, 3280684, 3286023,
    3291422, 3296809, 3302209, 3307587, 3312951, 3318340, 3323750, 3329060,
    3334387, 3339778, 3345126, 3350545, 3355956, 3361303, 3366670, 3372104,
    3377477, 3382885, 3388181, 3393551, 3398959, 3404348, 3409749, 3415112,
    3420476, 3425804, 3431140, 3436495, 3441873, 3447272, 3452685, 3458010,
    3463433, 3468740, 3474095, 3479443, 3484813, 3490171, 3495568, 3500974,
    3506387, 3511783, 3517154, 3522520, 3527908, 3533256, 3538668, 3543978,
    3549376, 3554739, 3560090, 3565457, 3570777, 3576162, 3581527, 3586899,
    3592224, 3597609, 3602937, 3608315, 3613719, 3619063, 3624437, 3629813,
    3635172, 3640546, 3645881, 3651242, 3656685, 3662084, 3667446, 3672775,
    3678172, 3683590, 3688865, 3694149, 3699495, 3704779, 3710195, 3715571,
    3720907, 3726326, 3731697, 3737057, 3742387, 3747736, 3753093, 3758470,
    3763798, 3769101, 3774512, 3779799, 3785161, 3790455, 3795810, 3801142,
    3806532, 3811893, 3817240, 3822594, 3827949, 3833257, 3838551, 3843893,
    3849184, 3854488, 3859809, 3865213, 3870566, 3875855, 3881127, 3886491,
    3891882, 3897254, 3902460, 3907779, 3913050, 3918400, 3923696, 3929085,
    3934443, 3939772, 3945191, 3950555, 3955921, 3961297, 3966568, 3971880,
    3977155, 3982460, 3987720, 3993126, 3998438, 4003807, 4009128, 4014469,
    4019846, 4025096, 4030424, 4035734, 4041068, 4046464, 4051770, 4057114,
    4062451, 4067794, 4073176, 4078473, 4083782, 4089090, 4094421, 4099748,
    4105056, 4110356, 4115722, 4121052, 4126380, 4131700, 4137024, 4142364,
    4147677, 4153011, 4158364, 4163597, 4168923, 4174224, 4179522, 4184850,
    4190141, 4195422, 4200732, 4206045, 4211357, 4216686, 4221985, 4227283,
    4232565, 4237862, 4243170, 4248402, 4253702, 4259015, 4264294, 4269625,
    4274957, 4280202, 4285399, 4290688, 4296021, 4301295, 4306609, 4311887,
    4317235, 4322593, 4327912, 4333234, 4338516, 4343802, 4349053, 4354389,
    4359663, 4364926, 4370299, 4375553, 4380845, 4386240, 4391542, 4396851,
    4402187, 4407487, 4412694, 4418023, 4423372, 4428609, 4433902, 4439170,
    4444490, 4449673, 4454923, 4460241, 4465544, 4470785, 4476148, 4481417,
    4486724, 4492007, 4497293, 4502619, 4507856, 4513194, 4518560, 4523774,
    4529073, 4534347, 4539593, 4544861, 4550196, 4555492, 4560804, 4566061,
    4571337, 4576657, 4581977, 4587326, 4592654, 4597877, 4603201, 4608469,
    4613737, 4619006, 4624232, 4629508, 4634797, 4640031, 4645360, 4650560,
    4655889, 4661190, 4666451, 4671705, 4676997, 4682243, 4687533, 4692790,
    4698103, 4703363, 4708643, 4713900, 4719202, 4724481, 4729855, 4735168,
    4740486, 4745721, 4750950, 4756289, 4761561, 4766823, 4772013, 4777296,
    4782597, 4787905, 4793167, 4798436, 4803668, 4808985, 4814267, 4819529,
    4824805, 4830058, 4835379, 4840681, 4845982, 4851212, 4856492, 4861763,
    4867028, 4872296, 4877529, 4882798, 4888078, 4893365, 4898673, 4903891,
    4909157, 4914384, 4919690, 4924919, 4930213, 4935488, 4940775, 4946070,
    4951297, 4956558, 4961878, 4967185, 4972410, 4977662, 4982941, 4988226,
    4993516, 4998802, 5004057, 5009406, 5014695, 5019950, 5025179, 5030447,
    5035681, 5040863, 5046095, 5051412, 5056629, 5061913, 5067205, 5072492,
    5077659, 5082860, 5088135, 5093333, 5098616, 5103826, 5109090, 5114362,
    5119591, 5124845, 5130154, 5135431, 5140731, 5145981, 5151275, 5156547,
    5161734, 5166954, 5172232, 5177522, 5182723, 5187966, 5193213, 5198500,
    5203797, 5209050, 5214289, 5219488, 5224741, 5230075, 5235256, 5240497,
    5245787, 5250964, 5256295, 5261560, 5266812, 5272057, 5277359, 5282588,
    5287825, 5292984, 5298144, 5303300, 5308565, 5313783, 5319019, 5324214,
    5329410, 5334623, 5339868, 5345130, 5350422, 5355703, 5360987, 5366148,
    5371412, 5376687, 5381929, 5387172, 5392412, 5397629, 5402887, 5408176,
    5413434, 5418615, 5423862, 5429133, 5434359, 5439576, 5444785, 5450050,
    5455226, 5460458, 5465636, 5470840, 5476040, 5481234, 5486492, 5491685,
    5496930, 5502195, 5507484, 5512631, 5517813, 5523148, 5528354, 5533526,
    5538821, 5544171, 5549334, 5554594, 5559794, 5564989, 5570318, 5575559,
    5580735, 5585968, 5591257, 5596537, 5601766, 5606978, 5612150, 5617364,
    5622604, 5627890, 5633085, 5638332, 5643587, 5648777, 5653955, 5659237,
    5664467, 5669724, 5674898, 5680112, 5685283, 5690537, 5695725, 5700962,
    5706173, 5711418, 5716608, 5721870, 5727030, 5732291, 5737555, 5742760,
    5747922, 5753109, 5758284, 5763488, 5768742, 5773921, 5779099, 5784324,
    5789590, 5794904, 5800089, 5805349, 5810588, 5815758, 5820930, 5826127,
    5831423, 5836688, 5841893, 5847110, 5852352, 5857519, 5862786, 5868021,
    5873255, 5878520, 5883729, 5888952, 5894167, 5899352, 5904577, 5909822,
    5914980, 5920157, 5925412, 5930672, 5935941, 5941165, 5946380, 5951600,
    5956845, 5962107, 5967358, 5972550, 5977742, 5982939, 5988135, 5993379,
    5998500, 6003727, 6008887, 6014158, 6019332, 6024475, 6029692, 6034853,
    6040041, 6045299, 6050499, 6055662, 6060852, 6066107, 6071358, 6076512,
    6081675, 6086846, 6092066, 6097313, 6102471, 6107732, 6112891, 6118146,
    6123306, 6128580, 6133813, 6139005, 6144218, 6149371, 6154675, 6159871,
    6164976, 6170168, 6175450, 6180645, 6185805, 6191134, 6196339, 6201446,
    6206615, 6211825, 6217047, 6222252, 6227426, 6232618, 6237903, 6243137,
    6248383, 6253594, 6258704, 6263772, 6268950, 6274153, 6279295, 6284431,
    6289703, 6294880, 6300083, 6305225, 6310423, 6315578, 6320783, 6326011,
    6331172, 6336395, 6341630, 6346739, 6351927, 6357116, 6362295, 6367512,
    6372759, 6377932, 6383126, 6388317, 6393566, 6398760, 6403894, 6409020,
    6414240, 6419444, 6424585, 6429774, 6434905, 6440084, 6445293, 6450524,
    6455682, 6460917, 6466171, 6471304, 6476474, 6481719, 6486895, 6492070,
    6497314, 6502519, 6507692, 6512873, 6518114, 6523259, 6528444, 6533690,
    6538887, 6544021, 6549285, 6554452, 6559587, 6564770, 6569951, 6575116,
    6580260, 6585456, 6590708, 6595957, 6601071, 6606273, 6611498, 6616698,
    6621894, 6627012, 6632211, 6637327, 6642444, 6647598, 6652723, 6657923,
    6663028, 6668208, 6673402, 6678603, 6683806, 6688966, 6694117, 6699329,
    6704527, 6709795, 6714983, 6720189, 6725391, 6730547, 6735695, 6740828,
    6745968, 6751153, 6756299, 6761489, 6766666, 6771775, 6776965, 6782076,
    6787249, 6792400, 6797654, 6802810, 6807999, 6813192, 6818374, 6823539,
    6828648, 6833809, 6838975, 6844146, 6849310, 6854427, 6859666, 6864928,
    6870031, 6875182, 6880327, 6885471, 6890595, 6895824, 6900909, 6906086,
    6911194, 6916351, 6921532, 6926760, 6932010, 6937122, 6942266, 6947433,
    6952622, 6957811, 6963003, 6968229, 6973374, 6978553, 6983701, 6988895,
    6994053, 6999239, 7004386, 7009509, 7014637, 7019911, 7025101, 7030312,
    7035446, 7040537, 7045744, 7050888, 7056063, 7061274, 7066487, 7071649,
    7076794, 7081992, 7087182, 7092253, 7097378, 7102560, 7107734, 7112923,
    7118105, 7123329, 7128529, 7133676, 7138851, 7143963, 7149099, 7154306,
    7159502, 7164744, 7169862, 7175070, 7180299, 7185447, 7190543, 7195725,
    7200837, 7206026, 7211221, 7216339, 7221467, 7226696, 7231835, 7237074,
    7242248, 7247438, 7252624, 7257777, 7262872, 7267970, 7273095, 7278251,
    7283410, 7288560, 7293745, 7298848, 7304018, 7309180, 7314293, 7319531,
    7324659, 7329881, 7335022, 7340210, 7345280, 7350378, 7355504, 7360615,
    7365832, 7371013, 7376145, 7381276, 7386365, 7391502, 7396642, 7401866,
    7406982, 7412102, 7417288, 7422441, 7427522, 7432639, 7437740, 7442912,
    7448114, 7453261, 7458445, 7463635, 7468787, 7473930, 7479118, 7484264,
    7489342, 7494521, 7499688, 7504815, 7509988, 7515087, 7520308, 7525392,
    7530543, 7535700, 7540804, 7545943, 7551130, 7556313, 7561435, 7566505,
    7571641, 7576783, 7581897, 7587022, 7592151, 7597276, 7602390, 7607619,
    7612748, 7617858, 7622960, 7628196, 7633277, 7638354, 7643496, 7648660,
    7653833, 7659011, 7664134, 7669193, 7674356, 7679488, 7684595, 7689731,
    7694861, 7700031, 7705205, 7710348, 7715474, 7720597, 7725778, 7730889,
    7736038, 7741178, 7746199, 7751407, 7756540, 7761686, 7766793, 7771905,
    7777035, 7782119, 7787226, 7792385, 7797627, 7802758, 7807903, 7813000,
    7818155, 7823285, 7828445, 7833550, 7838714, 7843890, 7848885, 7854000,
    7859172, 7864364, 7869478, 7874591, 7879768, 7884851, 7890024, 7895233,
    7900429, 7905546, 7910582, 7915728, 7920913, 7926037, 7931211, 7936281,
    7941378, 7946432, 7951602, 7956760, 7961868, 7967003, 7972124, 7977293,
    7982413, 7987569, 7992722, 7997861, 8002935, 8008047, 8013200, 8018323,
    8023413, 8028499, 8033583, 8038758, 8043966, 8049029, 8054132, 8059305,
    8064377, 8069508, 8074668, 8079782, 8084914, 8090092, 8095135, 8100189,
    8105256, 8110337, 8115467, 8120631, 8125719};
void Sieve(int n) {
  for (int i = 2; i < n; i++) is_prime[i] = true;
  for (int i = 2; i < n; i++) {
    if (is_prime[i]) primes[num++] = i;
    for (int j = 0; j < num && primes[j] * i < n; j++) {
      is_prime[i * primes[j]] = false;
      if (i % primes[j] == 0) break;
    }
  }
}
bool check(int p) {
  if (p < 2) return false;
  if (p == 2) return true;
  if (p % 4 != 1) return false;
  for (int i = 0; i < num && primes[i] < p; i++)
    if (p % primes[i] == 0) return false;
  return true;
}
int calc(int L, int R) {
  int ans = 0;
  for (int i = L; i <= R; i++)
    if (check(i)) ans++;
  return ans;
}
int getAns(int up) {
  int ans = sum[up / 200000];
  ans += calc((up / 200000) * 200000 + 1, up);
  return ans;
}
int l, r;
int main() {
  Sieve(maxn);
  scanf("%d%d", &l, &r);
  printf("%d\n", getAns(r) - getAns(l - 1));
  return 0;
}

```