// c=2003 
int sinp[5001]={
3656,914,1766,7544,1886,1208,302,614,2432,608,152,38,1166,938,3170,4376,
1094,1184,296,74,3998,2000,500,8210,5870,2702,1514,1276,1612,3634,1864,466,
676,628,13942,21718,72262,63352,15838,10162,4312,1078,10108,4096,1024,256,64,16,
4,502,4708,1384,346,32896,8224,2056,514,694,7198,5302,13384,3346,1756,4498,
2188,3304,826,139816,34954,10708,3934,3466,1852,1774,27874,10954,3958,9082,8974,40186,
21994,11602,4852,4762,3826,1936,484,592,148,898,838,3088,772,646,2926,5956,
1618,1108,264716,86426,32912,8228,2036,884,668,16658,5564,4052,1262,5678,16928,4232,
1058,3806,4700,13502,13778,4754,2216,554,710,8270,7622,63512,15878,12716,4832,1208,
302,7940,91214,14870582,8365958,6705992,1676498,472394,177650,58454,34136,8534,6056,1514,1070,7370,
3266,5300,1496,374,1466,1052,12644,6596,3212,5024,1256,314,620,1430,2060,3320,
830,3086,12482,11132,7082,3158,3032,758,1682,1352,338,974,16118,10322,3782,9976,
2494,1438,1042,7522,5488,1372,760,190,574,718,772,1474,2086,38626,22984,5746,
7144,1786,3424,856,214,940,1012,2614,1714,6136,1534,1078,1390,1024,256,64,
16,4,1258,11968,2992,748,4468,6064,1516,10780,2524,976,244,3370,8350,3634,
29248,7312,1828,1876,5272,1318,16126,6550,2722,2788,5254,3532,4354,3706,3982,1996,
3868,1228,4504,1126,9052,2200,550,9322,9814,3640,910,844,5758,2662,15046,8170,
31894,9850,6898,7036,1822,1186,1924,1798,10618,85138,50524,6712,1678,1132,1282,1978,
22486,7204,11590,4066,3544,886,2398,1402,7756,43924,72988,14188,13534,5578,26332,5440,
1360,340,4300,14710,25504,6376,1594,3776,944,236,548,2624,656,164,2462,1574,
1094,914,3164,4244,3518,1934,2642,4622,7352,1838,4406,2156,908,674,4946,6566,
2966,1616,404,2804,2048,512,128,32,8,2,13994,8024,2006,1256,314,1436,
9482,31676,5336,1334,1004,692,1454,3626,2978,7862,3452,6854,3074,10148,6674,-66682,
-24502,-9118,-10174,262156,74992,18748,74074,28282,11110,7510,4618,2236,5512,1378,1270,5728,
1432,358,1462,3604,1180,2674,2956,2092,3388,8806,6214,4756,1396,766,8104,2026,
1264,316,19804,10750,27058,2920,730,778,796,3754,1912,478,4702,10048,2512,628,
622,5062,4108,2416,604,2650,1498,1066,904,226,946,3766,5284,4918,433594,163102,
269122,57934,38962,31486,66424,16606,25114,9922,19522,2432,608,152,38,1040,260,554,
644,626,740,932,680,170,1298,992,248,62,1856,464,116,572,1424,356,
1184,296,74,848,212,914,1472,368,92,968,242,596,776,194,578,722,
1352,338,632,158,542,1568,392,98,87562,50518,19450,11752,2938,4546,6238,14884,
13528,3382,1774,1384,346,1600,400,100,18610,181222,68464,17116,3292,1348,2734,1654,
1126,928,232,58,4786,29296,7324,1942,1234,3562,3268,5518,4006,2008,502,694,
766,35074,31996,4130,3590,5534,2582,14282,26234,24542,9710,4148,9422,4040,1010,1946,
5822,2690,2780,1028,1556,5102,2420,3428,2180,1880,470,1460,2774,5372,1514,74348,
11342,4760,1190,23408,5852,1604,1718,1370,4094,2042,7114,4840,1210,1228,8086,9232,
2308,940,2806,4090,2038,3604,4192,1048,262,5596,2842,3166,2794,67876,13234,5470,
3766,32278,29644,34828,20128,5032,1258,47452,14614,14740,4948,4624,1156,724,100276,11752,
2938,1714,1150,4738,2284,2596,994,880,220,1330,1006,1834,4426,3706,1930,2380,
13930,18628,4000,1000,250,958,18062,17654,7190,7250,4184,1046,3362,8042,3524,4658,
8744,2186,1328,332,1364,764,3968,992,248,62,4208,1052,2858,1580,3200,800,
200,50,71828,13976,3494,3236,2402,1682,2552,638,6008,1502,9554,3248,812,2726,
2804,1034,896,224,56,14,2426,1418,1040,260,926,129110,127112,31778,12326,8204,
3578,1850,1202,5426,16358,10472,2618,1490,6584,1646,4670,10040,2510,4532,1358,3560,
890,842,824,206,2588,3506,2240,560,140,1310,27986,30884,6776,1694,15386,6278,
4802,10588,2494,1444,1678,1138,1912,478,688,172,4636,1378,2044,892,676,1462,
10468,4216,1054,904,226,1558,7714,39628,5356,2974,1624,406,3532,200632,50158,19318,
9994,19378,12172,2602,4612,4162,25348,6922,90022,41248,10312,2578,2722,2278,3136,784,
196,1504,376,94,544,136,34,-85418,-125258,-56102,-354218,-247598,-138002,-51242,-81386,-145994,
-81854,-55142,-458186,-106802,-39542,-682268,-190616,-47654,-51398,175034,75308,14630,5996,1634,3800,950,
866,3152,788,1496,374,650,1640,410,47702,18398,14924,3308,1130,1910,1226,1964,
878,1364,1658,3710,5114,2930,7850,5690,3866,12872,3218,37400,9350,4016,1004,698,
1760,440,110,1202,6626,8012,2012,5042,8402,40682,24158,135344,33836,6854,3080,770,
6140,2660,9698,10604,2498,10064,2516,1982,2684,2414,1688,422,668,986,3332,3380,
6176,1544,386,2570,2720,680,170,1370,3596,1184,296,74,1316,9860,8678,3764,
3434,3206,1712,428,590,1058,3314,8336,2084,48188,49226,28964,1280,320,80,20,
518,704,176,44,896,224,56,14,536,134,560,140,524,608,152,38,
5614,10960,2740,1024,256,64,16,4,3286,3124,1096,274,970,874,838,2716,
11746,30418,9448,2362,1396,772,2878,4852,1420,3160,790,1720,430,4690,2212,1204,
736,184,46,4204,2458,1432,358,1618,1348,2134,2476,1972,880,220,3724,7048,
1762,10360,2590,9118,8098,5266,2374,3670,3340,4744,1186,2350,7120,1780,844,1744,
436,592,148,538,712,178,21466,8560,2140,5500,18404,3962,2018,1268,1316,758,
3068,5096,1274,3638,5498,2342,7118,5282,2492,5768,1442,1052,1574,6146,2816,704,
176,44,6758,31826,12446,10592,2648,662,1988,884,4148,1478,9548,10196,4004,1262,
6032,1508,794,1118,11888,2972,2114,1304,326,7058,3158,7814,32876,16298,9656,2414,
2636,5822,3926,4124,2438,16292,3566,3284,2546,1466,4634,2198,16838,38708,6338,2888,
722,782,1718,3878,9062,18854,28016,7004,3248,812,11168,2792,698,37136,9284,2252,
78074,18296,4574,9002,18458,6086,11978,13508,3044,1082,25586,10106,3314,1754,1388,3014,
12464,3116,4628,6356,3194,1856,464,116,8648,2162,1322,5384,1346,1016,254,1694,
3788,512,128,32,8,2,20726,19916,15992,3998,5246,25168,6292,7576,1894,1222,
970,13678,11950,34150,13318,5506,26314,20110,8266,12436,10492,2290,3784,946,4912,1228,
742,790,808,202,7684,6370,12220,2614,1492,1786,2284,940,688,172,544,136,
34,9520,2380,958,2590,1624,406,664,166,574,10762,11308,2632,658,2986,2560,
640,160,40,10,7834,5686,2644,3562,2974,1732,5254,2482,8006,14936,3734,3434,
7370,8654,3758,1922,9950,4244,4226,4946,4064,1016,254,608,152,38,908,6170,
9494,5864,1466,12020,27770,67814,19970,13802,10358,15296,3824,956,692,4604,1376,344,
86,1934,1238,36854,4100234,3462008,865502,325076,158306,102902,233348,50696,12674,13946,76640,19160,
4790,6332,1700,1760,440,110,554,2690,6026,7520,1880,470,3596,12704,3176,794,
3806,1940,3254,5360,1340,764,656,164,1328,332,944,236,5576,1394,2066,2444,
2678,22234,17374,11056,2764,3604,3046,5008,1252,748,27526,30154,14212,3178,1792,448,
112,28,7438,13000,3250,1732,838,2872,718,7330,3262,3118,9532,3964,2398,2632,
658,760,190,1390,2062,10354,4396,6952,1738,6274,2866,1588,8284,2776,694,8086,
14404,3214,7654,8896,2224,556,4522,2170,5896,1474,1066,1198,3532,3928,982,5504,
1376,344,86,1334,2036,896,224,56,14,4196,1490,6152,1538,8588,3290,1748,
842,830,12134,16130,7016,1754,1172,734,3062,3008,752,188,2522,1460,788,662,
1658,1136,284,4358,3002,1640,410,668,3488,872,218,596,626,1076,716,4952,
1238,1982,7940,9398,6572,3134,16688,4172,4052,1274,992,248,62,8218,15184,3796,
16102,9172,48052,40780,10468,3688,922,2932,3682,3358,1774,1180,736,184,46,532,
3904,976,244,2548,3520,880,220,556,2692,2044,898,1792,448,112,28,520,
130,1360,340,5848,1462,1312,328,82,21862,13762,9028,3826,3094,80872,20218,19504,
4876,12214,4336,1084,718,784,196,1342,1018,3304,826,3142,5302,2392,598,9196,
2194,3220,6220,3178,28306,16000,4000,1000,250,2656,664,166,1936,484,1582,1108,
7840,1960,490,21886,8722,8254,3610,11602,18484,6380,1712,428,596,19016,4754,8558,
5480,1370,2060,902,854,836,6212,12698,8432,2108,6182,2834,8480,2120,530,43472,
10868,4346,3734,1916,1172,1730,5570,11240,2810,2870,1592,398,3572,2294,1376,344,
86,548,6974,2864,716,650,3266,8324,9458,10430,3836,1442,7670,3392,848,212,
4238,6002,7514,5516,1550,6128,1532,1118,52172,10298,7082,11348,18764,4034,9296,2324,
9368,2342,1394,3626,27998,20708,11186,11888,2972,20222,6590,2756,14642,14804,7424,1856,
464,116,1322,5126390,1922912,480728,120182,45584,11396,11402,58382,80486,30698,22166,8828,2144,
536,134,566,728,182,584,146,4184,1046,908,686,22904,5726,12260,7622,3374,
4994,4736,1184,296,74,1514,3698,15074,119288,29822,9290,5402,4328,1082,1898,4808,
1202,3464,866,13184,3296,824,206,11474,9614,9404,23390,3512,878,2240,560,140,
542,1496,374,656,164,4516,2824,706,1102,3382,10678,5008,1252,26806,29788,29884,
53278,53482,20572,10876,8824,2206,10996,2578,16708,2956,2122,1312,328,82,1906,11482,
4822,5794,2416,604,4336,1084,6394,2914,2938,1618,2554,1474,1318,2032,508,6442,
2932,1066,916,688,172,2614,5416,1354,1024,256,64,16,4,904,226,4084,
1282,1264,316,7108,32866,12706,3874,2902,20122,8062,14398,76378,29158,17692,9916,45646,
40966,24334,22984,5746,280904,70226,26852,5552,1388,4328,1082,24254,14936,3734,13910,50360,
12590,97988,18890,6218,2654,2786,1562,2534,19688,4922,10184,2546,1472,368,92,2600,
650,1088,272,68,530,716,4706,2282,22460,7610,29948,9716,6404,1718,5300,2762,
1682,1148,1616,404,962,878,8726,48068,9530,14558,9482,3572,4460,5786,4316,16340,
7862,11132,4424,1106,932,692,2042,4622,5516,4784,1196,12452,2852,1052,-14602,-14278,
20470,8194,11866,12448,3112,778,1732,3190,1714,6376,1594,6106,29758,17104,4276,13720,
3430,1804,856,214,598,742,796,1018,1918,2686,3010,3718,1912,478,4996,3124,
3322,2890,2920,730,38612,25664,6416,1604,1748,23654,18308,6446,2936,734,794,3134,
1694,1154,1946,4106,14636,2966,1742,1172,15302,8336,2084,1994,87536,21884,4622,2252,
4052,6608,1652,33602,20198,17888,4472,1118,938,5402,7022,3152,788,54002,42842,2012,
896,224,56,14,524,1298,2048,512,128,32,8,2,3592,898,856,214,
4276,1510,6130,2818,1576,394,3052,3754,3466,5536,1384,346,1006,1864,466,694,
4246,5056,1264,316,6706,3034,1762,1180,1630,3790,3430,8560,2140,1900,3268,1132,
2944,736,184,46,1324,2788,1042,910,1810,1198,1972,1186,964,700,2980,1078,
3376,844,4084,8074,8452,2104,526,1594,1672,418,676,646,2320,580,628,7426,
3304,826,10402,4420,1348,772,664,166,3400,850,838,6578,4016,1004,8234,3608,
902,1808,452,974,2990,4994,4796,7262,13418,5552,1388,4904,1226,980,704,176,
44,1838,4022,4502,5120,1280,320,80,20,524,1448,362,656,164,25514,10088,
2522,1466,1070,3374,5318,4292,1514,1088,272,68,920,230,1430,3662,16922,6866,
7694,11384,2846,6392,1598,15362,17468,9506,3584,896,224,56,14,4094,44278,31372,
7270,2956,1516,3832,958,880,220,562,1618,2212,1924,1948,886,5704,1426,2104,
526,718,790,9724,2344,586,2968,742,1120,280,70,10510,4462,2194,2536,634,
6574,2986,5710,2662,1660,832,208,52,4264,1066,27266,25484,5300,2618,61286,23504,
5876,3518,38408,9602,10580,4280,1070,1214,8582,3740,5180,2984,746,1724,3794,31802,
79754,46166,17834,11336,2834,7826,14144,3536,884,4346,5522,11228,2492,30794,18626,18194,
4388,7016,1754,2240,560,140,548,4586,3884,1250,10040,2510,1736,434,50540,9998,
4004,8924,2168,542,2120,530,4910,2294,1382,1040,260,2588,-86482,-23410,-69934,-33094,
-26734,-29596,-179284,-38002,-31054,-86374,8104,2026,1282,2434,2920,730,796,6646,5044,1468,
3100,5176,1294,4222,38740,7786,3442,1882,1228,4864,1216,304,76,4720,1180,4990,
9346,5836,3988,1270,2020,1198,30124,9778,3664,916,694,1696,424,106,562,1072,
268,1558,2182,2422,2668,2056,514,2110,3718,3070,11038,11794,7516,32854,19786,7942,
4852,1432,358,2602,1498,1084,2938,1624,406,1534,4114,22648,5662,7258,3244,2218,
1354,1030,1936,484,982,1858,2530,3424,856,214,1426,12250,5116,8254,7606,5584,
1396,784,196,95402,63740,52940,57152,14288,3572,1418,34310,62726,2630,7580,3440,860,
1550,2180,932,698,1112,278,2720,680,170,3476,758,17786,5918,3524,1184,296,
74,1928,482,704,176,44,2504,626,6148,8146,64198,24598,9748,3562,19486,8506,
6094,7228,3484,4474,3826,5716,3148,1114,1936,484,2692,16894,5668,5428,2836,2104,
526,35038,8602,2486,2738,2852,2114,8864,2216,554,2960,740,1520,380,596,2744,
686,782,818,1772,2276,1952,488,122,4418,8900,3386,13214,5480,1370,9542,3602,
3338,17702,7946,41840,10460,102490,45142,92626,35260,11230,7630,4072,1018,12586,18418,7432,
1858,1222,3526,5470,4390,10636,6982,8386,3670,13894,14218,4918,10492,4264,1066,4552,
1138,952,238,17296,4324,1336,334,4486,6280,1570,1114,2374,4498,2212,940,842038,
1069972,151384,37846,1840,460,2542,6262,9670,10654,7306,2974,2986,3292,3832,958,1852,
1834,7900,5290,4588,14596,3262,3148,5614,6862,2830,2704,676,652,2770,1564,129076,
449986,169270,218500,41494,221638,189502,107908,20758,199546,195010,73654,97486,108502,240838,205702,176056,
44014,260134,251044,47596,202678,260782,252250,108322,41146,10034,8816,2204,9032,2258,1556,818,
4442,2192,548,998,1934,188234,71114,27194,10724,2348,1976,494,4202,2102,2498,10292,
2456,614,1772,1814,2336,584,146,962,3968,992,248,62,2552,638,3038,175004,
167336,41834,16214,10436,3608,902,5576,1394,-33466,-18382,-18994,1360,340,3898,4870,3964,
1270,1486,1084,730,3118,1696,424,106,4414,2182,2830,1588,3172,3802,5710,2668,
2776,694,4078,2056,514,1606,3520,880,220,568,142,580,1480,370,8140,17506,
11164,2620,1018,5098,10732,2350,1408,352,88,22,928,232,58,2440,610,1660,
838,2224,556,1000,250,6232,1558,39406,15304,3826,8356,8032,2008,502,1324,1108,
16888,4222,2110,1318,6070,1136,284,3182,4586,3452,18992,4748,1418,4640,1160,290,
3542,1856,464,116,1352,338,2792,698,1712,428,608,152,38,542,1076,1622,
4268,1328,332,590,2162,3776,944,236,572,1004,716,662,776,194,7328,1832,
458,5168,1292,770,13160,3290,3170,8300,2084,3386,3224,806,830,3488,872,218,
1442,30170,18290,13982,4856,1214,7490,16412,9290,29792,7448,1862,1226,12458,7232,1808,
452,4574,2210,12004,19780,3706,1918,66166,34036,6910,5380576,1345144,336286,429904,107476,20680,
5170,4096,1024,256,64,16,4,1222,2008,502,3124,1114,946,2314,1396,790,
1852,5464,1366,14950,9730,3274,1756,3250,3286,4366,4408,1102,10276,6652,1558,2176,
544,136,34,934,1846,6490,2962,14752,3688,922,874,856,214,4606,24094,34786,
10708,2536,634,766,22372,6634,3016,754,8920,2230,10810,4582,3898,1990,2440,610,
1096,274,3574,5068,2746,175618,38266,14878,23122,14302,71164,827866,310978,100756,19420,10702,
100270,87112,21778,17182,26038,12428,20366,37424,9356,7370,4052,1496,374,28466,11204,2630,
5912,1478,3350,8540,29924,6140,3050,1784,446,1574,3842,1970,1268,2186,1874,1232,
308,5786,11132,4454,6272,1568,392,98,566,8054,264662,382994,144152,36038,25220,5258,
5696,1424,356,596,1010,908,2702,17774,9020,3860,3158,6752,1688,422,2870,9188,
2252,3464,866,854,3494,5462,31616,7904,1976,494,1730,1178,6758,8216,2054,4358,
8288,2072,518,12908,19232,4808,1202,980,1064,266,1280,320,80,20,1226,2594,
1502,2168,542,1628,1928,482,710,2864,716,2816,704,176,44,4328,1082,22148,
4682,30896,7724,14614,6010,10456,2614,1510,1096,274,4018,4126,4612,4462,2182,1348,
1156,3004,2554,13360,3340,14350,4252,3040,760,190,9268,3478,1834,2356,2020,4552,
1138,21904,5476,12184,3046,1672,418,22390,8926,5686,2662,1528,382,3652,3742,3154,
8296,2074,2398,2932,78766,23080,5770,4570,3118,1804,868,7810,9106,19132,5956,6982,
3148,1120,280,70,556,634,17854,2716,3442,48148,14866,16600,4150,2086,1312,328,
82,4408,1102,3220,2230,1366,1042,4090,13480,3370,4180,2500,3208,802,29194,17746,
26764,5548,1570,8998,3904,976,244,6568,1642,2248,562,10384,2596,4990,4012,1282,
3598,1984,496,124,5704,1426,10546,22072,5518,4666,3658,3382,1798,1204,12928,3232,
808,202,1438,24820,6574,2776,694,790,826,2426,4568,1142,1250,2030,1292,13100,
4262,3722,7298,5432,1358,1040,260,1400,350,662,1556,7286,2978,3002,5054,27248,
6812,1808,452,1454,1076,2762,7808,1952,488,122,2624,656,164,4838,9212,2258,
10886,102092,29858,18122,5576,1394,2114,2516,14612,10700,22874,39344,9836,2312,578,1652,
3218,4856,1214,986,21416,5354,26276,13454,5648,1412,1724,854,2642,7268,4526,2228,
16034,10346,61268,65156,19652,6854,7754,14126,5828,2966,9208,2302,6142,14728,3682,1912,
478,1828,874,5278,3754,14368,3592,898,868,694,5764,1612,8536,2134,4324,1342,
15556,3448,862,572,7562,3368,842,848,212,608,152,38,1352,338,2072,518,
1622,3854,5780,1616,404,1424,356,5312,1328,332,6752,1688,422,1568,392,98,
3746,2048,512,128,32,8,2,932,2126,4322,9316,3952,988,718,802,1870,
1234,2026,4240,1060,1630,1144,286,640,160,40,10,8044,3628,6082,5542,39076,
12322,6730,8458,6370,11728,2932,6184,1546,4408,1102,946,1864,466,1594,6346,36964,
1438,1072,268,970,8182,4570,43174,6748,1798,9352,2338,2518,4300,7696,1924,3112,
778,11590,4192,1048,262,1006,910,874,3268,41560,10390,23842,6022,2626,4492,1564,
826,5374,2548,12556,2698,4138,33244,6766,3070,1684,4978,4132,2494,1468,808,202,
9262,4006,9586,6724,2950,1762,2212,1954,2356,73088,18272,4568,1142,962,3044,36476,
7778,9098,6452,9008,2252,956,9746,30068,10196,4202,3698,1748,1826,4076,1298,15032,
3758,2054,1304,326,656,164,17522,47276,9398,4058,9224,2306,19574,7874,7418,4664,
1166,1262,9236,3932,5318,2528,632,158,3536,884,11114,7586,8936,2234,14768,3692,
1226,2024,506,18596,56888,14222,4934,2384,596,1502,11204,7262,15488,3872,968,242,
4016,1004,722,13148,3746,5696,1424,356,4562,2612,3662,1964,902,872,218,4994,
7634,29636,15038,85562,33686,13166,3998,5966,6052,1786,1204,760,190,2698,1546,1114,
952,238,4642,14200,3550,4684,2524,5938,2488,622,5128,1282,6910,8368,2092,1924,
4048,1012,724,670,7774,3334,4948,1462,2158,7072,1768,442,700,35746,13156,6964,
1840,460,5506,69010,20344,5086,5656,1414,4858,2356,976,244,580,3652,3820,2410,
1438,145402,55060,10858,4606,6424,1606,6316,3112,778,826,844,1714,1732,2302,4480,
1120,280,70,1628,1796,872,218,998,5612,4910,4100,1304,326,28454,30806,33440,
8360,2090,2822,12416,3104,776,194,608,152,38,3410,1814,3590,13874,5738,3806,
5252,1520,380,8666,3374,3236,1142,3506,1850,3244,1144,286,1018,1912,478,1072,
268,586,12496,3124,2218,2476,1000,250,1480,370,7366,3298,5734,2686,1796,1922,
2354,2666,4136,1034,3422,1820,878,866,5636,2732,2522,7916,5960,1490,2180,2066,
2504,626,1694,1172,3044,2198,4574,2252,1256,314,13244,3020,1364,6404,2894,1622,
2630,5474,10010,17030,8516,5546,34526,13484,4790,28436,14546,9524,10388,6932,3098,8282,
126608,31652,10244,3704,926,884,47282,27938,12488,3122,2908,2158,3616,904,226,622,
3376,844,5932,30160,7540,3538,1864,466,712,178,604,1672,418,694,8332,12790,
31366,22300,9910,30076,9802,3310,9064,2266,7876,2014,2476,1780,6472,1618,1144,286,
1504,376,94,1396,2242,1378,1054,1936,484,628,2080,520,130,586,1366,6094,
31204,6388,5050,4078,2986,5536,1384,346,46762,14092,6910,5230,33076,13924,3148,3880,
970,146548,32860,8476,1810,1216,304,76,2584,646,2860,8290,3646,3394,956,2960,
740,1046,1934,5654,4526,24074,9566,10628,10412,4274,2144,536,134,1604,5870,18242,
18836,4070,7460,7598,32822,19808,4952,1238,2042,1304,326,1802,1214,3224,806,13754,
5696,1424,356,992,248,62,13976,3494,8144,2036,920,230,2792,698,800,200,
50,5714,2450,4520,1130,962,2306,2924,2168,542,3014,3926,3554,2014,1294,1024,
256,64,16,4,1348,1726,1186,1372,796,688,172,1264,316,598,1156,1672,
418,1582,1132,1102,952,238,628,2824,706,1744,436,2596,6064,1516,8278,2992,
748,1048,262,3634,3082,5092,2506,15298,9952,2488,622,772,1564,832,208,52,
39382,12094,5074,8854,5944,1486,1096,274,21874,10642,13846,23494,28042,39868,8014,3544,
886,1192,298,18574,7504,1876,7096,1774,1204,2668,1318,17728,4432,1108,6172,1696,
424,106,7306,13624,3406,1816,454,10372,4264,1066,21886,8746,247876,71062,24892,5206,
2344,586,4378,6316,1912,478,718,808,202,5458,2398,1438,1078,1246,1006,916,
10924,10708,83104,20776,5194,8752,2188,13568,3392,848,212,7952,1988,11480,2870,1616,
404,240044,45548,9080,2270,1916,1214,1286,1022,1232,308,1436,9194,5306,4334,33836,
6884,5468,3110,1706,3500,1196,764,1052,5228,1520,380,998,914,9602,16538,10652,
9050,6440,1610,3104,776,194,5864,1466,2174,1556,1880,470,716,674,13136,3284,
8144,2036,1922,6818,30632,7658,12110,11138,18482,18158,169496,42374,16430,8888,2222,2894,
15034,6178,8014,9328,2332,3550,13864,3466,1840,460,1480,370,3712,928,232,58,
562,9976,2494,7546,3370,1804,1858,1468,8518,6142,4630,5800,1450,1084,19696,4924,
18238,27472,6868,1828,2344,586,760,190,11998,29902,27796,5752,1438,15322,6286,7870,
14350,14674,6652,13348,4774,4036,4990,17464,4366,6250,2884,4846,25240,6310,4900,2992,
748,10756,2458,1462,2170,1354,1048,262,1498,1102,3496,874,868,206050,30304,7576,
1894,2416,604,2656,664,166,1444,9220,2242,1576,394,688,172,13186,4654,5410,
4126,26794,10588,3208,802,2668,2116,2602,1516,22612,4780,7114,6194,2864,716,2696,
674,794,2264,566,5114,10622,7328,1832,458,1076,3398,5438,4412,2594,1514,5222,
5774,3992,998,6098,2828,3764,2756,1058,938,8588,4952,1238,9488,2372,986,2378,
1616,404,1004,4316,3722,1994,1508,824,206,13376,3344,836,698,3926,17768,4442,
3836,2432,608,152,38,29102,194168,48542,28658,11288,2822,973226,1050014,591986,222536,55634,
21404,13232,3308,20828,220412,63344,15836,7886,4282,3364,16048,4012,1294,1312,328,82,
7300,7714,9082,23176,5794,7462,3340,1168,292,11674,15940,9298,24796,3868,1492,1774,
1762,4060,5410,7138,8596,3772,37918,63190,24238,10090,7030,3178,3142,1720,430,3328,
832,208,52,6442,4978,10702,3958,2026,2494,3016,754,5356,1546,2224,556,646,
784,196,2656,664,166,604,26254,8332,2104,526,1096,274,379630,61540,75718,28936,
7234,11116,2626,6742,3070,2986,3034,4798,3988,2476,1006,8110,14210,9350,5912,1478,
2486,3212,13850,14264,3566,1880,470,1082,6884,6644,48116,31430,6302,2906,5030,16526,
6740,7508,9290,24794,23498,39368,9842,18584,4646,6434,4976,1244,776,194,1466,3404,
5318,13778,15020,3062,5786,7460,3134,1718,8828,2198,1568,392,98,1412,1754,4058,
6002,71450,62864,15716,7856,1964,1226,8170,5416,1354,4354,2176,544,136,34,556,
3496,874,2338,1420,8512,2128,532,40732,12814,8566,9808,2452,3748,1246,5164,6712,
1678,2302,61972,618928,154732,67858,25990,85300,12946,5398,7582,7684,1984,496,124,1588,
1174,8518,27610,8716,54682,16330,16918,20320,5080,1270,3652,1228,7198,6124,18086,11534,
9782,21794,7082,3200,800,200,50,1994,1292,1724,6848,1712,428,5378,3992,998,
1922,1664,416,104,26,554,752,188,3950,5918,11912,2978,1790,66158,58406,34214,
20606,53036,12752,3188,1142,3614,8996,6350,12536,3134,2168,542,5108,1502,8474,3722,
1940,908,1616,404,620,80144,20036,3770,1958,2462,7538,4814,13802,5720,1430,1934,
10196,2456,614,1706,1184,296,74,572,4784,1196,3506,3452,10454,12668,19202,4526,
6404,6242,2708,1052,2816,704,176,44,1574,2246,2624,656,164,18908,10562,5774,
24092,10106,4334,3932,4244,1340,5270,3788,2426,1454,3812,4316,4406,50306,11870,15128,
3782,3488,872,218,626,2222,4460,6998,-1433800,-358450,-1347646,-1365274,-766606,-2421694,-2616238,-5573200,
-1393300,-656392,-164098,-5818144,-1454536,-363634,-254722,-2292700,-3458332,-5911942,-2216434,-1400104,-350026,-327370,-3446986,-7349530,
-4132750,-1305604,-2770924,-519004,-3340702,-938620,-6257002,-2638108,65614,25150,9976,2494,1480,370,1570,6376,
1594,10210,9868,6538,8104,2026,6196,11098,18472,4618,6484,6466,4294,31954,19336,4834,
37180,7516,1954,16528,4132,2524,1018,21874,13666,11542,6844,1828,1876,2854,1756,874,
47182,18238,7384,1846,3232,808,202,2758,25276,5284,2848,712,178,1462,4432,1108,
2836,3784,946,1894,1486,1102,958,904,226,2944,736,184,46,562,1678,1174,
2470,1648,412,622,778,3244,7696,1924,1972,5674,6076,1684,3298,13150,5476,2902,
10370,11342,7736,1934,1670,1172,1694,4394,3836,3614,4934,2396,1292,788,1586,10208,
2552,638,4874,4106,3674,4610,6482,12638,7310,2804,9884,138530,135776,33944,8486,3728,
932,5024,1256,314,3098,2876,17012,8282,3398,1820,1454,1364,1748,1856,464,116,
2936,734,2288,572,2120,530,5990,2792,698,4388,5954,7616,1904,476,1022,4160,
1040,260,2702,1832,458,1622,1154,3566,1958,1280,320,80,20,1370,2156,950,
902,884,2930,23510,9362,12758,5330,11180,2642,7778,7412,3508,1204,772,9028,5326,
13942,9208,2302,7192,1798,2266,1396,808,202,622,12238,82864,20716,30898,9646,25516,
8542,9802,4222,5164,2818,4654,34324,6982,4516,15856,3964,6166,4834,3034,1684,862,
3322,1792,448,112,28,4456,1114,964,9964,4168,1042,6652,3994,2044,6112,1528,
382,2734,12394,5194,2494,109468,126982,41902,86752,21688,5422,10798,39502,47908,6316,3142,
2896,724,682,802,4024,1006,14914,8272,2068,934,3166,5266,2374,2572,2096,524,
4778,16028,5876,1784,446,13364,203528,50882,19628,10880,2720,680,170,5042,2438,7532,
4880,1220,776,194,620,4256,1064,266,2950,1654,1168,292,3874,14578,14902,6136,
1534,1390,2572,1030,934,898,4738,5674,28978,27052,5620,2140,7666,9070,5812,3004,
2740,15928,3982,6046,2542,3058,5182,2416,604,17494,7108,25150,8032,2008,502,736,
184,46,9724,2326,1420,814,6532,8584,2146,5332,8728,2182,1366,1060,6358,2932,
2194,1408,352,88,22,556,652,670,12958,4000,1000,250,1510,1114,1996,922,
1888,472,118,592,148,1606,1150,1282,12850,13444,5458,11938,17770,11164,13486,6304,
1576,394,3328,832,208,52,1384,346,1564,10690,17980,2920,730,1780,1870,7612,
3652,29482,49894,19258,12202,12886,5380,21688,5422,56194,57226,35458,77110,29464,7366,3310,
3382,1816,454,718,16036,9232,2308,9214,3550,3226,3184,796,3778,1930,9448,2362,
2698,7180,1894,1258,3706,3454,37868,12596,22964,100598,175928,43982,17042,10958,4658,3992,
998,2768,692,27824,6956,10688,2672,668,674,1862,1484,2564,23324,4922,153914,199256,
49814,53132,8432,2108,944,236,2078,1328,332,1304,326,1052,746,3236,2282,4532,
2423192,605798,835028,354884,76436,542372,5504,1376,344,86,2978,2834,2966,7046,2942,1652,
69926,8762,15548,3464,866,2006,4802,5954,7628,12794,104918,5342,2552,638,788,10148,
4226,16496,4124,1322,3722,8222,3632,908,1088,272,68,1592,398,698,8342,13766,
4832,1208,302,662,6476,1952,488,122,4324,1360,340,1306,2542,53212,17938,7276,
412564,58978,22666,7336,1834,1792,448,112,28,1738,1450,1576,394,1072,268,2722,
1570,1138,976,244,12712,3178,3460,1198,3676,3610,3514,14332,5404,4432,1108,67792,
16948,5566,4504,1126,4582,31828,8362,3034,44950,92578,35266,13774,7390,5530,3784,946,
904,226,634,3502,5134,3358,3262,3208,802,850,868,712,178,616,154,2056,
514,742,8068,2062,2386,1444,820,2164,6880,1720,430,3190,8500,6286,15628,9202,
4000,1000,250,3694,13198,39214,12970,4006,4330};
unsigned char cflag[5001+1]={
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
1,1,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,
3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,
1,1,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,
3,3,3,3,3,0,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,
4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9,10,10,10,11,11,
11,11,12,12,12,12,13,13,13,13,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,3,3,3,4,4,4,4,5,5,5,6,6,6,6,7,7,7,7,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,3,3,
3,3,4,4,4,4,5,5,5,5,6,6,6,6,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,
3,3,3,3,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,7,7,7,7,8,8,8,8,8,9,9,9,9,9,9,9,9,9,
9,9,9,9,10,10,10,10,10,11,11,11,11,11,11,11,11,11,12,12,12,
12,12,13,13,13,13,13,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,3,3,3,3,3,
3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,
4,4,5,5,5,5,5,5,5,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,
3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,2,2,2,3,3,3,3,4,4,4,4,4,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2,0,
0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,
4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,2,2,2,3,3,3,3,4,4,4,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,
2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,
3,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,2,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,
5,5,6,6,6,7,7,7,7,7,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,
3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,
3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,
5,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,
9,9,9,10,10,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,
11,11,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,14,14,14,
14,14,14,15,15,15,15,15,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,
3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
1,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,
4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,
1,1,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,4,4,
4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,6,6,
6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,
3,3,3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,
3,3,4,4,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,
0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,
4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,6,6,
6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,8,8,8,
8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,10,10,10,10,10,
10,10,11,11,11,11,11,11,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,3,3,3,3,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,
4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,
6,6,6,7,7,7,7,7,8,8,8,8,9,9,10,10,10,10,10,11,11,
11,11,11,11,12,12,12,12,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,
0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,
3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,
3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,
5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,
8,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,
9,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,
4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,6,6,6,6,6,6,6,6,6,6,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,
2,2,2,255}; //  index=5001 
unsigned int size[66]={
  27,
  71,
  77,
  120,
  60,
  70,
  47,
  43,
  39,
  60,
  91,
  72,
  119,
  74,
  129,
  65,
  85,
  62,
  62,
  92,
  156,
  79,
  76,
  36,
  56,
  79,
  67,
  44,
  76,
  93,
  37,
  27,
  34,
  100,
  50,
  74,
  78,
  98,
  110,
  134,
  81,
  25,
  39,
  95,
  95,
  75,
  38,
  21,
  60,
  84,
  63,
  122,
  73,
  108,
  76,
  84,
  59,
  55,
  154,
  88,
  91,
  83,
  26,
  142,
  98,
  97};
int cval[66]={
2003,2005,2009,2011,2015,2017,2021,2023,2027,2029,2033,
2035,2039,2041,2045,2047,2051,2053,2057,2059,2063,2065,
2069,2071,2075,2077,2081,2083,2087,2089,2093,2095,2099,
2101,2105,2107,2111,2113,2117,2119,2123,2125,2129,2131,
2135,2137,2141,2143,2147,2149,2153,2155,2159,2161,2165,
2167,2171,2173,2177,2179,2183,2185,2189,2191,2195,2197};
unsigned int numbc=66;