// c=1201 
int sinp[3740]={
1534,3586,4462,10186,4120,1030,1330,3418,1582,9808,2452,760,190,2680,670,28924,
36430,32164,4954,2158,16288,4072,1018,682,556,11644,4282,1906,2896,724,436,382,
8242,59098,22462,30868,6088,1522,3652,9418,3832,958,6226,4930,1912,478,6016,1504,
376,94,4138,1852,55654,32056,8014,8188,14560,3640,910,2194,2014,1402,826,610,
7474,10294,5206,11752,2938,6082,2236,6610,3208,802,6388,1498,862,5596,35662,31516,
14722,4666,2050,1102,2356,742,1168,292,1150,59866,22750,5044,1246,7684,1606,1654,
2734,3100,2446,3490,1714,7540,3868,3058,2290,3382,5434,2338,1750,4354,2038,2770,
4516,2524,2722,3172,1390,5812,3748,2614,1966,4082,1832,458,656,164,332,5072,
1268,3812,1016,254,896,224,56,14,872,218,1184,296,74,548,404,584,
146,356,368,92,8324,1862,3002,1088,272,68,314,2138,1994,50792,12698,5138,
2228,1562,6026,2222,1736,434,464,116,1976,494,12514,11992,2998,1426,5824,1456,
364,370,2920,730,4918,2146,3244,910,784,196,1516,586,1084,3730,87970,75658,
43312,10828,2332,856,214,382,1234,6322,3430,1588,3460,25678,7750,3208,802,2110,
1984,496,124,1120,280,70,328,82,2854,1372,2650,3280,820,9778,11422,21388,
4312,1078,706,7132,1450,1570,2758,1336,334,622,2416,604,1444,5350,2308,1882,
2794,2326,1174,742,580,1678,1000,250,12502,4990,7834,1580,752,188,338,5024,
1256,314,3566,1640,410,1784,446,470,662,716,9556,5326,3754,5968,1492,1414,
15796,2752,688,172,1438,2194,1126,3220,6454,6886,15532,6298,2302,5650,2422,3484,
1738,3052,2728,682,55162,5582,6068,1442,938,656,164,3320,830,5588,1352,338,
10610,3098,1466,854,2150,1970,1934,2612,794,602,530,2294,3068,12788,2702,1024,
256,64,16,4,4696,1174,1600,400,100,790,1438,844,652,2410,4678,2842,
7594,6196,42766,16342,6304,1576,394,1780,13606,4360,1090,1336,334,430,466,10024,
2506,3562,8962,9214,3760,940,1282,2356,3280,820,2218,2794,18466,35296,8824,2206,
1132,2320,580,6082,3442,2698,3724,1768,442,4858,15430,6244,2518,1930,3076,-4070,
31832,7958,3290,2006,1058,8420,5954,6476,1520,380,10328,2582,1274,27698,109472,27368,
6842,37988,30374,11696,2924,854,626,48596,14432,3608,902,644,1724,1472,368,92,
548,11336,2834,3950,1646,998,680,170,860,656,164,2588,980,1040,260,1562,
1538,2750,10472,2618,6776,1694,4910,1916,7748,7370,2386,20164,10216,2554,1264,316,
1588,604,4612,2638,4654,12874,5134,8986,3676,7528,1882,1012,496,124,2152,538,
508,1558,1642,922,652,1018,688,172,814,5584,1396,568,142,2668,1516,1192,
298,418,2236,2398,3478,2722,3694,50014,43654,17392,4348,3988,1054,2344,586,526,
3154,3856,964,2278,125966,71624,17906,7022,4718,3422,3386,1490,866,632,158,950,
9050,6662,10928,2732,2612,986,5162,8174,5366,80492,26870,63578,3862,1756,1486,4690,
4372,1474,4366,4744,1186,6310,2674,3718,1702,946,2260,2350,1888,472,118,352,
88,22,316,2068,3076,3040,760,190,592,148,916,1078,712,178,1612,610,
33292,6550,2764,826,1234,6562,16516,12952,3238,1522,2746,2314,2698,7120,1780,1270,
784,196,12148,4186,3124,1648,412,2914,22348,4498,12394,9478,4906,13978,8632,2158,
2026,3346,5590,2404,2476,772,4132,17494,6868,3808,952,238,1216,304,76,322,
2908,8506,5554,6148,6508,1528,382,646,550,514,8378,13112,3278,1538,17072,4268,
3338,5498,4556,10682,16028,3314,2636,992,248,62,332,1718,1844,5822,2492,776,
194,1532,596,3824,956,488,122,2306,4958,2168,542,512,128,32,8,2,
2708,3494,632,158,368,92,326,47072,11768,2942,1412,1874,1826,1658,3764,17972,
43406,16586,42272,10568,2642,2258,2042,20828,4214,3332,42866,24884,27692,20312,5078,5276,
1298,1502,872,218,3244,84856,21214,12706,5074,2212,724,2554,6208,1552,388,382,
988,11248,2812,1564,3526,4444,2596,796,1102,1354,922,1510,9610,16214,9896,2474,
1238,1472,368,92,3068,2768,692,440,110,2660,998,4892,3590,3920,980,494,
3146,1490,962,2606,7322,3056,764,1796,6548,1538,4766,16430,20564,4166,16448,4112,
1028,3794,1610,914,800,200,50,728,182,878,3632,908,8006,10382,1256,314,
428,896,224,56,14,4118,3092,890,644,1646,4604,3416,854,5864,1466,860,
3326,4280,1070,12182,7628,2186,1130,734,1880,470,1040,260,8492,3164,-89194,-49396,
-58144,-14536,-3634,7034,2948,2930,4796,2510,16070,20834,9914,4028,2690,55436,22130,9980,
5684,1376,344,86,824,206,-9850,-27958,-10174,460,2146,1984,496,124,334,436,
1660,622,544,136,34,796,5240,1310,914,2252,734,752,188,572,626,3872,
968,242,2318,2108,842,3242,2264,566,524,410,1010,3404,950,668,17642,6566,
2774,1352,338,1766,974,8894,3326,3980,1058,7124,6086,2594,5816,1454,2192,548,
1712,428,392,98,16520,4130,7760,1940,2270,1184,296,74,3296,824,206,8732,
2972,2756,2656,664,166,874,640,160,40,10,316,2086,1954,1096,274,24418,
7414,9838,9784,2446,6148,2368,592,148,340,376,94,12292,3340,1720,430,1846,
4474,1990,1900,2260,736,184,46,1522,1774,2980,13940,4076,8000,2000,500,1244,
4430,19772,6344,1586,908,2888,722,584,146,368,92,920,230,1682,944,236,
6992,1748,794,3026,1448,362,650,8318,5462,9458,3860,2810,2054,2360,590,12860,
4400,1100,1952,488,122,22102,8602,3712,928,232,58,4012,1066,1384,346,1048,
262,412,2788,6784,1696,424,106,844,472,118,358,448,112,28,4234,3166,
56150,12572,2672,668,440,110,356,980,5192,1298,3356,944,236,584,146,9158,
9350,6272,1568,392,98,842,3032,758,764,458,4316,1124,1142,872,218,1574,
2276,4640,1160,290,950,818,1250,1490,14990,5936,1484,1454,860,476,404,6242,
4298,3650,2840,710,4028,1070,716,1292,5108,53680,13420,8842,3970,1804,4954,1774,
1786,1054,2308,748,4324,1126,7870,9940,6520,1630,1594,1000,250,622,1138,742,
5566,52438,45742,26518,23872,5968,1492,3352,838,3622,99724,65668,12628,4834,2128,532,
2200,550,28894,13096,3274,2524,1498,10300,4252,1984,496,124,1714,958,2026,7858,
3262,26788,5338,7834,16012,12694,12208,3052,2404,766,7168,1792,448,112,28,796,
1012,694,1840,460,4594,2038,2728,682,1936,484,406,976,244,586,1390,1570,
904,226,400,100,334,6106,1828,658,562,526,1084,1864,466,490,6052,1450,
9598,11938,4792,1198,1462,192430,109030,211144,52786,20110,12100,2584,646,453982,32296,8074,
34114,13108,16582,23548,15878,9722,3962,1802,992,248,62,2648,662,3152,788,464,
116,338,2234,1154,878,3314,3416,854,44402,30134,13622,6656,1664,416,104,26,
326,974,2324,752,188,3578,1658,938,668,1784,446,3134,6536,1634,1076,518,
1082,722,5288,1322,812,21602,4124,3242,1532,4772,4712,1178,758,1238,9014,7952,
1988,1022,6332,5414,3836,4064,1016,254,1244,18956,6122,2612,806,13988,2858,1388,
1202,8102,5348,3728,932,11152,2788,1576,394,1654,1846,1762,3274,11476,6346,10720,
2680,670,568,142,370,1000,250,2890,1978,10072,2518,19504,4876,1240,310,1276,
556,6130,4240,1060,1090,1384,346,4834,2950,2710,3754,4672,1168,292,874,2242,
6382,4384,1096,274,946,1324,2458,13582,5410,3250,2620,808,202,3436,1702,1954,
1618,1294,802,5212,2734,1342,820,7750,2944,736,184,46,334,442,10504,2626,
23626,16396,2860,3058,2512,628,4888,1222,898,1348,5644,1510,9314,9368,2342,1196,
542,22328,5582,2126,1154,2180,2540,794,4610,61694,20702,15146,3320,830,1502,2996,
2636,812,470,494,1028,4292,938,1322,1538,2396,1568,392,98,1592,398,668,
650,1160,290,1754,2798,4580,5480,1370,2234,1856,464,116,1012,508,1726,2968,
742,1228,1174,1456,364,898,1840,460,7720,1930,1042,850,796,30550,17980,5674,
2446,16072,4018,6856,1714,4954,2176,544,136,34,1168,292,598,1132,1114,736,
184,46,2644,814,3616,904,226,8962,15548,95954,36302,21218,8276,4064,1016,254,
1088,272,68,332,2804,1034,2060,19994,6182,10418,4226,1904,476,932,494,1076,
710,5558,6206,3536,884,1688,422,3128,782,1238,2240,560,140,5684,1358,1562,
998,3212,13766,30344,7586,3164,658,2074,1966,8230,3406,2596,2614,1300,2110,35500,
6976,1744,436,922,1318,814,4180,4558,3082,20890,12550,5026,4972,1252,1522,2422,
1228,550,526,8554,4528,1132,532,1720,430,4852,2164,1408,352,88,22,328,
82,1588,1246,910,3568,892,1570,9256,2314,2692,6772,2704,676,1804,4396,1144,
286,640,160,40,10,54626,36272,9068,4934,11630,4682,5474,5168,1292,878,650,
2072,518,1040,260,7418,3062,15032,3758,1730,1652,5798,2192,548,956,500,37874,
22106,30584,7646,3188,7256,1814,1928,482,13970,8660,6626,7436,1526,17948,3686,1598,
920,230,626,1154,1904,476,410,1414,3862,7498,3808,952,238,1024,256,64,
16,4,322,442,5446,4912,1228,2044,1378,838,1996,2368,592,148,3988,8362,
2914,3656,914,938,674,2198,2042,1088,272,68,2096,524,1100,2060,3170,8054,
5336,1334,1556,614,6470,32020,60550,311002,2156074,4097428,2595526,1233742,462976,115744,28936,7234,
4876,8482,5578,9682,56974,21688,5422,2356,2218,8314,8548,21814,6700,5290,8608,2152,
538,11140,3940,1642,8860,1984,496,124,346,2860,1048,262,3688,922,2056,514,
1096,274,1888,472,118,598,2770,5524,6118,3136,784,196,862,646,13082,8168,
2042,1958,1058,6278,2678,1328,332,386,4982,2192,548,3716,5792,1448,362,3002,
2498,8492,1916,836,8252,1538,14216,3554,87926,33296,8324,7898,5252,5954,10166,4136,
1034,14072,3518,1556,1268,1166,2822,1382,842,1286,806,626,2066,1742,6308,17456,
4364,1142,752,188,12542,4094,1718,968,242,7052,1646,1868,674,-1211152,-302788,-31186,
-343642,-128542,-91768,-22942,-162202,-60502,-54526,2258,2906,2444,782,-32062,-37948,-376996,-58438,3754,
1732,2386,2182,2038,1792,448,112,28,1552,388,622,1540,784,196,1480,370,
6034,940,2020,4414,6490,2758,2362,1210,778,616,154,382,3118,16564,3430,2740,
838,1282,928,232,58,346,454,1066,724,460,3196,4396,7816,1954,1162,760,
190,3358,27742,85738,32476,16600,4150,165496,41374,82822,47398,27472,6868,1612,1264,316,
4576,1144,286,6232,1558,5746,14782,64552,16138,6376,1594,922,670,5548,3478,1568,
392,98,362,1346,830,1280,320,80,20,572,974,626,560,140,1604,650,
752,188,866,1184,296,74,590,1352,338,452,410,2048,512,128,32,8,
2,326,1820,1508,608,152,38,446,1064,266,644,788,680,170,133606,50428,
11818,7462,3124,2932,1492,1234,9430,3862,1774,2842,4222,2962,9550,3256,814,2746,
26686,11674,9118,6226,18700,3832,958,2446,1258,1522,3922,17938,38350,11356,37406,14354,
44174,16892,3494,28376,7094,2252,2816,704,176,44,578,1142,4808,1202,6434,4436,
5462,2108,722,1244,560,140,1214,782,620,11204,3968,992,248,62,350,458,
21980,4448,1112,278,650,4484,2078,1106,1406,854,812,686,584,146,1784,446,
494,512,128,32,8,2,818,3806,1754,3032,758,1700,1298,1442,1628,632,
158,386,1034,6272,1568,392,98,872,218,1736,434,15254,4862,2150,3464,866,
1304,326,1322,4328,1082,3590,2090,5300,3788,3302,5534,2402,2168,542,530,1226,
64106,142946,81224,20306,9506,6164,10160,2540,1862,1970,11618,7352,1838,1016,254,422,
22310,75770,9916,4876,8944,2236,2446,2194,1150,1426,862,2284,2518,2848,712,178,
394,2356,904,226,412,934,3208,802,628,1744,436,634,2344,586,10060,7096,
1774,1816,454,28870,133846,129616,32404,56668,16756,2524,1528,382,1102,1438,4300,5380,
1336,334,1006,1384,346,670,11698,4714,4390,3814,7486,23182,13858,5524,3334,10168,
2542,2248,562,538,724,968,242,1292,1184,296,74,356,1286,1544,386,1520,
380,11372,5342,9428,2096,524,1918,1048,262,1552,388,1432,358,676,1012,5296,
1324,1504,376,94,364,3676,1018,6268,3998,2882,1922,3188,8492,7238,3044,131168,
32792,8198,3404,968,242,4808,1202,5576,1394,3026,6440,1610,1730,4502,2018,6266,
7256,1814,1010,4970,3620,10910,5798,2504,626,1046,722,11774,14690,38018,33644,6638,
2444,788,8330,5510,2396,914,3836,9950,5960,1490,10334,4496,1124,12854,5150,3368,
842,1298,4322,4118,1874,6536,1634,4484,3458,5294,2066,2498,3674,2594,3146,1946,
8876,1994,5942,2558,3530,2810,10640,2660,55352,13838,5852,1400,350,2450,5780,7724,
1778,4106,3134,5078,2234,6428,4430,2210,4916,3098,2426,2714,2750,3422,5564,7400,
1850,3038,3236,3854,3908,3470,3524,3956,4340,4604,4988,8696,2174,13480,3370,1594,
928,232,58,352,88,22,838,14284,6274,3844,2008,502,1108,538,532,430,
28864,7216,1804,1330,952,238,176986,66700,17722,6976,1744,436,412,2944,736,184,
46,6994,4426,1990,1672,418,3916,6046,6670,8674,2512,628,448,112,28,2356,
772,1360,340,394,478,1972,700,1864,466,862,2296,574,1870,5050,2224,556,
982,1378,2998,7226,2612,7964,3068,9044,4994,2204,1448,362,13124,2792,698,776,
194,404,1286,17198,10502,14438,31778,12248,3062,2918,9908,2432,608,152,38,6992,
1748,19304,4826,1784,446,2042,1154,764,12824,3206,4376,1094,4076,3388,4360,1090,
610,7054,7708,11122,10960,2740,1600,400,100,1618,4138,5758,2200,550,538,1132,
544,136,34,108052,23746,37672,9418,3352,838,646,574,742,3334,1582,1870,2050,
5290,5110,2248,562,5128,1282,4318,1678,5182,2038,1096,274,2626,4846,2536,634,
1186,12136,3034,2056,514,3346,3832,958,850,39796,12022,4840,1210,1510,898,1894,
1042,3274,5048,1262,806,1742,986,6260,8330,19328,4832,1208,302,446,500,3020,
1088,272,68,11138,8816,2204,746,2210,23756,3298,1570,922,10102,9298,3820,3466,
1558,11362,4594,2056,514,526,1180,20110,9442,3874,1786,53644,24214,73288,18322,7204,
1684,820,1360,340,2260,1090,742,1990,3262,2668,4396,2182,3424,856,214,3934,
3046,3448,862,1318,3232,808,202,640,160,40,10,586,748,3892,2920,730,
1516,22378,8470,18046,10984,2746,19138,7510,18652,7672,1918,1912,478,1102,2434,1246,
1534,1696,424,106,928,232,58,74134,737446,1503580,716602,455620,85762,32494,261514,24022,
57082,721228,1478434,554746,1344028,284464,71116,3278,50954,19442,4874,2162,1256,314,452,2306,
4898,2522,1280,320,80,20,338,680,170,398,28856,7214,11846,9272,2318,16076,
4352,1088,272,68,1226,794,632,158,8138,3386,1604,1550,11360,2840,710,3818,
1766,1706,974,1936,484,3232,808,202,4798,2134,1186,1504,376,94,370,16300,
2878,1414,1810,1726,982,862,658,1240,310,1594,2536,634,5176,1294,820,11116,
12574,5050,14686,5842,4426,15256,3814,1178,1502,1010,1964,704,176,44,344,86,
368,92,5768,1442,9278,4436,2978,29096,7274,4034,12086,4868,48536,12134,4886,2168,
542,740,1766,998,710,602,1664,416,104,26,854,656,164,20348,11546,7334,
3086,8360,2090,3710,10142,3440,860,3986,4958,1982,9394,5182,14272,3568,892,1618,
36142,32092,15136,3784,946,28852,5746,5134,26638,32632,8158,6286,5512,1378,976,244,
382,6106,2626,3676,3148,1726,33712,8428,7468,2542,3742,5668,3958,4156,5362,10858,
4408,1102,11356,6388,1534,14854,9196,4696,1174,1462,13516,4642,1894,1906,6478,8422,
5578,2428,5506,3022,2002,20104,5026,15434,48902,49064,12266,4040,1010,716,1904,476,
1070,10556,3812,1052,3524,998,2444,2312,578,554,746,800,200,50,356,404,
14918,9356,9194,3176,794,8306,3452,1814,5036,21236,5702,23990,332114,124880,31220,7808,
1952,488,122,1274,1760,440,110,1016,254,986,15746,6242,2678,17054,10436,2294,
10076,4244,2618,2240,560,140,2624,656,164,368,92,1880,470,4148,6848,1712,
428,29822,17618,6944,1736,434,500,1328,332,1742,2894,5120,1280,320,80,20,
782,5962,4198,1912,478,1426,6250,4360,1090,2524,946,26662,10336,2584,646,580,
3370,2740,2278,1192,298,1012,5602,5086,2440,610,1594,9622,3946,3064,766,2332,
1108,1156,2092,730,9850,13024,3256,814,820,1144,286,3874,6166,2650,8032,2008,
502,526,892,8194,8518,3532,1000,250,5828,2486,1292,3506,56792,14198,4586,890552,
222638,83828,36974,14204,3002,4142,1892,3926,2756,1622,11216,2804,2792,698,2198,1274,
2684,842,3818,17912,4478,2018,1982,1082,2522,3434,87896,21974,45614,17444,902,4466,
2858,27794,19388,3974,7382,7724,1598,938,6248,1562,2534,2912,728,182,644,1028,
1136,284,392,98,1234,802,640,160,40,10,9892,2194,1162,1720,430,1090,
748,3016,754,622,1198,1522,910,1360,340,6004,1438,1582,1738,4924,2014,1708,
2332,1504,376,94,1990,8224,2056,514,532,1342,6814,3850,2854,520,130,388,
412,964,13672,3418,10378,5608,1402,988,1126,15724,22906,7036,6382,4438,5356,16594,
6562,2800,700,18640,4660,1276,2206,1906,1054,1420,4960,1240,310,1744,436,1528,
382,2044,2176,544,136,34,352,88,22,1630,12646,146944,36736,9184,2296,574,
8920,2230,3472,868,502,1792,448,112,28,856,214,928,232,58,610,568,
142,836,4130,1658,962,866,3032,758,1298,1676,1322,1052,2060,1430,11996,5348,
6164,1496,374,1136,284,1736,434,1982,8864,2216,554,548,1352,338,1376,344,
86,1862,1898,25198,9790,4012,2938,5206,5488,1372,598,2572,958,700,472,118,
4516,2122,3856,964,1228,4792,1198,790,13858,6826,7378,5002,4720,1180,562,1168,
292,934,1960,490,2032,508,436,7702,10942,4444,1174,7744,1936,484,988,526,
538,25414,3094,6568,1642,3004,904,226,17906,46742,17870,5624,1406,1832,458,1112,
278,446,1412,2006,1094,752,188,3140,2948,2492,58040,14510,3230,4244,2048,512,
128,32,8,2,6890,4730,2978,4136,1034,1436,800,200,50,2840,710,608,
152,38,356,3002,13046,5234,180026,2384,596,1022,1670,968,242,2654,12020,3518,
4864,1216,304,76,1000,250,436,424,106,382,1948,9886,14176,3544,886,1354,
850,838,2422,2218,1174,1516,1282,2342,4658,2090,2126,2054,8426,5036,4046,3134,
5132,9398,9560,2390,4064,1016,254,1094,15716,3290,1526,2918,6482,2774,19604,12962,
5204,2842,2458,2242,13528,3382,1612,646,586,12556,2698,5644,1402,1648,412,1942,
1072,268,394,13588,9532,1126,766,6328,1582,3214,2602,2086,34550,14150,3782,4238,
1934,1070,746,9578,7634,5156,2312,578,1298,1592,398,494,530,1160,290,1856,
464,116,10118,4742,7640,1910,3428,1826,3770,17900,1784,446,512,128,32,8,
2,992,248,62,368,92,362,1802,3158,2582,11338,3190,8302,5920,1480,370,
484,436,3886,2632,658,592,148,814,1336,334,20086,64528,16132,3370,1552,388,
418,502,5506,2410,1282,826,1600,400,100,364,46120,11530,8404,1786,1732,670,
1240,310,28834,11158,19906,7810,3274,1462,9458,3266,8096,2024,506,536,134,1052,
46574,92984,23246,32234,12434,23918,37826,13256,3314,1538,1904,476,5018,2228,764,4964,
1304,326,1196,1202,944,236,932,1754,1004,1148,41954,28778,11138,5954,14498,232592,
58148,16466,4274,1808,452,2372,6754,4666,5584,1396,2236,766,634,2182,7744,1936,
484,8500,324076,46180,10738,4492,7552,1888,472,118,640,160,40,10,2830,1408,
352,88,22,5782,4108,3532,2002,8362,31018,18580,11278,4576,1144,286,454,4126,
1894,2056,514,1156,1192,298,21970,50132,26912,6728,1682,2336,584,146,17102,12020,
4250,3260,1148,770,3800,950,704,176,44,356,1802,1760,440,110,1328,332,
410,1100,554,2198,1172,1310,8078,17408,4352,1088,272,68,10562,43814,16778,9002,
7544,1886,1202,2666,8822,3656,914,6824,1706,2984,746,3218,1180,2152,538,550,
604,1780,682,2026,1108,556,1744,436,430,1828,1648,412,1240,310,1132,712,
178,3880,970,2512,628,466,1402,874,676,718,2260,772,2752,688,172,934,
1396,610,880,220,2836,1378,1096,274,3394,1564,2314,1216,304,76,892,1888,
472,118,1258,820,502,1934,1820,1388,3716,1046,15704,3926,33362,12860,4490,1874,
1052,1226,956,1142,16262,15380,2774,9872,2468,812,8414,5606,4814,10520,2630,3878,
9980,3680,920,230,17162,5438,3932,6068,2546,1304,326,584,146,404,668,1208,
302,11492,2504,626,5254,2320,580,1906,6064,1516,634,1042,11500,2506,2284,778,
1312,328,82,4768,1192,298,3796,1942,1078,754,2014,3526,1672,418,670,3622,
1708,2968,742,628,1138,4282,2812,3310,1480,370,2662,1348,2230,1186,6316,1534,
1786,2752,688,172,382,2482,6208,1552,388,4012,1102,922,2758,1384,346,4750,
1948,886,682,1258,1582,6712,1678,1084,3292,1156,2716,994,2500,2428,1780,1912,
478,2554,5236,2110,2158,1264,316,1006,1750,2164,1462,898};
unsigned char cflag[3740+1]={
0,0,1,1,1,1,1,2,2,3,3,3,3,3,3,3,3,3,3,3,3,
3,3,3,3,3,4,4,5,5,5,5,5,5,5,5,5,5,6,6,6,6,
7,7,7,7,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,10,10,
10,10,10,10,10,10,11,11,12,12,12,13,13,13,13,14,14,14,14,14,14,
14,14,14,14,14,14,14,15,15,16,16,16,17,17,18,18,19,19,20,20,21,
21,22,22,23,23,24,25,26,27,28,29,30,30,31,32,32,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,2,2,2,2,2,2,3,3,3,3,3,3,3,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,1,1,1,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,3,3,3,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,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,1,1,1,1,1,1,
1,1,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,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,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,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,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,
1,1,1,1,1,1,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,1,1,1,2,2,3,3,3,
3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,6,6,6,6,6,7,7,7,7,7,7,7,7,7,
7,7,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,9,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,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,4,4,4,4,4,4,4,
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,8,8,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,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,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,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,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,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,4,4,4,4,4,4,4,4,4,4,4,
4,4,4,4,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,7,7,7,7,7,7,7,8,8,8,
8,8,8,8,8,8,9,9,9,9,9,9,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,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,3,3,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,
6,7,7,7,7,8,8,8,8,0,0,0,0,1,1,1,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,5,
5,5,5,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,
8,8,8,9,9,9,10,10,10,11,11,11,11,12,12,12,12,12,12,12,12,
12,12,12,13,13,13,14,14,14,15,15,16,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,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,1,1,1,1,1,1,1,1,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,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,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,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,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,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,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,10,10,
10,10,11,11,11,11,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,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,0,0,0,0,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,6,6,6,6,7,7,7,7,
8,8,8,8,9,9,9,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,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,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,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,1,1,1,2,2,3,3,3,3,3,3,3,3,4,
4,5,5,5,5,6,6,7,7,7,7,8,8,9,9,9,9,10,10,10,10,
10,10,10,10,10,11,11,11,11,11,11,12,12,13,13,13,14,14,14,14,14,
14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,21,22,22,23,23,24,
24,25,25,25,25,25,26,26,27,27,28,28,29,29,30,31,32,33,34,35,36,
37,38,39,40,40,41,42,43,44,45,46,47,48,49,50,51,51,0,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,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,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,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,3,
4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,7,7,7,8,8,8,
8,8,8,8,8,8,9,9,9,0,0,0,0,0,0,0,0,0,0,0,0,
0,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,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,4,4,4,4,4,4,4,4,
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,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,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,2,2,2,2,2,2,2,2,
2,2,2,2,2,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,
2,2,2,2,2,2,2,3,3,4,4,4,4,4,5,5,5,6,6,7,7,
8,8,8,9,9,9,10,10,10,10,10,11,11,11,11,11,12,12,12,13,13,
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,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,0,0,0,0,0,1,1,1,1,1,2,2,
2,2,2,3,3,3,3,3,3,3,3,4,4,4,5,5,5,5,5,5,5,
5,5,5,6,6,6,6,6,6,6,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,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,1,1,1,1,1,1,1,1,1,1,1,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,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,4,4,
4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,
6,6,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,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,4,
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,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,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,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,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,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,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,1,2,2,
2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,0,
0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,
6,7,7,7,8,8,8,9,9,9,10,10,10,11,11,11,12,12,12,13,13,
13,14,14,14,14,14,14,14,15,15,15,16,16,16,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,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,1,1,1,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,4,
4,4,4,5,5,5,6,6,6,6,6,6,7,7,7,8,8,8,8,9,9,
9,9,9,9,9,9,10,10,10,11,11,11,12,12,12,13,13,13,13,13,13,
14,14,14,15,15,16,16,16,17,17,18,18,18,19,19,19,19,19,20,20,21,
21,21,255}; //  index=3740 
unsigned int size[67]={
  121,
  49,
  81,
  15,
  27,
  26,
  65,
  58,
  58,
  24,
  94,
  74,
  25,
  108,
  13,
  60,
  40,
  43,
  27,
  57,
  123,
  81,
  87,
  48,
  44,
  46,
  63,
  50,
  26,
  20,
  57,
  81,
  80,
  47,
  32,
  116,
  67,
  17,
  18,
  117,
  70,
  42,
  69,
  23,
  94,
  44,
  36,
  51,
  61,
  90,
  55,
  60,
  109,
  34,
  53,
  56,
  23,
  26,
  27,
  46,
  46,
  46,
  49,
  53,
  57,
  47,
  88};
int cval[67]={
1201,1205,1207,1211,1213,1217,1219,1223,1225,1229,1231,
1235,1237,1241,1243,1247,1249,1253,1255,1259,1261,1265,
1267,1271,1273,1277,1279,1283,1285,1289,1291,1295,1297,
1301,1303,1307,1309,1313,1315,1319,1321,1325,1327,1331,
1333,1337,1339,1343,1345,1349,1351,1355,1357,1361,1363,
1367,1369,1373,1375,1379,1381,1385,1387,1391,1393,1397,
1399};
unsigned int numbc=67;