/*发现自己无耻到一种境界了*/
/*分析复杂度，分类讨论，最后打表*/
#include <stdio.h>
#include <memory.h>
#include <math.h>
int prime[4000],ans[20010];
const int M=20000;
int a[10000]={0,0,0,0,0,0,0,1,0,1,2,2,2,3,3,4,4,5,5,6,6,6,6,9,8,8,11,11,10,13,13,12,14,15,13,18,17,14,21,19,17,25,20,21,26,25,22,30,28,21,32,31,23,37,32,27,39,36,32,43,41,36,45,44,35,51,48,34,54,48,36,59,50,43,60,55,46,61,62,47,67,64,44,73,61,52,80,66,55,79,74,61,80,82,58,89,84,57,92,86,67,98,84,71,100,92,79,107,101,72,111,107,69,119,105,76,118,101,83,122,117,94,119,125,91,135,128,89,143,127,94,146,127,102,147,141,105,146,149,106,159,157,103,165,152,116,176,148,122,178,161,128,176,175,125,190,180,119,196,175,131,200,173,144,195,185,147,202,195,143,221,204,136,230,202,148,232,197,154,228,216,159,222,228,161,241,228,155,253,221,176,268,216,178,254,243,184,258,258,174,272,260,166,281,259,191,286,244,200,285,269,210,286,283,195,306,293,189,324,287,204,322,274,223,318,305,231,302,314,221,339,321,218,356,313,232,358,313,241,366,339,246,344,353,242,372,364,233,377,350,256,396,336,269,397,361,282,384,387,268,416,399,248,427,383,282,426,379,291,418,399,305,412,412,299,452,420,280,458,415,295,471,404,306,467,428,324,442,450,319,469,455,295,493,446,331,506,421,336,500,467,348,482,487,328,522,491,324,531,496,356,528,464,361,538,500,384,531,510,363,564,531,344,582,526,371,585,502,393,581,551,407,545,568,395,602,571,381,628,551,409,634,543,426,633,592,416,604,610,423,649,626,401,657,605,437,673,559,467,677,611,463,646,648,447,696,665,412,705,644,461,723,618,484,697,663,489,687,684,489,738,685,452,750,685,488,778,660,504,757,694,522,722,744,515,758,738,479,789,724,531,813,678,538,803,753,541,765,783,521,824,782,495,832,780,554,828,737,565,847,791,599,810,800,566,872,841,535,890,824,577,900,770,588,887,844,619,829,873,601,914,870,576,949,842,609,949,835,622,954,894,631,896,909,623,969,926,600,961,903,647,990,861,680,1010,918,672,931,969,658,1023,980,604,1035,937,678,1038,920,694,1009,978,715,983,1005,700,1075,994,647,1082,987,714,1097,949,708,1083,1016,747,1031,1074,730,1061,1064,679,1146,1040,752,1150,963,765,1131,1071,771,1086,1111,744,1174,1113,700,1192,1106,781,1167,1025,805,1193,1121,813,1146,1133,797,1217,1177,743,1251,1165,793,1263,1074,835,1241,1189,864,1156,1211,822,1272,1215,800,1313,1180,849,1308,1134,882,1309,1235,870,1246,1266,866,1340,1288,841,1329,1255,876,1364,1186,927,1376,1249,925,1292,1333,906,1409,1340,814,1397,1296,931,1431,1253,962,1378,1324,955,1334,1375,953,1458,1349,884,1465,1361,963,1487,1294,950,1454,1398,998,1388,1451,977,1460,1433,925,1523,1411,1002,1543,1302,1025,1529,1450,1033,1451,1508,986,1548,1473,955,1582,1479,1048,1553,1383,1071,1586,1495,1088,1499,1526,1052,1634,1556,983,1651,1530,1047,1653,1431,1080,1635,1564,1129,1515,1610,1096,1683,1607,1045,1727,1518,1114,1707,1507,1134,1715,1633,1124,1604,1653,1136,1735,1700,1077,1742,1638,1161,1782,1551,1203,1790,1631,1184,1675,1726,1169,1805,1748,1051,1834,1684,1211,1838,1603,1224,1775,1722,1230,1725,1777,1239,1871,1742,1129,1880,1766,1226,1904,1677,1220,1878,1779,1275,1771,1835,1248,1866,1832,1165,1940,1793,1286,1980,1661,1295,1943,1831,1298,1840,1910,1238,1968,1889,1208,2010,1869,1317,1945,1758,1349,1987,1896,1387,1919,1911,1322,2049,1957,1237,2097,1942,1327,2082,1806,1384,2072,1976,1425,1900,2001,1377,2104,2017,1320,2151,1941,1387,2167,1893,1429,2124,2041,1412,2016,2077,1404,2190,2099,1344,2133,2042,1430,2208,1924,1509,2231,2036,1487,2095,2151,1461,2264,2123,1342,2276,2112,1481,2280,1992,1522,2213,2155,1536,2119,2211,1517,2350,2155,1407,2354,2189,1522,2378,2060,1494,2341,2198,1587,2194,2297,1566,2324,2275,1465,2406,2230,1607,2469,2059,1601,2408,2278,1627,2295,2364,1554,2445,2344,1493,2483,2340,1649,2441,2182,1657,2502,2347,1683,2379,2340,1653,2531,2427,1549,2589,2410,1635,2562,2217,1704,2560,2457,1749,2345,2473,1709,2606,2489,1593,2644,2393,1719,2657,2321,1741,2657,2501,1724,2489,2550,1715,2676,2589,1624,2631,2516,1768,2749,2368,1828,2721,2466,1819,2548,2625,1781,2757,2652,1622,2771,2593,1817,2749,2460,1858,2705,2611,1867,2599,2674,1883,2843,2646,1690,2844,2652,1844,2893,2523,1829,2845,2686,1910,2655,2755,1903,2807,2768,1746,2915,2726,1930,2950,2503,1922,2868,2774,1959,2759,2876,1865,2924,2848,1815,2981,2806,1944,2927,2605,1997,2976,2836,2025,2833,2844,1985,3031,2924,1855,3083,2908,1925,3061,2700,2050,3049,2928,2081,2748,2980,2028,3100,2997,1927,3143,2883,2058,3176,2793,2050,3149,3006,2038,2932,3057,2069,3173,3063,1969,3120,2989,2098,3212,2825,2146,3224,2978,2164,3021,3138,2089,3251,3150,1925,3273,3075,2146,3270,2909,2188,3168,3102,2176,3037,3187,2200,3353,3116,2012,3358,3169,2180,3386,2951,2170,3320,3177,2269,3122,3294,2244,3326,3277,2074,3409,3248,2260,3477,2945,2252,3436,3292,2311,3265,3384,2181,3464,3334,2126,3510,3350,2289,3420,3096,2334,3489,3307,2405,3300,3339,2321,3559,3455,2166,3625,3431,2282,3570,3169,2392,3568,3441,2439,3268,3490,2384,3647,3499,2199,3707,3387,2396,3716,3260,2419,3701,3516,2396,3438,3537,2452,3698,3618,2290,3650,3551,2458,3773,3299,2522,3754,3485,2512,3531,3640,2480,3807,3706,2247,3832,3620,2495,3831,3406,2573,3699,3628,2561,3605,3713,2565,3887,3614,2366,3903,3703,2537,3942,3499,2528,3869,3734,2640,3625,3837,2599,3815,3825,2421,3978,3765,2627,4058,3406,2606,3987,3816,2675,3778,3909,2547,4033,3909,2462,4064,3835,2649,4001,3590,2708,4048,3872,2762,3851,3889,2685,4096,4043,2498,4161,3968,2636,4166,3684,2770,4136,3991,2790,3756,4047,2746,4213,4044,2573,4284,3932,2768,4272,3735,2802,4247,4077,2773,3934,4127,2795,4272,4199,2641,4168,4097,2819,4370,3821,2901,4353,4005,2905,4017,4243,2819,4391,4273,2590,4402,4197,2898,4421,3954,2956,4259,4121,2961,4131,4300,2956,4460,4211,2724,4501,4307,2916,4519,4050,2869,4493,4282,3026,4166,4400,2994,4408,4394,2752,4616,4338,3034,4631,3973,3033,4603,4421,3103,4313,4462,2950,4637,4489,2832,4666,4434,3091,4584,4143,3128,4625,4473,3165,4410,4419,3092,4721,4588,2857,4825,4536,2998,4784,4229,3199,4740,4586,3218,4327,4625,3174,4777,4622,2947,4882,4490,3166,4873,4297,3218,4858,4655,3165,4482,4699,3206,4891,4773,3018,4796,4662,3218,5001,4345,3279,4930,4583,3298,4639,4817,3230,5015,4864,2974,5018,4736,3313,5036,4446,3355,4791,4786,3368,4698,4898,3320,5044,4794,3099,5114,4869,3321,5183,4526,3284,5070,4866,3405,4754,4976,3392,5009,5003,3131,5230,4924,3395,5278,4393,3442,5174,4990,3486,4873,5065,3324,5271,5091,3212,5199,5070,3490,5196,4693,3523,5262,5044,3589,5009,4981,3458,5370,5188,3266,5440,5167,3410,5430,4786,3610,5358,5150,3663,4900,5259,3531,5448,5260,3363,5544,5093,3580,5478,4909,3643,5503,5272,3553,5080,5356,3636,5556,5419,3344,5429,5274,3667,5642,4965,3733,5588,5150,3762,5231,5428,3681,5649,5506,3341,5650,5354,3750,5702,5051,3754,5453,5426,3803,5340,5541,3784,5750,5431,3491,5840,5503,3691,5807,5146,3705,5765,5540,3880,5366,5638,3863,5664,5634,3568,5903,5531,3888,5936,5047,3909,5873,5649,3940,5452,5780,3778,5924,5749,3620,5985,5675,3950,5855,5286,3959,5961,5674,4031,5605,5649,3955,5987,5884,3678,6080,5748,3879,6102,5374,4047,6048,5827,4117,5472,5875,4005,6086,5939,3754,6274,5681,4032,6237,5479,4083,6196,5925,3932,5777,5985,4056,6219,6048,3804,6089,5929,4106,6322,5461,4192,6245,5837,4203,5856,6126,4132,6333,6163,3741,6319,6034,4199,6439,5635,4251,6117,6084,4278,5978,6147,4182,6463,6037,3911,6506,6143,4188,6568,5751,4195,6436,6125,4340,6034,6292,4288,6356,6287,3992,6571,6215,4310,6596,5663,4350,6588,6309,4418,6153,6411,4199,6633,6351,3989,6670,6360,4384,6535,5890,4416,6638,6314,4506,6254,6248,4359,6717,6514,4105,6806,6459,4300,6817,6007,4483,6663,6480,4537,6067,6559,4454,6841,6580,4162,6959,6320,4448,6937,6086,4560,6896,6529,4413,6421,6647,4516,6891,6627,4235,6770,6612,4571,7032,6134,4628,7006,6444,4634,6427,6753,4538,7012,6809,4151,7071,6712,4615,7059,6249,4647,6826,6744,4688,6616,6822,4665,7129,6668,4323,7163,6687,4686,7232,6390,4610,7138,6807,4779,6686,6963,4747,6925,6990,4327,7307,6848,4787,7357,6229,4828,7272,6949,4789,6806,7080,4651,7241,7107,4454,7404,7030,4854,7174,6463,4893,7352,7044,4930,6906,6901,4882,7401,7231,4517,7473,7153,4726,7509,6622,4963,7425,7156,4965,6776,7202,4857,7528,7247,4612,7659,6997,4958,7656,6731,5001,7538,7189,4898,7062,7359,4996,7608,7411,4681,7459,7275,5020,7666,6759,5107,7685,7093,5124,7130,7467,5065,7761,7563,4549,7783,7377,5110,7821,6908,5150,7553,7429,5193,7227,7456,5172,7831,7376,4771,7862,7517,5174,7964,7060,5073,7780,7531,5259,7341,7675,5178,7676,7612,4839,8004,7549,5218,8071,6847,5306,8002,7686,5335,7498,7818,5094,8021,7632,4921,8103,7717,5316,7896,7186,5373,8105,7736,5409,7447,7684,5313,8199,7926,4974,8228,7854,5225,8244,7288,5386,8202,7804,5522,7438,7980,5409,8269,7961,5086,8368,7607,5458,8342,7370,5463,8356,7976,5422,7769,8099,5489,8292,8140,5133,8213,8018,5538,8412,7430,5590,8459,7855,5539,7859,8201,5560,8531,8297,5060,8550,8073,5597,8556,7533,5686,8234,8196,5660,7981,8280,5703,8620,8095,5156,8612,8276,5635,8742,7782,5573,8653,8267,5752,8107,8466,5662,8368,8419,5306,8829,8330,5759,8864,7562,5828,8724,8393,5867,8182,8489,5609,8795,8538,5404,8921,8530,5820,8565,7959,5887,8872,8508,5886,8345,8368,5866,8926,8713,5363,8984,8631,5700,9068,8026,5962,8909,8670,6031,8118,8650,5907,9005,8759,5514,9140,8453,5976,9155,8078,6045,9039,8834,5860,8475,8878,6006,9125,8939,5617,8957,8775,5951,9214,8125,6151,9258,8646,6148,8561,9006,6103,9291,8970,5477,9252,8925,6119,9319,8314,6210,9071,8983,6206,8624,9101,6177,9404,8832,5719,9493,9054,6197,9541,8486,6010,9422,9042,6274,8801,9273,6233,9191,9225,5780,9598,8987,6356,9587,8304,6363,9579,9187,6402,8879,9383,6095,9514,9389,5861,9707,9285,6408,9416,8664,6395,9703,9197,6444,9028,9155,6376,9700,9501,5946,9855,9446,6257,9852,8633,6488,9792,9457,6579,8822,9550,6436,9849,9601,6065,9924,9243,6495,9921,8879,6547,9954,9578,6390,9212,9683,6483,9911,9675,6117,9758,9529,6552,10056,8947,6733,10022,9246,6705,9258,9825,6614,10096,9834,5935,10134,9694,6647,10089,9087,6724,9828,9758,6748,9468,9871,6722,10168,9600,6129,10319,9813,6679,10346,9202,6604,10269,9887,6894,9559,9910,6807,9971,10034,6314,10406,9913,6859,10430,8999,6919,10282,10069,6835,9678,10161,6663,10450,10175,6364,10539,10117,6856,10251,9377,6987,10381,10092,7039,9815,9986,6916,10542,10189,6427,10665,10246,6775,10684,9395,7061,10605,10288,7048,9460,10360,6963,10682,10387,6554,10809,10002,6975,10804,9565,7013,10786,10382,6904,10010,10468,7107,10774,10531,6612,10497,10378,7144,10895,9748,7252,10877,10142,7263,10175,10659,7163,10799,10669,6449,11020,10548,7214,10984,9835,7331,10681,10605,7262,10277,10693,7269,11097,10433,6719,11152,10675,7286,11184,9903,7175,11126,10708,7423,10271,10916,7370,10825,10899,6798,11136,10751,7398,11279,9778,7466,11238,10793,7522,10506,11030,7108,11291,10956,6894,11377,10992,7479,11018,10157,7518,11366,10815,7657,10601,10812,7508,11379,11156,6952,11562,11072,7295,11333,10289,7567,11445,11073,7671,10357,11200,7627,11550,11225,7016,11687,10694,7621,11624,10401,7688,11668,11196,7528,10780,11246,7708,11605,11416,7045,11383,11261,7715,11743,10453,7842,11654,10972,7806,10885,11508,7715,11698,11553,6973,11938,11296,7722,11867,10591,7933,11557,11438,7941,11055,11455,7864,11884,11145,7274,11986,11502,7842,12013,10774,7738,12000,11536,7946,11019,11760,7922,11679,11702,7316,12090,11492,8005,12241,10535,7976,12017,11684,8075,11338,11905,7704,12188,11817,7403,12178,11688,8076,11847,10856,8110,12218,11775,8182,11380,11665,8023,12169,11993,7479,12416,11921,7734,12383,10954,8243,12376,11948,8159,11112,12035,8166,12472,12048,7602,12455,11594,8147,12505,11021,8290,12520,12090,8034,11613,12256,8242,12497,12217,7676,12147,12094,8258,12671,11256,8394,12580,11801,8383,11724,12409,8153,12708,12355,7499,12767,12200,8338,12746,11441,8477,12392,12163,8451,11743,12445,8437,12793,12143,7808,12926,12404,8404,12839,11596,8263,12801,12360,8574,11956,12585,8520,12521,12578,7763,13076,12408,8603,13051,11311,8573,13004,12576,8649,12126,12574,8283,12980,12702,7943,13135,12654,8663,12665,11788,8703,13017,12663,8753,12294,12475,8679,13188,12876,7972,13386,12732,8322,13281,11819,8858,13225,12839,8875,11922,12936,8769,13292,12829,8110,13439,12413,8769,13373,11971,8887,13381,13014,8631,12323,13104,8818,13316,13150,8241,13131,12938,8826,13529,12025,8891,13521,12608,9019,12607,13151,8882,13582,13282,7994,13640,12939,8985,13664,12259,9033,13190,13134,9031,12669,13291,9012,13606,12985,8318,13784,13271,9007,13889,12357,8869,13638,13218,9118,12788,13515,9127,13396,13483,8430,13897,13322,9236,13927,11818,9260,13867,13474,9245,12938,13636,8881,13933,13645,8534,13938,13589,9145,13658,12513,9282,14048,13465,9388,13084,13331,9141,14101,13742,8593,14190,13709,9019,14237,12657,9464,14123,13553,9472,12732,13886,9363,14202,13728,8737,14364,13316,9367,14224,12891,9473,14347,13924,9258,13321,14017,9410,14364,14013,8712,14010,13833,9493,14497,12941,9659,14545,13534,9634,13345,14056,9529,14532,14235,8596,14592,13936,9552,14658,13136,9663,14010,13993,9745,13566,14280,9669,14688,13888,8861,14758,14188,9548,14823,13172,9399,14758,14170,9834,13702,14494,9725,14240,14274,9054,14906,14238,9829,14804,12921,9822,14822,14387,9826,13655,14621,9481,14906,14529,9122,14988,14364,9845,14588,13388,9862,15023,14432,9997,14008,14267,9882,15050,14746,9091,15182,14442,9628,15155,13465,10032,15015,14709,10130,13630,14754,9923,14938,14821,9303,15323,14235,9926,15261,13681,10106,15308,14844,9720,14178,14760,10111,15253,15037,9353,14916,14777,10119,15457,13621,10291,15351,14479,10198,14291,15043,10195,15471,15157,9046,15352,14855,10194,15600,13949,10350,14918,14944,10359,14514,15115,10184,15616,14711,9521,15682,15096,10286,15746,13949,10111,15617,15062,10470,14465,15410,10395,15156,15291,9632,15850,15182,10333,15662,13692,10455,15776,15305,10516,14742,15504,10101,15862,15457,9613,15885,15345,10498,15487,14269,10547,15935,15292,10714,14801,15031,10572,15979,15561,9761,16144,15508,10221,16089,14397,10629,15852,15537,10757,14529,15700,10532,16153,15698,9911,16301,15092,10516,16292,14516,10732,16295,15732,10475,14894,15818,10723,16173,15801,9988,15891,15704,10734,16372,14584,10931,16390,15235,10935,15042,16056,10764,16524,16102,9701,16527,15808,10890,16606,14818,10782,16041,15878,11026,15388,16158,10937,16601,15647,10094,16678,15893,10940,16634,14961,10689,16613,16032,11158,15451,16363,10981,16034,16353,10172,16853,15990,11107,16896,14516,11113,16814,16246,10977,15646,16425,10731,16860,16502,10233,16961,16299,11121,16455,14947,11228,16891,16304,11397,15795,16102,11169,16823,16698,10332,17003,16499,10867,17079,15178,11351,17095,16549,11415,15460,16635,11154,17228,16698,10553,17331,16025,11245,17334,15490,11382,17196,16535,11029,15918,16870,11421,17299,16945,10598,16882,16729,11411,17254,15528,11535,17335,16342,11528,16154,17032,11444,17544,17030,10239,17574,16811,11519,17565,15635,11674,16968,16939,11672,16202,16847,11604,17553,16693,10731,17725,17054,11472,17778,15873,11366,17425,17037,11744,16428,17352,11657,17133,17252,10829,17774,17116,11607,17959,15452,11796,17780,17293,11840,16591,17474,11416,17817,17173,10903,17867,17349,11800,17416,16069,11899,17914,17333,12030,16575,17081,11726,18022,17706,11006,18209,17413,11547,18180,16127,11922,18060,17544,12133,16166,17752,11990,18176,17721,11176,18354,16810,12001,18227,16460,12089,18271,17593,11849,16977,17836,12089,18134,17989,11204,17876,17727,12092,18524,16441,12116,18480,17206,12139,17150,18032,12168,18520,18097,10916,18611,17862,12209,18439,16548,12370,17939,17859,12354,17246,18080,12326,18662,17740,11328,18588,17941,12275,18796,16856,12052,18694,17999,12443,17327,18384,12230,18219,18311,11395,18983,18037,12458,18964,16383,12511,18803,18004,12527,17642,18511,12036,18751,18508,11556,19011,18401,12510,18300,17001,12567,18997,18307,12735,17671,17939,12486,19059,18654,11460,19286,18469,12209,19294,17181,12771,19105,18599,12739,17200,18519,12643,19287,18746,11784,19259,18018,12610,19364,17369,12752,19024,18827,12448,17986,18893,12755,19360,18954,11865,19002,18746,12568,19524,17157,12928,19567,18280,12975,18066,19053,12767,19561,18939,11535,19658,18854,12761,19612,17560,13035,18968,18913,12990,18002,19211,12946,19758,18704,11993,19663,19026,12954,19906,17776,12552,19630,19007,13189,18338,19498,13054,19251,19252,12141,19977,18871,13179,19999,17325,13235,19905,19327,13196,18667,19585,12560,19766,19578,12235,20118,19393,13206,19551,17936,13287,20103,19380,13293,18548,19047,13195,20182,19812,12301,20356,19566,12934,20234,17876,13447,20114,19544,13506,18224,19803,13313,20353,19782,12401,20209,19073,13371,20493,18334,13396,20412,19728,13192,18926,19914,13347,20430,20030,12507,20031,19739,13469,20491,18349,13759,20538,19104,13697,19120,20145,13587,20701,20228,12228,20815,19678,13621,20551,18649,13781,20040,20056,13727,19254,20224,13747,20856,19730,12452,20924,20053,13687,20970,18768,13389,20722,20142,13923,19364,20274,13801,20123,20469,12786,21044,20140,13887,21139,18255,13893,20736,20420,13930,19622,20544,13466,21071,20591,12882,21268,20429,13808,20606,18952,14051,21164,20382,14072,19730,20057,13996,21312,20635,12879,21446,20625,13606,21414,19074,14174,21243,20836,14247,18903,20912,14013,21464,20894,13040,21648,20095,14138,21634,19226,14080,21505,20755,13919,20003,21027,14115,21550,21162,13219,21042,20628,14127,21659,19359,14460,21622,20253,14413,20103,21282,14227,21665,21171,12866,21746,21003,14334,21911,19712,14530,21091,20992,14351,20306,21295,14427,21986,20606,13341,21904,21236,14381,22049,19516,14143,21898,21235,14684,20355,21614,14300,21397,21578,13429,22041,21267,14568,22238,19235,14647,22156,21463,14654,20458,21745,13913,22209,21682,13540,22284,21584,14705,21669,19889,14773,22227,21113,14932,20728,21240,14717,22355,21964,13586,22578,21708,14280,22379,20054,14755,22362,21833,14941,20185,21914,14771,22558,22003,13644,22764,21137,14890,22493,20358,14949,22611,21951,14515,20875,21813,14879,22588,22313,13898,22069,21720,15005,22839,20398,15169,22525,21455,15144,21116,22302,14969,22860,22411,13405,23093,22023,14917,22912,20623,15272,22127,22154,15246,21332,22436,15212,22749,21623,14032,23041,22271,15163,23204,20764,14845,23057,22359,15338,21148,22536,15195,22442,22684,14114,23320,22276,15391,23389,20287,15283,23179,22568,15312,21715,22855,14836,23267,22739,14327,23320,22371,15480,22693,20958,15516,23230,22656,15673,21760,22315,15418,23244,23012,14328,23706,22852,15049,23604,20919,15724,23519,22955,15575,21266,23038,15494,23760,23059,14568,23852,22215,15529,23850,21136,15713,23796,23077,15302,21989,23258,15641,23805,23437,14577,22764,23086,15662,24005,21468,15910,23842,22308,15946,22242,23427,15609,24135,23448,14196,24154,23219,15914,24115,21729,15963,23219,23027,16084,22330,23578,15818,24143,22909,14735,24389,23387,15960,24148,21900,15489,24274,23514,16129,22322,23779,15908,23670,23765,14667,24501,23405,16204,24541,21286,16126,24438,23557,16228,22722,23819,15666,24453,23872,14917,24587,23841,16200,23946,22127,16151,24317,23768,16487,22860,23426,16151,24670,24155,15016,24902,23854,15581,24561,22137,16461,24751,24131,16504,22249,24221,16324,24880,23983,15269,25043,23094,16328,25023,22481,16481,24959,24235,16039,22889,24411,16428,24967,24546,15166,24302,24136,16473,25252,22334,16535,25012,23539,16667,23356,24614,16443,25081,24783,14824,25247,24094,16659,25257,22783,16786,24230,24517,16758,23440,24563,16670,25158,24037,15468,25392,24552,16697,25536,22802,16394,25336,24565,16511,23533,24913,16808,24780,24945,15577,25576,24564,16950,25758,21973,16977,25419,24914,17055,23799,25094,16341,25652,25153,15679,25512,25072,17021,25019,23023,17098,25630,24791,17183,24024,24498,16760,25765,25323,15797,26074,25061,16447,26045,23195,17250,25864,25024,17281,23301,25360,17069,25986,25384,15885,25973,24439,17133,25895,23551,17315,26148,25328,16855,24229,25489,17222,26173,25522,15857,25479,25085,17300,26322,23450,17455,26251,24727,17495,24278,25572,17173,26519,25922,15559,26452,25442,17455,26318,23865,17527,25315,25583,17538,24322,25892,17442,26539,25113,16232,26679,25645,17369,26782,23922,17016,26572,25528,17652,24564,26139,17634,25745,25768,16255,26786,25710,17672,26868,23277,17629,26763,25939,17764,24655,26280,17048,26838,26274,16456,26942,26018,17737,26023,24119,17638,26878,26038,17971,24973,25555,17646,27007,26498,16461,27222,25743,17247,27190,24324,18041,27019,26450,18047,24350,26505,17769,26916,26460,16543,27382,25557,17951,27368,24439,18014,27264,26483,17412,25330,26626,18064,27206,26835,16710,26653,26416,18022,27505,24320,18292,27422,25880,18295,25448,26616,18005,27665,27102,16196,27267,26608,18195,27667,24966,18366,26787,26694,18201,25632,27045,18129,27775,26273,16890,27875,26967,18178,28038,24996,17843,27501,26705,18564,25747,27430,18363,27030,27203,17041,28014,26977,18505,27781,24063,18518,27945,27200,18556,26032,27564,17793,28034,27418,17012,28209,27279,18402,27461,25263,18660,28032,27136,18825,26176,26499,18569,28285,27701,17219,28200,27494,18069,28490,25486,18755,28002,27575,18813,25446,27746,18626,28500,27573,17437,28638,26713,18606,28614,25603,18871,28544,27805,18458,26489,27851,18717,28575,27730,17493,27766,27739,18915,28722,25726,19188,28754,27003,19053,26137,28157,18841,28835,28265,16964,28898,27761,19066,28982,25978,19027,27912,27749,19207,26855,28329,19150,29008,27462,17524,29079,27797,19154,29196,26247,18513,29001,28094,19290,26932,28612,19131,27902,28541,17753,29366,27986,19364,29141,25411,19308,29257,28380,19175,27161,28677,18772,29312,28693,17920,29427,28296,19420,28466,26079,19539,29381,28425,19694,27393,27969,19374,29497,28959,17807,29465,28512,18897,29804,26558,19569,29509,28741,19675,26652,28884,19303,29626,28978,18179,29875,27813,19558,29794,26733,19678,29756,28606,19179,27622,28938,19634,29826,29337,18256,28972,28862,19609,29673,26823,19934,30013,28146,19686,27567,29241,19634,30156,29420,17519,30125,28940,19744,30268,27155,20053,28894,29148,20021,27979,29178,19820,30229,28532,18383,30334,29247,19878,30480,27127,19434,29915,29340,20100,28151,29870,19974,29398,29603,18503,30592,29271,19690,30682,26492,20206,30472,29693,20252,28257,29897,19469,30555,29505,18641,30281,29753,20252,29802,27538,20359,30600,29644,20534,28169,29193,20156,30762,29947,18715,30976,29738,19574,30934,27518,20175,30783,29998,20614,27741,30098,20182,31060,30089,18939,31029,28729,20413,31040,27831,20527,31092,30102,20012,28603,30414,20402,30668,30585,18916,30326,30043,20535,31298,28003,20738,31107,29066,20558,28926,30628,20561,31491,30661,18459,31428,30280,20721,31264,27986,20763,30334,30326,20860,29132,30706,20700,31513,29774,19213,31375,30475,20730,31513,28464,20255,31507,30461,21031,29312,30883,20578,30738,30884,19282,31893,30434,20987,31949,27680,21119,31665,30538,21111,29516,31232,20262,31670,31132,19204,31977,30961,21069,30730,28520,21189,31815,30955,21401,29712,30199,21055,31912,31432,19216,32151,30955,20470,32199,28765,21321,32041,31284,21427,28857,30772,21201,32177,31462,19747,32291,30104,21256,32383,29000,21430,32024,31421,20577,30015,31573,21279,32317,31760,19776,31549,31330,21121,32502,29010,21536,32266,30553,21566,30151,31906,21338,32652,31563,19249,32711,31493,21591,32651,29286,21662,31616,31608,21716,29949,31921,21620,32751,31027,20005,32923,31723,21423,33018,29576,20877,32899,31562,21896,30421,32364,21684,31954,32245,20097,32830,31415,21831,33274,28764,21941,32886,32019,21962,30541,32528,21091,32827,32107,20207,33332,32295,21874,32287,29736,21939,33246,32167,21940,30934,31561,21577,33357,32600,20227,33522,32362,21338,33458,29637,22152,33429,32497,22254,29622,32716,21973,33480,32604,20442,33295,31398,22063,33651,30296,22215,33661,32356,21645,31167,32940,21876,33634,32989,20508,32734,32566,22168,33809,30272,22362,33745,31400,22397,31360,33188,22237,33833,33282,20031,33979,32761,22188,33433,30594,22552,32766,32965,22501,31561,33095,22503,34151,32331,20545,34194,32847,22411,34338,30759,21974,33981,33124,22748,31621,33285,22563,33067,33499,20740,34373,33034,22659,34621,29969,22677,33746,33408,22767,31936,33665,21995,34271,33622,20981,34653,33525,22458,33482,30954,22874,34531,33518,22952,32065,32548,22748,34535,33582,21041,34827,33658,22124,34917,31156,23104,34622,33834,22944,30661,33864,22852,34861,33945,21271,34984,32725,22956,34972,31401,22916,34662,33942,22500,32458,34275,23008,34792,34288,21422,33985,33625,23002,35223,31220,23342,35071,32987,23386,32523,34488,23062,35022,34512,20717,35287,34043,23018,35455,31848,23475,34156,34170,23228,32726,34459,23252,35468,33596,21613,35268,34257,23292,35664,31633,22843,35486,34409,23638,32808,34925,23440,34464,34583,21656,35325,34394,23477,35637,31056,23564,35542,34640,23718,33226,35081,22418,35769,34990,21799,36051,34828,23607,34886,32105,23698,35852,34284,23915,33094,34224,23600,35841,35303,21905,36276,34979,22970,35871,32497,23919,35977,34811,23905,32390,35323,23725,36235,35422,21869,36329,34006,23926,36287,32645,23837,36316,35277,23372,33540,35100,23951,36169,35792,22295,35387,35242,23997,36298,32811,24224,36135,34302,24287,33848,35807,23858,36564,35925,21517,36726,35012,23944,36793,32998,24350,35507,35534,24293,33926,35969,24255,36861,34404,22278,36856,35737,24198,36969,33354,23545,36780,35790,24542,33747,36354,24365,35578,36226,22537,36889,35726,24404,37212,32311,24297,36961,36045,24607,34333,36261,23781,37052,36258,22675,37278,35826,24391,36246,33394,24752,37157,36163,24706,34595,35528,24562,36917,36541,22708,37471,36431,23847,37663,33452,24826,37036,36594,24650,33661,36726,24688,37468,36674,23049,37718,35329,24666,37698,33241,24916,37522,36756,24252,34794,36849,24749,37652,37311,23029,36282,36634,24632,37908,33999,25223,37794,35548,25018,34985,37151,24628,37983,37317,22456,37788,36750,25088,38212,34390,25241,36716,36460,25274,35246,37129,25170,38130,35923,23293,38331,37197,25068,37904,34635,24497,38205,37135,25391,35428,37650,25112,36953,37540,23064,38457,37124,25349,38641,33603,25416,38374,37286,25572,35326,37547,24599,38491,37738,23403,38613,37522,25454,37374,34838,25628,38206,37264,25747,35842,36827,25475,38600,37949,23592,39014,37602,24487,38953,34915,25569,38811,37815,25802,34872,38025,25652,38803,37735,23849,39223,36597,25703,38638,35165,25771,38955,38018,25154,35800,38225,25678,39003,38685,23909,38018,37602,25814,39405,35199,25765,39140,36905,25985,36272,38592,25922,39420,38653,23103,39344,37724,26068,39548,35689,26235,38038,38265,26206,36601,38700,26178,38924,37678,24058,39654,38585,25970,39782,35668,25456,39656,38477,26046,36590,38775,26205,38483,39052,24176,39973,38560,26328,40055,34447,26402,39751,38778,26261,36985,39174,25298,39864,39093,24316,39590,38933,26480,38922,36139,26469,39691,38851,26704,37282,38163,26090,39986,39181,24529,40402,39251,25640,40418,36019,26666,40112,38859,26914,36145,39526,26466,40357,39622,24740,40420,38013,26406,40208,36343,26784,40533,39494,26031,37390,39763,26568,40587,39879,24601,39167,39412,26647,40775,36593,27038,40601,38384,27030,37660,39713,26786,40869,39844,24119,40881,39651,27024,40870,36756,27121,39106,39737,27128,37776,40257,26901,40937,38936,25050,41178,39853,26639,41261,37072,26461,40921,39801,27258,37695,40529,27248,39826,39896,25101,41357,39932,27289,41429,36081,27377,41177,39937,27309,37992,40633,26384,41318,40616,25285,41497,40299,27327,40396,37331,26897,41363,40279,27679,38562,39371,27264,41430,40835,25334,41908,40090,26647,41525,37621,27659,41445,40791,27868,37441,40905,27517,41199,40923,25487,41964,39120,27700,42152,37807,27753,42016,40975,26681,38861,40988,27688,42088,41384,25421,40828,40698,27686,42154,37507,28082,42106,39797,27984,39089,41395,27829,41931,41673,24838,41952,40912,27935,42433,38348,28153,40962,41137,28143,39185,41287,27820,42501,40304,25791,42592,41397,27931,42477,38481,27363,42412,40976,28137,39398,42044,28131,41265,41781,26018,42708,41522,28254,42572,37294,28236,42371,41533,28401,39658,42147,27268,42849,41839,25884,43054,41861,28347,41693,38451,28468,42777,41556,28663,39749,40403,28218,43053,42427,26251,43085,42121,27291,43231,38852,28629,42537,42133,28765,38525,42394,28492,43134,42328,26441,43093,40829,28255,43475,39148,28687,43339,42334,27896,40177,42523,28559,43338,42063,26602,42288,42291,28770,43543,39075,29007,43604,41187,29005,39882,42932,28346,43648,42856,25865,43819,42304,28847,43865,39662,28826,42271,42538,29049,40230,43085,28906,43972,41805,26832,43780,42167,28949,44084,39938,28333,43937,42550,29255,40652,43475,29056,42054,43204,26855,44224,42805,29170,44414,38657,29052,44187,43044,29131,41018,43487,28232,44245,43532,27047,44473,43231,29335,42807,39351,29375,44305,43258,29613,41175,42311,29231,44456,43901,27213,44198,43226,28495,44771,40279,29599,44388,43603,29624,40077,43754,29181,44771,43793,27303,44957,42387,29498,44987,40471,29786,44880,43413,28725,41428,43950,29687,44502,44387,27609,43696,43769,29640,44564,40490,30039,45107,42634,29961,41652,43808,29680,45297,44362,26416,45449,43865,29913,45439,41006,30108,43750,44061,29849,42056,43983,29947,45277,43224,27705,45385,44334,29780,45767,41229,29271,44599,44329,30227,42129,44785,30148,44010,44638,27694,45790,44268,29855,45957,39535,30365,45435,44584,30367,42471,45044,29286,45858,44517,28007,45986,44662,30229,44578,41373,30445,45914,44710,30682,42135,43709,30292,45966,45099,28060,45981,44948,29496,46184,41666,30115,46025,45004,30887,41457,45448,30452,46253,44962,28321,46580,43207,30620,46465,41892,30457,46350,45276,29965,42909,45614,30370,45896,45737,28417,45210,45145,30666,46555,42002,31003,46646,43744,30586,42715,45712,30662,46895,45929,27655,46745,45426,30907,46932,41997,31096,45208,45060,31198,43203,45940,31017,46932,44640,28537,46533,45761,30905,47227,42741,29918,46810,45564,31217,43580,46271,30515,45581,46178,28732,47380,45843,31249,47123,41306,31311,47079,45566,31337,43741,46646,30248,47221,46235,28695,47295,45969,31267,45529,42801,31467,47329,46164,31501,44041,45037,31270,47523,46792,28396,47613,46316,30424,47825,42829,31621,47509,46405,31767,42773,46264,31464,47312,46909,29317,48004,45052,31421,47858,43196,31701,47342,46854,30765,44303,46572,31638,47896,47203,29341,46508,46565,31356,48149,43074,31995,48157,45421,31734,44578,47367,31707,48101,46879,28552,48170,46865,31935,48362,43727,32124,46256,46982,32076,44292,47334,31992,48530,46067,29506,48577,47029,31902,48812,43557,30829,48383,47035,32079,44850,47840,32048,47136,47814,29685,48799,46674,31947,48983,42600,32279,48497,47565,32440,45234,47991,31079,48232,47633,29809,48670,47928,32391,47541,44072,32425,48992,47541,32285,45332,46553,32197,48882,47839,29961,49247,47982,31409,49322,43779,32573,49082,48230,32880,44085,48226,32232,49282,48187,30072,49109,46413,32436,49480,44706,32741,49385,48332,31775,45528,48430,32251,49327,48846,30347,48016,47952,32590,49706,44674,32936,49671,46054,32966,45874,48749,32773,49549,48903,29407,49856,48406,32878,49357,45183,32807,48000,48562,33196,46206,48765,32922,49968,47557,30108,50099,48532,32943,49827,45291,31878,49867,48584,33253,46263,48737,33274,48569,49230,30576,50263,48357,33220,50455,44065,33301,49669,48866,33383,46713,49481,32101,50319,49376,30418,50610,49278,33017,49018,45533,33354,50355,49106,33749,46656,48060,33361,50171,49201,30864,50867,49538,32379,50657,45635,33631,50616,49575,33861,44917,49472,33314,50818,49775,31097,51068,47980,33457,51237,45975,33382,50974,49626,32520,47160,50038,33662,50850,50034,31245,49425,49150,33587,51369,46150,33977,50731,48362,33968,47296,50376,33558,50811,50368,30305,51155,49981,33868,51517,46187,34063,49726,50007,33645,47527,50463,33948,51634,48967,31437,51515,50253,33566,51700,46139,33049,51493,50214,34327,47607,50826,34199,50082,50643,31494,50845,50445,34233,52093,44976,34267,51653,50449,34440,48154,51170,32671,51829,50641,31779,52191,50800,34332,50471,46991,34484,51556,50093,34581,48300,49682,34084,52099,51337,31813,52365,50949,33314,51795,47136,34618,52194,51082,34676,46492,51269,34442,52297,51433,31663,52629,49365,34625,52697,47533,34645,52405,50945,33958,48705,50911,34650,52484,51793,32234,51033,51079,34727,52782,47481,34727,52149,49729,34860,48764,51882,34657,52650,51957,31252,53006,51458,34564,52675,47777,35019,51291,51622,35133,49006,51845,35160,53114,49944,32246,52990,51453,34911,53301,48190,34237,53105,51728,35337,48511,52413,35216,51404,52375,32254,53302,51542,35235,53733,46579,34948,53195,52124,35307,49593,52653,34168,52938,52341,32774,53698,51795,35441,51855,48316,35528,53392,52233,35733,49881,50762,35297,53020,52774,32741,53808,52465,34090,54019,48507,35487,53731,52652,35265,48314,52825,35489,53878,52949,33096,54225,50912,35544,54120,48295,35851,53459,52788,34835,49869,53046,35616,53953,53413,33125,52028,52651,35721,54364,48610,36021,54292,51260,35996,49943,53275,35355,54359,53444,32153,54520,53041,35579,54662,49376,36170,52757,52475,36241,50402,53569,35924,54508,51898,33179,54159,53450,35992,54301,49576,35062,54599,53245,36409,50550,53886,36161,53009,53176,33072,54946,53193,36363,55161,48147,36349,54804,53620,36543,50951,53558,34722,54982,53925,33607,54966,53807,36468,53429,49904,36580,54675,53493,36752,50799,52602,36349,55196,54180,33727,55438,53992,34844,55574,49950,36659,55254,53861,37041,49748,54417,36367,55489,53770,33972,55726,52606,36653,55729,49999,36551,55616,54514,35824,50946,54562,36642,55572,54985,34137,53911,54152,36681,55619,50266,36676,55531,52743,36997,51679,54801,36976,55973,55097,33039,55988,53569,36965,56106,50731,37190,54215,54589,37078,51882,55134,37058,55473,53604,34022,56343,54790,37133,56589,50907,36080,56109,54809,36884,52127,55309,37193,54203,55389,34322,56533,54941,37396,56575,48843,37410,56475,55206,37545,52517,55342,36124,56059,55627,34643,56138,55358,37503,55206,51336,37542,56624,55206,37582,52775,53979,37050,56756,55726,34537,56895,55540,36336,57181,51279,37794,56473,55140,38002,51089,56032,37598,56998,55998,34997,57257,53878,37649,56736,51293,37796,57177,56206,36760,52880,56083,37690,57232,56357,34770,55586,55923,37513,57430,51755,38172,57403,54203,38164,53010,55923,37905,57550,56698,33956,57095,56071,37944,57707,52265,38149,55126,56202,38263,53370,56784,38116,57833,54508,35241,58033,56284,37712,57972,52501,37144,57739,56069,38381,53627,57093,38132,56136,56404,35318,58052,56580,38365,58156,50979,38388,58150,56805,38571,52678,57247,37106,58045,57237,35537,58302,56959,38547,56735,52679,38159,58163,56330,39019,54231,55697,38392,58306,57451,35647,58698,56610,37492,58709,52864,38554,58482,57393,38993,52456,57469,38697,58044,57474,36010,59138,55482,38781,58528,53265,38919,58912,57588,37469,54292,57597,38909,58916,58120,35980,57099,56792,38826,59240,52809,39222,59059,55790,39240,54661,58133,38992,59116,58335,34719,58656,57643,38882,59243,53636,39396,57279,57791,39425,54842,58175,38839,59017,56418,36309,59505,58189,39153,59821,53622,38328,59349,57184,39560,55193,58362,39378,57636,58492,36319,59667,58195,39385,59488,52277,39653,59548,58488,39429,55382,58882,38027,59912,58725,36074,59993,58662,39725,58258,54045,39749,59455,58498,39984,55597,56384,39624,59970,59057,36755,60170,58776,38563,60460,53915,39949,59425,58984,40074,53968,58801,39702,60153,59130,36978,60772,57154,39042,60390,54457,40157,60494,59015,38897,55973,59352,39956,60318,59049,37062,58374,59123,40009,60837,54794,40255,60560,57390,40227,55555,59700,39934,60783,59523,35853,60823,59144,40127,61074,55214,40061,59028,59234,40603,56469,59950,40066,60904,58095,37327,61180,58739,40384,61411,55429,39324,61161,59567,40726,56244,60526,40483,58668,60090,37311,61423,59660,40675,61552,53705,40637,61484,59568,40424,57152,60599,39297,61426,60469,37575,61688,60281,40897,59861,55066,40233,61640,60102,41102,57205,58741,40773,61634,60725,37744,61325,60423,39525,61612,56061,41065,61871,60290,41313,55266,60750,40503,61983,60801,38001,62253,58328,40915,62301,56205,41298,62241,60202,39958,57320,61148,41112,62156,61139,37841,60431,60685,41019,61935,56254,41420,62377,59044,41497,57921,61292,41071,62017,61608,36518,62700,60912,41201,62930,56799,41581,60581,61110,41652,57877,60399,41552,62748,59666,38301,62818,61331,41288,63313,57137,40416,61912,61341,41542,58174,62054,41684,60950,61844,38242,62858,61336,41346,63490,55215,41832,62798,61744,41925,58602,62186,40329,63148,61248,38667,63480,62080,41679,61370,56920,41948,63333,61669,42350,58061,60412,41860,63389,62345,38659,63705,62160,40287,63879,57188,41620,63493,62086,42439,56926,62680,41985,63648,62438,39118,63465,59560,41990,63799,57746,42366,63614,62454,41168,59053,62868,42167,63327,62588,39221,62109,62456,42176,64123,57824,42552,64233,60479,41857,59246,62955,42019,64214,63282,37990,64363,62589,42391,64600,57683,42683,62205,62808,42854,59018,63064,42562,64574,61451,39291,63826,62859,42521,64793,58569,41505,64480,62474,42947,60046,63598,42195,62459,63428,39468,64731,63136,42967,65138,56763,42634,64780,62729,42963,59970,63893,41565,64838,63873,39585,65207,63656,43003,62047,58649,43199,65045,63220,43382,60392,61905,43006,65045,64236,39310,65486,63133,41700,65638,59010,43302,65208,63945,43489,58662,63531,43178,65362,64347,39827,65739,61902,43173,65416,59275,43489,64785,64292,42339,60840,64244,43270,64833,64874,40335,63829,64084,42919,65975,59411,43589,65957,62296,43756,60879,64398,43533,66038,64331,38998,66173,64279,43565,66043,59899,43761,63937,64206,43651,60474,65017,43809,66489,63082,40407,66171,64640,43693,66632,59943,41975,65870,64601,44164,61212,65544,43867,64242,65200,40679,66615,64300,43988,66939,57770,44137,66497,65058,44371,61547,65813,42335,65866,65434,40804,66915,65448,43909,64945,59947,44340,66917,65125,44101,61988,63734,44176,66854,65347,40860,66717,65597,42885,67250,59886,44393,66988,65791,44854,60150,66079,44297,67030,65535,41118,66588,63514,44247,67428,60874,44622,67592,65940,43274,62331,66047,43560,67171,66419,41367,65534,65863,44322,67697,61048,44755,67453,63171,45035,61931,66494,44713,67675,66764,39947,67764,66075,44802,67360,61310,45001,65692,65747,45147,62812,66545,45005,67963,64680,40995,68149,66228,44879,68468,61849,43367,67845,66262,45286,62947,66475,45088,65909,67051,41470,68320,66471,45284,68354,59990,45289,67472,66693,45183,63225,67349,43767,68336,67185,41829,68686,66574,44837,66473,62019,45507,68456,66885,45736,63633,65240,45424,68619,66882,41497,68987,67299,44064,68835,62196,45650,68649,67351,45900,61074,67629,45473,68127,67745,42098,69195,65220,45430,69451,62476,45387,69182,67462,44513,63857,67332,45597,69150,68215,42240,67098,66833,45564,69488,62604,46291,69278,65586,45752,64118,68314,45761,68752,68314,40988,69109,67567,45858,69859,63008,46299,66962,68067,45734,64308,68220,46170,69789,66418,42572,69963,68133,46069,69792,61959,44816,69894,68159,46292,64644,68876,46161,67463,68838,42703,69433,68289,46070,70513,61493,46239,70019,68354,46398,65005,69075,44338,70173,68900,42949,69996,68745,46446,68094,63623,46680,70180,67480,46923,65332,67169,46438,70094,68923,43038,70657,68971,45038,70073,63611,46636,70652,69073,47141,62873,69357,46120,70619,69523,42832,71019,66741,46638,71072,64152,46904,70882,69222,45739,65147,68892,46566,70803,69929,43492,68689,69323,46748,71129,64238,47085,70500,66782,47273,65786,70130,46933,71156,69867,42029,71308,69631,46588,71575,64709,47068,69116,69613,47417,65741,70063,47306,71477,67569,43702,71398,69862,47146,71423,64865,46069,71560,69791,47475,65628,70719,47422,69515,70210,43835,71958,69428,47307,72262,62906,46993,71812,70265,47646,66834,71033,45988,71946,70805,43629,72210,69823,47513,70018,64749,47660,71944,70370,48239,66915,68890,47548,70740,71158,44053,72420,70776,46204,72632,65230,47945,71877,70898,47725,64775,70598,47828,72581,71220,44310,72742,68514,47848,72817,64832,48162,72746,71268,46230,67270,71274,48036,72668,71725,44582,69839,70967,47998,73179,65781,48471,72440,68872,48543,67468,71562,47495,72937,71885,43043,73430,71505,48207,73356,65885,48667,70875,70536,48542,67672,72155,48506,73100,69757,44776,73467,71703,48058,72916,66623,46927,73377,71567,48716,67834,72503,48673,71312,72041,44304,73166,71814,48704,74149,64609,48813,73631,71604,48966,68333,71933,47133,73719,71877,45118,73869,72111,48733,71825,66698,49022,73203,72078,49309,68473,70580,48322,73831,72767,45143,74443,72485,46895,74109,66998,49119,73998,72662,49416,65923,73020,49059,74259,72230,45379,74450,70353,49130,74536,67372,49104,74483,72322,47875,68243,73157,49254,74541,73695,45534,72407,72750,49134,74938,67404,48728,74857,70221,49685,69200,73495,49288,74683,73923,44322,75125,72328,49454,74570,67951,49912,72565,72959,49629,69062,73733,49671,74380,71594,45783,75315,72914,49584,75488,68227,48348,75281,73247,49425,69730,74132,49559,72655,74136,45613,75396,73348,49947,75827,65183,49923,75375,73750,50259,69869,74440,48259,74923,74151,46186,74993,73882,50027,73692,68363,50186,75629,73777,50333,70282,71744,49352,75762,74596,46427,75856,74355,48417,76195,68583,50306,75907,73662,50125,68012,74728,50097,75908,74551,46652,76316,72118,49976,75665,68758,50516,75874,74674,49125,70256,74878,50360,76326,75156,46267,74086,74586,50199,76752,68202,50887,76534,72283,50818,70686,74604,50292,76585,75318,45461,76775,74826,50093,76923,69627,51032,73160,74807,50908,70952,75563,50864,76912,73094,46835,76557,75157,49919,77229,69763,49510,76938,75113,51051,71323,75894,51050,74567,74618,47210,77414,75207,51163,77594,67745,51077,76893,75552,51361,70809,75711,49011,77183,76131,47279,77556,75744,51288,75298,70145,50773,77454,75438,51699,71349,73884,51210,77145,76092,47366,77991,75177,49721,77872,70338,51378,77813,75690,51828,69786,76551,51303,76987,76507,47341,78403,73808,51461,78224,70604,51337,78187,76301,49713,72147,76643,51520,78071,77207,47916,76023,75952,51577,77786,69950,52034,78351,74225,52130,72330,77014,51733,78563,77385,46448,77802,75955,51795,78572,71220,52145,75983,76369,52222,72934,77137,51585,78926,74969,47685,78689,76939,51936,79251,71422,50367,78604,75919,52407,73031,77896,52147,75624,77628,48254,79118,77225,52198,78499,69227,52455,79010,77185,52534,73258,77444,50672,79230,77805,47766,79148,77538,52442,77098,71766,52513,79205,77364,52394,73388,74861,52388,79266,78154,48453,79741,77935,50758,79732,71717,52782,78099,77828,53140,71437,78262,52354,79476,78106,48836,80334,75619,52074,79988,71653,53102,80056,78019,51225,73874,78552,52846,79843,77794,48957,77711,78202,52368,80343,72511,53205,80029,75771,53373,73434,78850,52889,80081,79280,47503,79550,78398,52963,80636,72968,52872,77792,78274,53512,74516,79361,53257,80824,76153,49141,80804,77649,52984,80905,73129,51843,80576,78742,53751,74620,79821,53083,77389,79410,49357,80897,78929,53468,81272,70555,53449,80981,78838,53125,74434,79956,51901,81017,79723,49657,81374,79426,53718,79110,72566,53857,80964,78504,54215,75129,77465,53754,81205,80056,49619,80707,79746,51995,81715,73323,53780,81472,79742,54033,73045,80035,53207,81476,80075,50244,82195,77075,53813,81472,73946,54310,81851,79268,52389,75677,80051,54154,81719,80919,50236,79575,79417,53872,81355,74167,54563,82121,77706,54479,75879,80647,54155,81866,81094,47730,82457,79913,54331,82651,74677,54617,79277,80318,54675,76212,80009,54651,81887,78639,50128,82523,80473,54327,82918,74766,53109,81681,80585,54797,76317,80665,54757,79882,81261,50526,83000,80346,54086,83257,72587,54861,82923,81055,54613,76632,81567,53103,82769,80476,50485,83360,81390,54815,80341,75086,55114,82462,81015,55532,76300,79330,54919,83067,81697,50901,83630,81396,53282,83585,74705,54476,83296,81536,55515,74774,81857,54908,83283,81917,51428,83969,78190,54692,83870,75896,55487,83669,81195,53870,77420,82209,55346,82923,82464,51430,80768,82033,55277,83991,75755,55761,83951,79252,55262,77323,82454,55291,84072,82351,49663,84354,82027,55385,84509,75456,55848,81421,82230,55983,78029,82930,55052,84612,80313,51530,83418,82555,55699,84965,76582,54237,84486,82184,56076,77615,83482,55387,81807,82610,51616,84704,82591,56027,85309,73918,56121,84709,81282,56400,78629,83533,54211,84790,83499,51789,84935,83250,56252,81744,76947,55999,85043,82880,56468,78934,81172,56123,84740,83820,51288,85581,83188,54229,85085,77205,56613,85353,83385,56863,76580,82800,56373,84973,84053,52366,85747,80374,56495,85927,77205,56634,84805,83631,55071,79472,84367,56550,85612,84626,52170,83290,83548,55965,86059,77439,57127,85720,81231,57006,79422,84563,56767,85555,83750,50865,86100,83950,56923,86273,77994,57109,83591,84049,56897,78969,84059,57034,86505,82197,52709,86300,84152,57025,86969,78391,54943,86204,84272,56972,79859,84920,57278,83711,84905,52925,86827,83606,57312,87103,75762,57489,85847,84726,57613,80302,85681,55429,85543,85029,53005,87164,85106,57424,84604,77892,57742,86992,84850,57326,80798,82847,57376,86915,85795,53022,87335,85310,55013,87660,77996,57949,87248,85340,58126,78068,85700,57486,87166,85999,53702,86364,82369,57654,87691,79184,57974,87372,85520,56378,81117,86051,57312,87571,85765,53697,85103,85486,57839,87722,79304,58358,88142,81997,58403,81302,86416,57572,87820,86704,52011,88172,85695,58121,87388,79881,58292,85405,85921,58396,80972,86638,58390,88321,84019,53144,88389,86129,58281,88935,80249,56664,88305,85114,58728,81734,86381,58488,85635,87150,54057,88894,86272,58712,88794,77765,58229,87738,86640,58995,81751,87390,56752,88660,87149,54322,89270,86909,58075,85861,80402,58921,88983,86528,59161,82385,84707,58610,89055,86664,54368,89526,86859,57044,89623,80583,59286,89090,87383,59359,78943,87653,58769,89284,87514,54280,89846,84574,58848,89948,80736,58802,89501,87595,57669,83092,87844,59179,88925,88619,55038,86503,86585,59127,90031,81095,59820,89977,84941,59720,83185,87627,59380,89093,88556,53201,90235,87720,59158,90289,81364,59794,87386,87966,58661,83482,88392,59648,90368,85984,55103,90431,88286,59585,90863,80592,58004,89659,88123,59825,83751,89179,59750,87413,89042,55332,89892,88387,59727,90966,78793,60166,90184,88433,60214,84227,89347,57140,90604,89124,55498,91210,89018,59654,88395,82035,60272,90983,87635,60380,84248,86822,60076,90974,89687,55577,90747,89037,58264,90583,82122,60469,91075,89251,60879,81844,89364,60267,91530,89120,55355,91893,86621,60321,91751,82858,60524,91624,89509,58929,84892,89129,59966,90931,90281,56157,88832,89540,60612,92080,83023,60994,91200,86882,60956,84092,90406,60547,91890,90403,54134,92213,89661,60164,92501,83564,61172,89143,89344,61164,85316,90584,61023,92290,86700,56174,92419,89873,60880,92635,83711,58849,92377,90151,61274,84645,91181,61260,89341,90664,56462,92828,90013,61013,92334,81180,60723,92583,90484,61619,85886,91273,59295,92634,91181,56638,93191,89253,61537,90393,84000,61363,92300,90694,61990,86388,88761,61605,91904,91495,56403,93652,91090,59616,93360,84168,61659,93331,91048,61330,83587,91261,61739,92760,91862,57002,93798,88365,61692,93763,83817,62036,93894,91700,60234,86142,91189,61804,93555,92407,57176,90028,91368,61620,94135,84930,62353,93951,88403,61802,86789,92489,60905,93867,92256,55556,94279,91635,61934,94218,85313,62670,90492,90729,62487,87042,92692,62319,94290,89309,57631,94200,92302,62187,93967,85096,60626,94271,91904,62700,87260,92832,62275,91471,92857,57049,94236,92236,62111,95374,82971,62899,94543,92390,62757,87744,92262,60399,94821,93143,57988,94455,92959,62524,92199,85749,62985,93914,92636,63301,88150,90454,62797,94914,92843,58058,95318,92951,60105,95435,85540,63264,95263,93279,63411,85465,93610,62557,95405,92700,58359,95845,90367,62916,95661,86115,63473,95359,93405,61561,86658,93967,63046,95609,94422,58486,93004,93255,63121,96245,86536,62977,95847,89817,63227,88729,94285,63111,95963,94490,56820,96353,92529,63375,96230,87268,63534,93003,93648,63943,89128,94118,63657,95127,91754,58850,96640,94102,63539,95988,87195,61923,96323,93943,63455,89268,94923,63774,93172,94950,58857,96773,93258,63988,97461,83617,63995,96497,94530,64268,89598,95519,61877,96857,95186,58493,96217,94797,64178,94038,87528,64050,96826,94459,64708,90104,92432,63325,96278,95435,59308,97499,94769,62043,97501,87772,64547,97354,94263,64742,86812,95009,64287,97252,95615,59673,97841,92230,64080,96523,88172,64679,97695,95680,62277,90383,95848,64451,97551,95940,59061,94854,95303,64477,98247,88051,64655,97068,92555,65017,90585,95263,64593,97952,96442,57974,98184,95498,64414,98231,88463,65256,93928,95443,65135,90891,96590,64954,98114,93712,59983,98548,96012,63743,98830,89011,63169,98242,95930,65393,90632,97007,65213,95497,95764,60204,98220,96142,65229,99033,86625,65232,98573,96260,65789,90588,97175,62861,98810,96335,60304,99213,96820,65424,96259,89539,64768,99171,96416,66162,91800,94517,64885,98884,96778,60270,99611,96062,63331,99675,89786,65815,99240,96960,66119,87956,97674,65554,98242,97525,60752,99695,93859,65402,99505,90157,66185,99689,96740,63222,92184,97958,65703,99737,98088,61014,97045,97332,65534,100224,89351,65821,99986,94259,66387,92188,98260,65838,100044,98598,58970,98954,97487,66038,99726,90528,66619,96776,97655,66514,92835,98466,65368,100545,95414,61164,100609,97472,66052,100990,91013,64586,99899,96641,66707,92931,99071,66668,97424,98810,60778,100580,98182,66432,100031,88108,66869,100590,98582,66575,93335,98982,64491,100137,99294,60899,101126,98801,66665,98331,91066,66994,100902,98496,67272,93833,94080,66564,100908,99599,61627,101637,99112,64711,101385,91625,67394,100051,99131,66528,90929,99426,66864,100771,99551,62066,102094,95950,66247,101903,91866,67450,100899,99419,65381,94127,99635,67211,101149,99151,62056,98938,99229,67100,102066,91363,67747,102124,96342,67779,93320,100290,66965,102129,100540,60410,102243,98851,66935,102706,92536,67226,99077,99674,67905,94338,100748,67580,102566,97168,62576,101970,99123,67517,102430,92756,65614,102229,99895,68206,94869,101237,67698,98343,100134,62659,103094,100074,67787,103215,89921,67878,102666,100569,67578,95000,101274,65225,102836,100993,62719,103259,100687,68144,100099,92087,68439,103078,99988,68746,94966,98241,68023,103030,101369,62964,102425,100944,66082,103737,93427,68434,103295,100420,68674,92331,101632,67437,103335,101621,63341,104204,98037,68101,103775,93889,68281,103725,100295,66654,95872,101995,68245,103473,102245,63546,101013,101252,68558,102468,93917,68970,103748,98448,68812,96015,102272,68584,104128,102138,60725,104441,100627,68964,104755,94565,69171,100742,101747,69187,96531,101178,69011,104465,99336,63249,104420,101840,68837,104962,94609,67071,103420,101966,69446,96812,102958,69189,100499,102717,63712,105147,102156,68084,105435,91564,69663,104877,102446,69767,97178,102762,67167,104806,101970,63989,105138,102819,69544,101813,94630,69726,104946,102600,69702,96509,100363,69421,105119,103346,64332,105607,103085,67355,105921,95165,68972,104099,102697,70370,94465,103708,69582,105523,103614,64704,106310,99072,69550,106096,94859,70181,105830,103530,67752,97741,103984,69671,104698,104158,64776,102909,103357,69157,106393,95458,70565,105963,100485,69586,97918,104018,70103,106318,104552,62772,105366,103612,70189,106666,95339,70767,102455,103662,70630,98571,104724,70473,106363,100933,64984,105759,104223,70226,107045,96335,68319,106535,103905,70807,98681,105231,69262,103258,104948,64785,107229,104183,70711,107225,93677,71076,106784,103238,70878,98466,105701,68410,106864,105304,65372,107366,104319,70992,103009,97176,71205,107170,103801,71451,99428,102231,70698,106912,105801,64776,107713,105123,68675,107485,97049,70742,107357,104964,71627,96575,104596,71001,107583,106072,65927,108076,101520,71054,107353,97670,71298,106630,105571,69386,99860,106127,71125,107853,106331,66157,105113,104528,70510,108228,97595,71711,108253,102005,71677,100019,106429,71478,108427,105632,63684,108458,105586,71728,108555,98257,72032,104873,105756,71938,98574,106592,71787,108038,103609,66432,108775,105893,71513,109182,98525,69192,108653,105985,72251,100816,106575,71640,105406,106590,66464,109458,105038,71982,109593,95316,72305,108946,106768,71856,100662,107731,69736,107678,106752,66531,109562,107062,72108,106269,98612,72531,108514,106875,72120,101409,103977,72032,109212,107883,67041,109660,107385,69716,109979,97015,72699,109216,107476,72945,98069,107659,72271,109613,107713,67334,109125,103732,71615,110053,99418,72784,109972,107602,70608,101783,107656,71793,110096,108292,67492,106153,107588,72600,110450,99268,73112,110288,103134,73287,101988,108808,72705,109987,107843,65193,110779,108004,73056,109467,100276,73281,106607,107873,73385,102146,109040,72600,110952,105534,66818,110971,108153,73140,111070,100303,71303,110733,108013,73447,101881,108399,72935,107290,109081,67794,111243,108227,73385,111964,97533,73692,109814,107729,73841,102988,109169,71051,111125,109318,67992,111906,109248,73081,108281,100504,73373,111238,108658,74259,103389,106122,73300,111243,108578,68132,112091,109478,71506,111116,101139,74193,111457,109449,74298,99072,109763,73813,111866,109997,68157,112140,105074,73868,112464,101615,73597,111935,109632,71968,103760,110306,74060,111884,110773,68146,109115,107971,73943,112584,101481,74683,112338,106490,74487,103933,110726,74386,110500,111001,66441,112894,109945,74454,112390,102054,75019,109120,110021,73654,104344,110170,74650,113168,107437,68813,113040,110237,74589,113502,101403,72495,112894,110419,74682,104620,111615,74743,109095,111166,69131,112311,110365,74881,113731,99401,75102,112009,110157,75299,105008,111830,71713,113494,111478,69407,113880,111044,75074,110193,101823,75403,113646,109598,75622,104799,108545,74945,113586,112168,69399,114121,111578,72096,112969,103048,75327,113529,111433,75843,101829,112233,74973,114081,112080,69037,113770,108156,75213,114451,103428,75674,114186,111508,73544,105376,111426,75482,114216,111519,70109,111242,111817,75509,114872,103643,76116,113443,108643,76008,105963,112942,75030,114639,112710,67798,114550,112024,74841,115018,104178,76522,111148,112295,76108,105544,113220,76178,115064,108435,70222,115150,112398,75492,115548,104443,74017,115135,111975,76397,105524,113554,76179,111683,113543,70465,115670,112550,76373,116086,100778,75064,114945,112839,76851,107017,113969,73881,115178,113676,70745,116254,111789,76516,111502,104869,76804,115104,113197,77061,107428,110487,76575,114622,114193,70745,116495,112893,74150,116323,104907,77049,116215,113946,76063,103755,114093,76735,116262,114421,70530,116755,110178,76595,116629,104434,77145,116093,114310,74930,107577,114209,77040,115687,115196,71440,112194,114103,76718,116531,105606,77634,116623,110481,77445,108131,114334,76309,116631,114989,69124,117157,114387,77097,117363,106225,77785,113217,112882,77186,108316,115015,77549,117199,111674,71241,117429,114993,77360,116830,106348,75536,116138,114700,78102,108469,115767,77287,113710,115696,70950,117885,114345,77709,117971,102501,78024,117409,115423,78153,109107,114965,75341,117627,115870,71951,117808,115807,77437,114020,106726,78243,116494,115321,78346,109411,112739,77774,117846,116210,71895,118049,116067,74732,118562,106573,78304,117992,115842,78735,106025,116536,78012,118438,114447,72475,119281,112571,78219,118427,107397,78651,118267,115874,76018,108413,117001,77586,118728,117185,72655,115248,115964,78458,118916,107774,78113,119037,112578,79134,108826,117299,78425,118542,117291,70526,119586,115245,78760,119468,108542,79118,115176,115546,79283,110393,117629,78647,118146,113794,72792,119833,116830,78920,119968,108385,75981,119531,116837,78565,110461,118133,78963,115946,117422,73203,120023,116841,79430,119623,104138,79164,119510,117467,79508,110783,118327,76431,119871,117904,73341,118514,116862,79501,116714,108794,79623,120094,117396,79772,111116,114887,78511,120091,118519,72976,120809,117883,76594,120805,109027,79927,120027,116947,80044,108017,118461,79591,119397,118490,73842,121060,114551,79585,119638,108947,80128,120770,118531,77518,111736,118110,79886,120829,119491,73077,117299,118128,79485,121367,109747,80513,120606,114891,79863,111920,118100,79997,121085,119603,71706,121458,118670,80042,121631,110134,80881,114796,118501,80242,112154,119753,80422,121662,115845,74269,122239,118891,79316,122126,109747,78334,121473,118999,80613,112404,119434,80425,118070,118546,74337,122214,119226,80152,122299,107280,80969,121729,119378,81026,111647,120486,78116,121460,120050,74389,121453,119947,80835,118766,110830,80101,122152,119396,81404,113271,116879,80769,122040,119808,74645,123065,118685,78300,122577,111071,81423,122273,120169,81813,109867,120770,80339,121261,120728,75202,123234,115527,80933,123061,111391,81644,123107,120272,78149,112700,121060,81298,122980,121481,75295,119517,120190,81245,123174,110517,81918,123167,116119,82010,113672,121562,81068,123322,121789,72971,122528,120749,81577,123831,112189,81107,119119,120637,82015,114336,121836,80892,123841,117882,75526,123673,121250,81329,123194,112596,79752,123542,119350,82173,114543,122193,82185,120069,122183,75633,123996,120575,82170,123314,108501,82244,123883,121723,82444,114511,122188,79337,124085,122561,74536,124849,121863,82268,120634,112617,82278,124082,121507,82647,115480,117556,81869,123322,122941,76143,125178,122284,79774,124425,112975,82970,123371,122350,83117,111914,122099,82349,124480,122466,76559,125444,118405,81545,125338,113331,83112,124951,122676,79960,115692,123270,82438,125116,122180,76696,120993,122378,82675,125724,113525,83458,124500,118958,83234,114699,123919,82737,125611,123792,74260,125860,122993,82704,125855,113142,82347,121667,122903,83503,116338,123966,83197,125936,120028,76903,126053,122208,82527,126509,114041,80926,125696,123152,83794,116273,124867,83395,120537,123898,77042,125574,123620,83472,126797,110815,83829,125573,123816,83024,116981,124844,80813,126455,123377,77290,126734,124103,83850,122910,113431,83810,126429,124104,84007,117342,121226,83066,126665,125137,77459,125911,124278,80959,127091,115201,84097,126798,124519,84496,112871,124807,83013,127048,124914,77819,127789,120509,83995,127378,115512,84574,127044,122758,81880,117789,125614,84247,126697,125797,78014,123829,124731,84310,126676,115764,84158,127496,121244,84557,118039,125381,84354,127925,126099,74517,128247,124906,84618,127420,116475,84960,123617,125218,84954,118309,124833,84849,128127,122362,77878,128494,124085,84652,128643,116604,82510,126766,125528,85068,118473,126936,84933,123871,126307,77723,128822,125594,84175,128191,112746,85238,128373,125997,85486,119124,126804,82361,127558,125486,78818,129116,126512,85317,124990,116831,85051,128672,125849,85868,118206,122197,85061,128959,127202,78853,129132,126654,82434,129500,117255,85045,129016,126422,85362,115779,127279,85043,129367,127276,79227,129908,121442,85511,129560,117325,86090,128409,127503,83259,119293,127560,85643,128228,127872,79484,125716,126973,85591,130001,116700,86460,130032,123078,85205,120020,127884,85464,130177,128312,77003,130374,127228,85481,130600,116530,86533,125729,127380,86462,120171,128547,86057,130327,123971,79466,128407,128003,85971,130830,118483,83831,130042,127641,86635,120569,129172,85197,126448,127653,79899,130612,127733,86514,131243,115113,86785,130530,126897,86818,121120,129315,82940,130394,128879,80026,131404,128688,86284,125718,118778,86807,131093,128284,87514,120653,125385,86497,131164,129497,79178,131493,128490,83992,131870,118701,87117,131084,127876,87651,117904,128141,86758,131262,129635,80625,132097,125112};
int main()
{
// freopen("cin","r",stdin);
// freopen("cout","w",stdout);
int i,r,j,flag,num,zz;
double temp;
for(i=3,num=0;i<=20000;i++)
{
temp=sqrt(i);
flag=0;
for(r=2;r<=temp;r++)
if(i%r==0)
{
flag++;
break;
}
if(!flag) prime[num++]=i;
}
memset(ans,0,sizeof(ans));
for(i=0;i<num;i++)
for(r=i+1;r<num;r++)
{
zz=prime[i]+prime[r];
if(zz<=M) ans[zz]++;
else break;
}
while(scanf("%d",&zz)!=EOF)
{
if(zz%2==0)
printf("%d\n",ans[zz]);
else
printf("%d\n",a[zz/2]);
}
return 0;
}