// c=1403 
int sinp[3920]={
119948,46508,7154,23234,13946,43322,22112,5528,1382,22910,8942,3704,926,698,2042,11210,
133502,50414,19256,4814,2156,235778,14288,3572,19634,10598,16136,4034,3146,6386,14162,5588,
5918,2570,22262,3752,938,26558,10310,17078,87872,21968,5492,3338,9170,9896,2474,11372,
13028,8330,31010,18320,4580,9332,4850,6022,24448,6112,1528,382,5818,10894,7006,15052,
22558,9694,12352,3088,772,496,124,1036,10486,10516,8734,5896,1474,904,226,436,
676,478,3604,20074,9742,6358,5626,4396,27364,5482,3586,1696,424,106,1318,4522,
2404,802,652,468382,298264,74566,140518,135874,51304,12826,4222,4018,1858,1048,262,28822,
394978,148468,19408,4852,1324,21530,8426,3512,878,2414,3710,13766,8624,2156,6626,2480,
620,8312,2078,5492,1382,1658,974,1334,10838,3758,4844,3404,1838,3224,806,8912,
2228,770,1166,51824,12956,2102,8084,1868,1406,11324,10028,3128,782,992,248,62,
28334,25580,7826,7220,1706,6706,4654,2098,2062,1126,934,880,220,394,2008,502,
1612,844,736,184,46,370,1090,1474,1636,1342,856,214,2422,6058,3112,778,
2332,790,8354,37808,9452,2126,3734,1754,3752,938,1412,2276,10592,2648,662,602,
1334,854,674,5438,3248,812,506,4994,5894,2564,2762,2438,1268,17504,4376,1094,
764,2036,3458,4598,2078,3104,776,194,1844,1406,9782,4022,1862,1052,902,692,
1226,1574,944,236,398,1384,346,484,688,172,934,3148,2878,8620,3310,50044,
26530,14656,3664,916,526,3544,886,14008,3502,11320,2830,6460,4408,1102,21742,597694,
272392,68098,22864,5716,1426,1120,280,70,1048,262,21850,8548,1822,3220,958,3688,
922,700,1978,1096,274,1012,544,136,34,2302,3262,8224,2056,514,1480,370,
724,490,538,556,1042,3436,1852,2464,616,154,412,13264,3316,976,244,400,
100,634,592,148,382,1858,2068,742,14056,3514,1672,418,3274,1582,9520,2380,
3850,1798,8662,5758,5260,2128,532,454,1210,808,202,430,5488,1372,5974,4246,
12994,6766,20326,59758,177532,65632,16408,4102,2416,604,4288,1072,268,5218,8728,2182,
4336,1084,2140,-3602,1394,878,1382,11318,8432,2108,1466,1034,1724,5486,3974,7916,
37364,5876,1448,362,2516,6890,8366,5594,18098,7142,41936,10484,2096,524,3218,1562,
3344,836,512,128,32,8,2,356,422,2200,550,562,2164,1498,1732,7750,
3262,1540,8212,2422,1264,316,856,214,436,1012,1174,796,2542,2362,2218,5296,
1324,604,40096,10024,2506,2080,520,130,2998,1480,370,2002,2890,2242,5728,1432,
358,490,1984,496,124,640,160,40,10,1126,778,4000,1000,250,1030,742,
634,1246,324058,183172,118804,19918,34402,105358,68962,230134,86656,21664,5416,1354,1594,1786,
1894,1066,14716,2692,4594,5566,2188,766,838,670,964,13504,3376,844,514,18418,
17230,20146,18688,4672,1168,292,213736,53434,30946,15440,3860,12974,5222,19334,6062,2630,
1364,2270,1208,302,470,2594,2120,530,1190,1076,5726,2504,626,1244,590,578,
5510,2174,1172,13016,3254,2666,3944,986,18542,7310,3098,10586,28526,11054,4502,29054,
11252,6260,6860,4376,1094,932,1154,3578,4802,4934,2012,734,632,158,416,104,
26,4754,3566,1694,992,248,62,380,428,2432,608,152,38,1846,13150,8290,
3466,1600,400,100,376,94,946,712,178,424,106,1630,1810,1036,2134,51976,
12994,5230,12610,5086,3754,1618,964,538,1522,928,232,58,3862,28996,5794,2530,
1306,27512,6878,12278,7802,3284,974,15686,23570,7256,1814,1916,2510,151544,37886,33668,
796444,149692,28426,58696,14674,7222,3544,886,3184,796,508,454,1492,20518,16078,6388,
3658,17872,4468,18358,4702,2122,13498,82024,20506,19006,7486,3166,1546,7666,4588,6088,
1522,12346,45292,20626,41686,12352,3088,772,1114,2644,7124,5990,2606,5360,1340,818,
1844,1418,27860,7628,1790,2174,3212,962,12122,7718,3254,1580,656,164,1778,17870,
6992,1748,1412,22244,10394,6746,4694,2120,530,2156,764,72464,18116,11150,6008,1502,
1052,1526,932,2102,1148,33232,8308,1918,8392,2098,14518,8686,9040,2260,784,196,
658,66250,25204,5086,9364,2116,928,232,58,382,5476,2206,11362,3826,2920,730,
634,598,1288,322,1036,1192,298,472,118,8902,5908,1468,3856,964,766,5014,
20110,2056,514,21550,19894,103456,25864,6466,2008,502,14224,3556,37282,11116,10876,22972,
17464,4366,6970,2974,8428,32206,22024,5506,3352,838,1372,2290,2272,568,142,4648,
1162,796,11602,7606,6446,3758,2624,656,164,392,98,398,15536,3884,4406,20054,
28316,34904,8726,87122,33032,8258,3458,1658,1868,2504,626,596,716,2018,1118,1532,
1334,11306,3812,1076,2666,1382,2882,1442,902,8552,2138,7652,1796,698,1604,662,
8012,5096,1274,9704,2426,3278,15194,18272,4568,1142,6932,3326,2774,72056,18014,11036,
13106,5276,5744,1436,5236,8956,12520,3130,11800,2950,1468,2728,682,1288,322,1990,
1108,1216,304,76,376,94,5482,3988,2026,2044,52858,26890,16030,8074,5446,2404,
87850,50320,12580,10900,3970,5068,1312,328,82,2644,1648,412,880,220,664,166,
424,106,964,1826,1934,1088,272,68,926,710,7172,2924,1046,1952,488,122,
1262,836,1142,956,542,566,794,3062,1496,374,740,34126,20104,5026,2248,562,
574,8224,2056,514,556,1960,490,4336,1084,1318,11302,269368,67342,38788,7636,9340,
6754,2896,724,4396,3580,3424,856,214,1906,1078,6172,2644,4480,1120,280,70,
3040,760,190,2050,1132,12910,8170,11626,267910,256882,96694,71338,47482,13990,107530,35374,
20806,29284,5854,3514,1624,406,2068,1678,1852,20536,5134,3796,8872,2218,3742,-1671734,
-703946,-2522378,-1195538,-671582,-251480,-62870,-234842,-1683542,-1063028,-669746,-375824,-93956,-13316276,-28428446,-10660304,-2665076,
17564,9140,2078,56012,16664,4166,3254,2420,818,4658,24344,6086,4334,1610,968,242,
2498,1340,19808,4952,1238,4442,2030,4784,1196,6116,4280,1070,3542,5336,1334,2390,
54014,139280,34820,5534,26882,8198,5522,3650,1664,416,104,26,374,1268,602,590,
2228,782,36382,14008,3502,1678,994,1468,640,160,40,10,26608,6652,1612,6166,
6250,7006,2992,748,1480,370,1120,280,70,658,1282,9922,14914,17428,25960,6490,
41872,10468,3856,964,1252,1264,316,424,106,1822,1048,262,712,178,1012,3604,
7222,3916,14296,3574,2830,1426,1714,1876,2524,838,874,2470,3982,1858,10138,41644,
35842,250222,94198,41062,21316,7150,3046,1486,922,18544,4636,1234,1606,1090,4306,3334,
1576,394,2458,22234,47020,17938,11002,16888,4222,1948,730,6196,16402,2480,620,482,
2144,536,134,416,104,26,17372,2678,1370,2810,2570,2360,590,806,668,734,
19820,4082,8138,5492,2210,3602,17858,1724,2900,1730,5132,1328,332,428,446,1514,
1766,1028,1994,2036,18680,4670,3296,824,206,698,1346,10244,4910,3188,58682,25808,
6452,27362,24824,6206,3944,986,2084,10568,2642,4366,20044,24832,6208,1552,388,8134,
5686,4114,1798,18586,7336,1834,1054,2338,2314,1234,988,13114,5284,1384,346,496,
124,1792,448,112,28,9088,2272,568,142,28792,7198,6226,2392,598,1252,7732,
1816,454,1708,1396,628,484,898,2926,19882,7822,68158,59248,14812,9628,33166,173548,
49726,43696,10924,3988,1114,784,196,985472,246368,61592,15398,22472,5618,2474,3590,12458,
12860,6020,1496,374,2060,137648,34412,16262,81278,26876,25388,14930,5966,4274,1970,1106,
782,1358,1682,998,5696,1424,356,434,530,566,2222,2168,542,2294,3680,920,
230,9098,2216,554,8612,1982,1892,722,638,1388,2330,1298,854,2020,3526,1690,
1870,2122,51484,88054,33388,6628,2200,550,574,9202,9358,38572,7600,1900,724,1210,
1600,400,100,2932,1744,436,1042,2626,7744,1936,484,2878,2554,2356,1582,35566,
24874,41326,25396,8062,5596,4138,2470,1294,7486,4012,1120,280,70,394,3056,764,
512,128,32,8,2,3542,2492,836,3704,926,716,746,7136,1784,446,536,
134,3074,5894,2096,524,908,5602,2470,3838,3082,1504,376,94,976,244,1390,
1648,412,2092,4324,1180,3550,2920,730,2962,1480,370,508,1066,946,724,748,
9442,3910,2498,2396,5738,2522,1316,1904,476,8372,1940,734,2378,1262,11288,2822,
5564,4106,1910,2000,500,464,116,392,98,6428,7076,2774,2486,2324,806,2228,
788,518,2876,2972,3398,3188,968,242,716,4766,5780,1454,9524,2156,1532,2174,
2372,3134,23810,13736,3434,1658,992,248,62,4658,1958,3206,8534,5726,6590,32672,
8168,2042,1136,284,2656,664,166,1414,22930,16480,4120,1030,12016,3004,934,1738,
5212,1348,1306,2518,4762,6220,87832,21958,16282,7396,2626,2404,6994,9964,2050,2080,
520,130,1000,250,1972,3844,2008,502,790,1024,256,64,16,4,928,232,
58,1810,3628,1240,310,736,184,46,388,1036,8930,25238,9836,2216,554,3860,
1784,446,776,194,3266,7154,7802,5318,2366,1316,10658,25136,6284,1550,3374,2450,
8234,11150,51542,19700,6470,2798,2528,632,158,1934,12176,3044,3050,21212,5822,2288,
572,920,230,458,1262,1880,470,548,3176,794,1376,344,86,404,1154,11144,
2786,12116,32426,8846,8090,5480,1370,1700,2234,2186,59618,301292,56864,14216,3554,17846,
7064,1766,1034,6830,6146,380,704,176,44,416,104,26,944,236,24934,14956,
3028,940,3490,1570,1192,298,484,83428,65716,12694,15388,8260,1732,5290,2356,814,
3346,14578,47464,11866,4822,4144,1036,1222,1618,2032,508,1780,706,850,1708,2518,
4948,1300,616,154,430,3328,832,208,52,382,3508,1030,1510,11014,7126,18070,
216862,416608,104152,26038,44800,11200,2800,700,42694,24946,27646,38014,51136,12784,3196,8086,
42242,16214,81266,30848,7712,1928,482,554,980,2984,746,1904,476,4868,1286,2858,
1466,4400,1100,5234,2336,584,146,428,8366,21410,8402,3524,1034,944,236,3182,
6368,1592,398,1304,326,2048,512,128,32,8,2,374,3506,1688,422,1970,
1112,278,5450,2186,1268,2804,3290,3734,130298,64016,16004,3374,4118,12740,2762,1430,
17036,8960,2240,560,140,1832,458,782,6584,1646,4910,5090,2282,2390,4774,2164,
1522,4096,1024,256,64,16,4,1678,1126,796,766,994,2614,1354,1696,424,
106,802,2452,1624,406,526,2656,664,166,436,2182,1192,298,1102,964,2506,
2344,586,1264,316,6988,1684,1408,352,88,22,382,1516,658,6178,4072,1018,
1504,376,94,6818,4772,2084,4340,2390,1328,332,3488,872,218,1964,932,1274,
2516,21074,9968,2492,842,219044,47282,48242,24764,5018,6014,2630,2468,1598,974,740,
3440,860,536,134,1436,644,1118,794,2450,1958,5852,1472,368,92,392,98,
992,248,62,398,524,4952,1238,1004,520,130,424,106,2566,9820,3700,1258,
18568,4642,2116,772,1366,4240,1060,574,1648,412,1054,4366,3394,3556,1042,766,
1402,3502,2908,1756,1432,358,934,5698,2512,628,1378,892,6256,1564,4960,1240,
310,2044,1510,1540,664,166,7282,3106,718,1342,1582,1828,2260,1690,1132,3014,
2636,1682,5606,4094,12734,25454,23264,5816,1454,416,104,26,386,7874,3788,2006,
1928,482,794,674,848,212,17156,16622,15812,2882,1478,1772,24398,63872,15968,3992,
998,1502,4958,9332,2126,3062,2344,586,2284,3148,1102,790,1588,4066,39706,53314,
18058,17026,8266,8764,2020,1510,1084,580,3400,850,1420,25450,17824,4456,1114,3730,
3040,760,190,448,112,28,382,520,130,1138,1582,970,2608,652,940,1564,
670,628,13462,13678,5506,3406,1654,3472,868,1186,2752,688,172,1402,7630,3238,
1570,31388,4184,1046,770,2444,836,1988,9734,4028,2042,2852,4874,3686,1760,440,
110,692,1232,308,14918,5972,2624,656,164,4514,4580,5846,2570,2390,1274,14594,
14108,3920,980,1220,3542,1706,1904,476,728,182,446,2714,1916,3038,2366,23048,
5762,6656,1664,416,104,26,61574,23468,4778,3632,908,548,3416,854,698,10058,
6602,4658,48452,17054,8564,762740,1566662,587876,8128556,1524482,1288076,241892,234590,928,232,58,
400,100,676,946,104014,134716,58630,25822,23584,5896,1474,11758,27310,85630,67162,25564,
29254,10450,75910,33112,8278,5602,5980,257348,48632,12158,14942,7394,3152,788,15158,80456,
20114,7922,3350,4628,3074,1532,6572,4574,3020,7868,2750,8138,4808,1202,830,2540,
2534,9812,5546,26606,15914,12512,3128,782,1388,21476,4406,26822,37028,7322,9974,8042,
23986,22042,13348,5956,16372,5554,6490,4600,1150,988,11026,8710,3646,1690,1900,736,
184,46,1396,1342,1042,2392,598,604,1504,376,94,898,4222,1852,1990,1126,
802,12112,3028,4012,1132,592,148,1222,838,694,640,160,40,10,1096,274,
1906,3412,7030,3016,754,2440,610,6166,2692,19126,7552,1888,472,118,424,106,
16000,4000,1000,250,1090,26290,2476,844,538,1252,2332,8110,4798,2014,19286,22364,
4574,2096,524,740,1160,290,71288,17822,7064,1766,4184,1046,4454,1820,722,1358,
890,4220,1172,2108,776,194,3080,770,2510,1322,2924,27934,16666,13102,15856,3964,
2068,958,1492,2122,1264,316,1042,772,526,1318,16126,10024,2506,1372,3976,994,
754,664,166,3148,7108,1714,1024,256,64,16,4,382,1168,292,436,1474,
934,2848,712,178,448,112,28,1102,1552,388,454,2194,1204,1636,688,172,
5476,1408,352,88,22,28762,13516,6016,1504,376,94,1006,2662,3424,856,214,
5434,3982,2776,694,-141826,-117850,-36082,23930,9356,10238,10454,6836,1664,416,104,26,
392,98,5702,112058,42404,6632,1658,1004,1238,1652,692,512,128,32,8,2,
2462,3302,2492,3518,4784,1196,1292,18032,4508,9320,2330,1256,314,500,476,6056,
1514,950,1490,1088,272,68,1400,350,5378,5864,1466,932,800,200,50,1724,
7826,2870,2570,1346,25358,120614,87218,38510,39266,32108,9986,8780,37508,19556,4802,41198,
71666,22712,5678,10292,2312,578,4622,55454,36836,82706,-797926,-298840,-74710,-27634,-64036,-91606,
-33970,-277876,-200938,-112072,-28018,-71842,-72676,-111514,-45946,-201604,-83236,-76900,-67954,-185566,-747100,-104392,
-26098,-110908,-105430,-39154,-154948,-102010,-139720,-34930,-48610,-155272,-38818,-180220,-54562,-381424,-95356,-92938,
-51322,-153490,-142984,-35746,-106834,-132106,-73354,-40306,-482998,-180742,-67396,-82570,-45490,-235948,-43858,-52402,
-472144,-118036,-32242,-97114,-79186,-68626,-93262,-41278,-365386,-204574,-47098,-164182,-61186,-49810,-314680,-78670,
-228856,-57214,-72850,-132292,-40114,-107644,-129730,-87610,-53410,-124030,-56638,-210838,-78682,-66532,-194314,-108346,
-169096,-42274,-229006,-47422,-48658,8086,2944,736,184,46,400,100,3280,820,2164,2206,
1210,2512,628,3754,23008,5752,1438,922,2596,1648,412,460,4726,1882,3406,1660,
694,1930,13450,35074,20686,8140,7942,4738,3622,4756,9562,9886,4090,12718,5152,1288,
322,1138,6034,3646,1750,1162,8830,3694,1768,442,2026,5674,35806,13810,14842,343318,
97228,50224,12556,4036,2092,964,1228,5914,6808,1702,8848,2212,1558,1108,2260,4540,
1234,13990,31756,1324,856,214,730,2434,2326,1390,904,226,1084,586,6160,1540,
7132,1720,430,544,136,34,976,244,3118,1552,388,1066,3178,1486,940,802,
1408,352,88,22,676,3766,2902,21952,5488,1372,640,160,40,10,3568,892,
550,2812,910,724,1012,20740,6790,4252,1180,604,496,124,406,784,196,3026,
4376,1094,794,1406,1184,296,74,3512,878,2768,692,1154,13628,2588,4208,1052,
2774,1424,356,12656,3164,20324,6176,1544,386,9074,11522,61562,35588,58646,22376,5594,
4106,32078,14924,3182,4484,2966,1496,374,524,482,3728,932,2216,554,12962,15026,
23612,3992,998,758,668,1532,7886,4718,5456,1364,1454,8588,1994,13718,5528,1382,
902,722,2432,608,152,38,398,9254,3854,6914,83594,54938,31862,12332,2696,674,
3362,16484,16634,10316,2318,26084,10004,5204,2404,1900,4348,14176,3544,886,2602,1360,
340,448,112,28,1762,1168,292,2566,28756,5776,1444,4780,1780,718,33130,12808,
3202,1564,2248,562,1630,3076,1294,2572,1684,700,3058,4462,5590,6136,1534,12940,
4600,1150,11260,55000,13750,16498,167104,41776,10444,3898,1846,8182,9082,3790,21472,5368,
1342,171730,8350,13690,5518,4318,130816,32704,8176,2044,66238,6238,12106,4924,92908,31438,
127474,63028,12202,4960,1240,310,7894,5950,31672,7918,8506,3574,14014,16444,13528,3382,
17830,10990,11098,4546,17956,18928,4732,12772,8722,9892,7612,14662,9208,2302,25930,10108,
8342,13688,3422,2888,722,656,164,416,104,26,4130,1934,44954,70550,92420,17714,
7028,4202,1856,464,116,13310,8450,3554,1718,8768,2192,548,488,122,1448,362,
776,194,458,2774,5366,61424,15356,5282,2366,2294,17030,34208,8552,2138,3260,1880,
470,11290,5872,1468,1708,706,2428,8080,2020,87802,65488,16372,11230,6136,1534,3454,
191734,72286,31894,12346,9862,4084,5398,2410,2320,580,4678,2140,976,244,7432,1858,
3400,850,4210,23470,7276,1750,1042,5974,2626,4048,1012,3940,7006,4354,5506,6478,
6046,197134,32242,2330,2816,704,176,44,5828,2606,1364,4274,10310,9014,3212,3506,
1682,2726,2552,638,626,1376,344,86,3020,1916,746,227768,56942,21740,3734,2768,
692,3362,2858,10526,4334,2012,764,530,2390,12902,13388,4226,3344,836,1202,24682,
18112,4528,1132,1792,448,112,28,976,244,712,178,454,3178,4504,1126,11254,
13720,3430,21010,8266,29236,8554,7906,3352,838,6214,31018,173092,32842,74254,42736,10684,
4756,3676,2002,1138,814,1426,922,1090,796,1192,298,99742,43192,10798,7042,3028,
7690,4648,1162,1894,10468,2350,2290,1246,2812,10606,6934,5000,1250,3584,896,224,
56,14,1856,464,116,410,542,1382,1748,716,1172,608,152,38,992,248,
62,2498,151786,129916,24748,29314,31312,7828,16192,4048,1012,3238,1582,982,3124,8092,
1906,2044,772,19756,10528,2632,658,1342,892,556,87796,8992,2248,562,1288,322,
8902,3184,796,538,6148,15382,28504,7126,7012,2944,736,184,46,406,4528,1132,
1648,412,466,1234,1666,5068,5716,4258,2914,70298,46556,7220,3656,914,5546,4094,
3140,3176,794,7328,1832,458,1232,308,2168,542,2852,5096,1274,1658,1820,938,
1502,4574,8090,7190,3086,1550,1118,9920,2480,620,506,1334,890,1496,374,530,
6146,7058,14294,5750,2546,8162,8738,9224,2306,5246,3626,3014,1520,380,2654,18668,
3890,20308,4198,2560,640,160,40,10,394,538,592,148,418,7198,23236,6316,
2752,688,172,1024,256,64,16,4,597676,169072,42268,45268,8878,59848,14962,6478,
68422,232864,58216,14554,5848,1462,1798,4588,2266,1240,310,1150,2824,706,13408,3352,
838,29446,49138,976,244,436,472,118,1042,1256,314,3014,493844,158774,135824,33956,
6758,11732,13838,8762,2456,614,3956,1322,1976,494,5414,14774,14324,4292,1196,5846,
8618,5054,2834,1454,1796,728,182,2012,1544,386,536,134,33652,10444,2350,8626,
7246,6016,1504,376,94,712,178,1900,748,532,3766,1804,730,1390,5494,2452,
6682,4738,39028,11956,4342,2020,3142,1570,5170,4186,3334,1642,1756,5008,1252,2846,
1460,3002,87788,18356,11498,9068,10532,3944,986,3722,5006,2270,1244,626,1334,8570,
25112,6278,9392,2348,1832,458,2252,1004,80498,46262,48098,49178,65432,16358,5288,1322,
6896,1724,716,788,2198,2156,9712,2428,1666,1018,3070,2710,5362,2404,844,2224,
556,146836,16396,6982,1816,454,7090,3052,15508,2302,2278,3790,11080,2770,1432,358,
2170,2878,2602,1420,7768,1942,3868,730,13102,6658,2890,2692,898,31606,65188,12616,
3154,1576,394,1882,4876,2896,724,790,16966,11482,205642,50806,101638,66112,16528,4132,
1168,292,448,112,28,2098,1180,31654,28576,7144,1786,4552,1138,820,6796,6310,
7192,1798,2932,2044,1558,4492,8218,7732,4978,2260,1006,7354,4528,1132,9784,2446,
2734,2284,998,2726,264932,37946,14624,3656,914,2864,716,35774,18722,22868,4682,2150,
52064,13016,3254,2816,704,176,44,7154,2702,8030,8648,2162,1298,3134,3782,5354,
2402,4058,1916,2198,2222,29864,7466,3194,1592,398,5156,6946,4894,2230,1318,5056,
1264,316,454,5908,2416,604,508,490,6136,1534,970,19030,4090,5326,2392,598,
1174,3598,1744,436,52792,13198,5344,1336,334,520,130,1060,6460,1606,778,4192,
1048,262,9916,2254,1240,310,2572,2578,9376,2344,586,5494,2236,814,700,526,
592,148,4738,3652,2014,1150,826,5542,3118,1564,688,172,5974,14666,9230,13652,
6422,2804,1778,3380,1940,1556,1466,1814,1076,1292,638,872,218,1112,278,500,
1130,4622,30920,7730,8402,57164,11114,10970,7160,1790,1196,620,512,128,32,8,
2,3218,3842,8078,14360,3590,1742,3650,6272,1568,392,98,7070,6404,7268,4946,
4904,1226,3560,890,1490,11156,3014,1526,968,242,2084,1756,12082,21964,7168,1792,
448,112,28,1894,2056,514,838,1462,1702,1948,2704,676,54976,13744,3436,1864,
466,1612,1444,4648,1162,832,208,52,406,2362,1282,1054,11236,6106,2686,6724,
13946,20648,5162,5510,6536,1634,1010,776,194,470,9572,2192,548,500,8984,2246,
3782,5078,17732,3722,1742,5612,36290,14006,20954,10280,2570,1418,1094,2810,10748,4016,
1004,16742,30350,23032,5758,4708,5056,1264,316,87778,75952,18988,3958,1882,3304,826,
1492,1414,928,232,58,1168,292,13420,2914,4348,1834,2026,2134,1198,16912,4228,
4024,1006,1132,610,2404,9910,4114,41500,6532,6220,1564,916,1252,36586,21574,8488,
2122,2188,808,202,1108,1306,3400,850,5542,2476,862,3106,4510,57158,19568,4892,
1316,1424,356,2072,518,1664,416,104,26,1916,758,1082,2504,626,28394,39176,
9794,6506,11474,8306,20486,10088,2522,4022,7562,132398,50048,12512,3128,782,692,2186,
22166,6932,83024,20756,9206,2864,716,9638,8666,2828,2042,5066,14876,3188,5552,1388,
4016,1004,1028,1286,1988,1556,10502,5876,59588,17756,3728,932,1406,926,746,4184,
1046,992,248,62,422,2834,2342,4934,3044,8174,3464,866,1484,26936,6734,2924,
5804,1514,5156,2234,4634,648242,412334,155024,38756,26162,18674,21302,8522,99602,43166,16586,
36746,8638,4792,1198,1672,418,556,4426,10960,2740,1084,2464,616,154,742,5704,
1426,934,8800,2200,550,3940,1138,826,3820,3508,1192,298,3436,3346,1654,3292,
1924,760,190,1228,4840,1210,6088,1522,970,3184,796,1222,4408,1102,1618,1006,
1564,1438,11068,7324,3058,1546,5722,2308,832,208,52,706,664,166,3454,2164};
unsigned char cflag[3920+1]={
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,3,3,3,3,4,4,4,5,5,5,6,6,6,6,6,7,7,
7,7,8,8,8,9,9,10,10,10,10,11,11,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,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,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,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,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,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,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,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,5,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,6,6,6,6,6,6,6,6,6,7,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,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,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,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,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,0,0,0,0,0,0,
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,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,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,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,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,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,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,
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,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,1,1,1,1,1,1,1,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,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,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,1,1,1,1,1,1,1,1,1,1,1,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,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,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,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,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,2,2,2,2,2,
2,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,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,3,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,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,3,3,3,3,3,0,0,0,0,0,0,0,0,0,1,1,
1,1,2,2,2,2,2,2,3,3,3,3,3,4,4,4,4,5,5,5,5,
5,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,2,2,2,2,2,3,3,3,3,4,4,4,4,4,5,
5,5,5,6,6,6,6,7,7,7,7,7,8,8,8,8,8,9,9,9,9,
10,10,10,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,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,3,3,3,3,3,3,3,3,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,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,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,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,2,2,2,2,3,3,3,3,4,4,4,4,4,5,5,
6,6,7,7,7,8,8,8,8,9,9,9,10,10,10,11,12,12,13,13,14,
14,15,15,16,16,16,17,17,17,17,18,18,18,19,19,20,20,20,21,21,21,
22,22,23,23,24,24,24,24,25,25,25,26,26,27,27,28,29,29,30,30,31,
31,32,32,33,33,34,34,34,35,35,36,36,37,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,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,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,7,7,7,7,7,7,7,
7,7,7,7,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,
1,1,1,2,2,2,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,
5,5,5,5,5,5,5,5,5,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,8,8,8,8,8,8,8,8,
8,8,9,9,9,9,10,10,10,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,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,
3,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,7,7,7,7,7,
7,7,7,7,7,8,8,8,8,8,9,9,9,10,10,10,10,11,11,11,12,
12,13,13,14,14,14,14,14,0,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,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,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,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,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,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,1,1,1,1,1,1,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,1,
1,1,1,1,1,1,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,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,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,0,0,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,0,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,1,
1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,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,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,
6,7,7,7,7,7,7,8,8,8,8,8,8,8,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,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,2,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,4,4,4,4,4,4,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,1,1,
1,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,1,1,1,1,1,1,1,1,1,1,1,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,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,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,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,
2,2,2,2,2,3,3,3,3,3,3,3,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,5,5,5,
5,5,6,6,6,6,6,6,6,6,6,6,6,6,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,4,
4,4,4,4,4,4,4,4,4,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,255}; //  index=3920 
unsigned int size[66]={
  55,
  62,
  48,
  29,
  51,
  127,
  37,
  96,
  68,
  36,
  15,
  42,
  43,
  79,
  64,
  47,
  24,
  85,
  50,
  91,
  60,
  62,
  54,
  49,
  24,
  28,
  66,
  54,
  84,
  66,
  78,
  53,
  53,
  55,
  39,
  59,
  76,
  26,
  41,
  78,
  29,
  73,
  177,
  138,
  89,
  104,
  49,
  50,
  44,
  60,
  23,
  55,
  56,
  56,
  35,
  35,
  39,
  92,
  41,
  66,
  62,
  37,
  35,
  58,
  100,
  63};
int cval[66]={
1403,1405,1409,1411,1415,1417,1421,1423,1427,1429,1433,
1435,1439,1441,1445,1447,1451,1453,1457,1459,1463,1465,
1469,1471,1475,1477,1481,1483,1487,1489,1493,1495,1499,
1501,1505,1507,1511,1513,1517,1519,1523,1525,1529,1531,
1535,1537,1541,1543,1547,1549,1553,1555,1559,1561,1565,
1567,1571,1573,1577,1579,1583,1585,1589,1591,1595,1597};
unsigned int numbc=66;