// c=1001 
int sinp[3355]={
29024,7256,1814,1646,4052,1010,722,1448,362,386,1070,6668,2126,4724,1136,284,
1910,1700,758,1052,3662,9292,14200,3550,1582,844,1066,22018,13012,15658,74950,73816,
18454,10690,6640,1660,562,958,610,970,4300,1816,454,2578,4696,1174,1492,4894,
2086,4210,3436,922,2842,11122,1418,1322,2174,1052,3182,2552,638,620,368,92,
932,76406,28904,7226,4694,2012,3452,926,1214,782,8288,2072,518,446,566,464,
116,662,500,770,3020,818,1886,980,2294,1112,278,356,1346,2222,1850,1670,
878,7736,1934,10796,2276,2156,656,164,6344,1586,2534,1202,2210,10448,2612,1364,
728,182,320,80,20,2048,512,128,32,8,2,1966,2746,1282,802,1288,
322,532,352,88,22,1354,760,190,2290,2170,1066,652,814,1666,910,5512,
1378,874,580,2002,6502,4288,1072,268,706,640,160,40,10,256,64,16,
4,442,418,2144,536,134,1316,500,2936,734,1046,29018,13160,3290,2306,1118,
1262,932,428,3746,1658,6662,6824,1706,4394,2522,1982,1748,770,542,938,2396,
5366,6890,3926,8348,2120,530,452,338,380,740,392,98,290,362,662,7148,
3362,1514,3422,2558,2072,518,1640,410,3044,824,206,1550,1382,2030,2630,268,
304,76,8362,5338,4726,2026,1774,2374,1144,286,7318,2998,1378,2368,592,148,
676,3988,1756,772,1402,1828,7876,4528,1132,466,2824,706,35578,12058,20836,47728,
11932,2122,1108,946,2698,2152,538,6904,1726,1648,412,502,442,916,892,1096,
274,9334,3754,2746,1888,472,118,298,802,1882,2158,1042,24586,14464,3616,904,
226,1396,1024,256,64,16,4,262,352,88,22,1826,1664,416,104,26,
1232,308,1340,506,7436,2492,722,2960,740,2636,2474,6488,1622,902,1304,326,
7388,1640,410,1556,8894,3590,2438,1952,488,122,2114,5668,1318,3742,3724,6748,
2536,634,724,1078,2122,2986,1894,5686,6010,1858,952,238,772,400,100,274,
358,2866,1330,754,538,598,2374,6160,1540,544,136,34,268,36304,9076,4120,
1030,29014,51520,12880,3220,2662,256,64,16,4,9356,3272,818,1274,734,4028,
9032,2258,4874,2084,1988,728,182,5282,1934,2948,6656,1664,416,104,26,266,
356,1004,6332,2008,502,7870,3208,802,3064,766,544,136,34,8896,2224,556,
1048,262,1372,514,17158,10012,2134,1630,868,886,4666,12244,20992,5248,1312,328,
82,688,172,982,12568,3142,6562,13054,5152,1288,322,874,4522,8680,2170,55984,
13996,3412,2830,1318,820,30494,9884,3506,4838,2072,518,452,5114,7166,6194,15158,
5942,2486,1190,704,176,44,266,794,1076,968,242,9326,3074,3818,2792,698,
1616,404,758,542,1130,1280,320,80,20,650,1010,85898,48962,42536,10634,6626,
529130,298280,74570,42590,18902,7346,1310,2588,1622,866,1724,1298,17588,3596,932,2684,
22448,5612,68374,39106,17434,6796,2176,544,136,34,1684,574,4114,1276,1582,2734,
8596,1870,13084,10378,4150,2980,8488,2122,1054,2116,2332,3574,2656,664,166,1366,
1414,2152,538,460,4060,49984,12496,3124,844,307546,115588,25318,30094,40186,15328,3832,
958,33382,387676,354016,88504,22126,55090,15946,6238,6490,2692,1504,376,94,1306,748,
856,214,766,63838,1342,18802,5740,2260,682,514,1690,892,4762,2044,2476,1039402,
390034,82870,47260,24262,10978,1658,920,230,16964,3440,860,890,704,176,44,1250,
728,182,1298,746,4652,3194,1352,338,386,404,1028,452,344,86,1304,326,
3482,1334,3706,2734,6244,3868,2896,724,5092,3382,1528,382,562,1708,580,3976,
994,33280,8320,2080,520,130,1966,1588,1096,274,512,128,32,8,2,5918,
2480,620,1076,4460,1886,968,242,788,1340,1826,1520,380,332,638,500,2168,
542,464,116,2192,548,806,1162,784,196,298,7672,1918,1732,586,622,254074,
183424,45856,11464,2866,1336,334,892,904,226,346,1072,268,1354,838,1948,7858,
3208,802,562,472,118,2272,568,142,10048,2512,628,3082,1324,4702,3298,1498,
14422,46498,17698,6898,2848,712,178,328,82,292,316,742,10534,16204,7762,3172,
856,214,8614,22252,6142,4108,2974,2326,68368,17092,3466,1432,358,1612,1702,12718,
9436,55246,24058,16906,5212,10372,2206,1894,12316,1774,4772,1130,686,9722,3908,5942,
3998,5852,5834,2450,1148,1730,268,1792,448,112,28,11638,11584,2896,724,3574,
3250,7864,1966,1000,250,3538,2248,562,2890,13690,9862,14500,3814,3844,1738,63748,
18586,16930,10180,3520,880,220,304,76,2836,952,238,352,88,22,466,736,
184,46,280,70,982,8282,5318,2258,3158,1448,362,974,3428,2288,572,542,
614,494,14312,3578,2672,668,3104,776,194,9314,10712,2678,1268,1016,254,1208,
302,3226,1474,922,610,634,502,4534,2866,4912,1228,1006,2104,526,2572,1384,
346,394,412,1336,334,5506,21526,5998,6316,2092,1138,1438,66298,25126,14794,5812,
1354,772,3454,10042,4030,3200,800,200,50,284,18806,39200,9800,2450,1184,296,
74,818,572,824,206,5306,2182,1084,1192,298,832,208,52,1678,3664,916,
922,3208,802,1720,430,586,994,3028,1516,550,472,118,310,382,7852,1738,
1642,1588,1090,91444,23224,5806,2098,139558,52600,13150,32188,21784,5446,2308,2236,1342,
2560,640,160,40,10,670,1246,578,992,248,62,290,830,824,206,344,
86,1526,896,224,56,14,272,68,686,524,134690,76430,28928,7232,1808,452,
794,2846,1334,842,4304,1076,2414,1172,6176,1544,386,884,1640,410,28262,12890,
9374,3782,15140,9578,57098,74432,18608,4652,1928,482,938,22010,19838,7706,7322,2180,
1280,320,80,20,1004,608,152,38,6154,2122,1864,466,442,592,148,1000,
250,538,2314,1726,2512,628,556,1504,376,94,808,202,1054,1150,5500,3160,
790,1936,484,358,4204,9874,3970,1756,1162,9064,2266,1096,274,370,406,1612,
69094,152200,38050,14536,3634,1630,1456,364,1744,436,664,166,1574,1556,560,140,
710,1070,1694,15866,6218,2600,650,512,128,32,8,2,470,2852,1376,344,
86,19694,20798,28502,63296,15824,3956,1010,2366,5174,2954,16594,10006,8062,3292,886,
1348,7018,7198,2968,742,778,15448,3862,4174,1834,2824,706,7738,14146,15838,6208,
1552,388,9238,7576,1894,4768,1192,298,1528,382,412,346,5398,5146,128212,55366,
16042,14812,3046,1264,316,328,82,718,538,796624,199156,7520,1880,470,446,1166,
800,200,50,8522,5468,6674,18728,4682,3308,890,2420,1286,752,188,1796,1484,
548,6386,10274,9950,17366,6782,12866,49640,12410,4778,3362,4118,1814,950,626,2984,
746,1094,680,170,770,1718,914,75560,18890,11300,14732,3032,758,554,986,52262,
19868,3266,5216,1304,326,392,98,1364,1058,2174,1538,2204,782,692,1652,1124,
1376,344,86,302,2138,2786,3632,908,440,110,836,1634,2660,3176,794,4244,
1868,620,386,10718,5264,1316,58094,12878,4094,5846,2462,5012,2084,23072,5768,1442,
2498,2996,45296,11324,10286,4460,1106,6404,10436,5684,2614,2146,1684,586,490,454,
1894,1576,394,418,1156,4330,886,1174,1336,334,4198,2548,748,1036,127774,82090,
31054,62518,35842,18586,7240,1810,982,1228,7816,1954,1804,3280,820,424,106,310,
850,712,178,1264,316,1270,1390,4114,1630,370,2470,2722,2128,532,25742,15158,
14078,5108,1166,1334,2414,2036,842,3242,6896,1724,8096,2024,506,734,18686,10424,
2606,2144,536,134,24608,6152,1538,848,212,1028,464,116,5672,1418,6626,2756,
788,5168,1292,11486,53066,52904,13226,28496,7124,2486,3386,5816,1454,1496,374,1604,
572,1622,2264,566,1766,1874,974,1226,2522,1184,296,74,1616,404,13078,5176,
1294,1420,538,982,640,160,40,10,1450,5734,2422,1180,1234,2332,10594,15616,
3904,976,244,748,412,1072,268,322,3418,2602,2788,2122,23716,11296,2824,706,
4924,1168,292,1414,802,20962,28738,66088,16522,9196,1996,646,514,556,376,94,
502,460,358,406,424,106,826,1144,286,856,214,352,88,22,280,70,
298,952,238,1900,628,14528,3632,908,5894,1874,1736,434,926,620,1952,488,
122,9296,2324,2276,1322,2540,4112,1028,1808,452,1592,398,422,596,2294,5084,
1226,2330,15290,32624,8156,1802,2816,704,176,44,998,758,3626,2468,1376,344,
86,3536,884,4436,2648,662,1268,24461576,6115394,2580716,50438348,7093370,30307994,43751288,10937822,4101956,
2193614,822878,308852,15856,3964,1798,3850,1444,544,136,34,286,844,1654,5866,2128,
532,688,172,2020,652,3598,826,20230,21346,8278,9796,2110,1870,8890,2632,658,
520,130,322,394,4030,2950,11806,7324,3100,3922,1744,436,1696,424,106,508,
1174,3706,2554,2068,850,592,148,2140,3112,778,796,4516,1120,280,70,5488,
1372,68344,17086,10294,23146,6988,4246,7594,2614,8566,4444,61270,45346,17278,10402,4174,
1220,8564,1880,470,950,1058,3884,1778,980,458,446,4136,1034,662,494,7106,
3992,998,7052,2276,800,200,50,788,422,1724,2030,11480,2870,2300,2912,728,
182,2210,3164,6620,11618,21200,5300,1268,512,128,32,8,2,1628,5162,1166,
3704,926,2084,854,1400,350,1598,3668,962,7376,1844,620,860,2528,632,158,
1436,1070,5648,1412,1292,11314,3610,3538,20956,4204,1072,268,2566,8320,2080,520,
130,760,190,346,4000,1000,250,1516,694,676,3820,1018,2164,2218,7834,2486,
1208,302,5078,2180,3620,6170,4160,1040,260,2822,1334,776,194,704,176,44,
284,5450,3092,2012,1424,356,1460,1100,482,4478,1742,4592,1148,644,2648,662,
524,374,416,104,26,9956,5510,2342,1154,7418,4862,1850,1730,4430,14816,3704,
926,5582,11566,30268,32374,14452,2986,1396,538,478,7102,6802,149014,243874,34192,8548,
5734,3916,1792,448,112,28,1324,3106,1294,2404,33346,9862,6238,26926,35962,13762,
4354,1708,2008,502,1006,2602,1252,3538,2494,8614,5536,1384,346,406,7966,18766,
17146,6706,6022,4078,2644,772,592,148,304,76,712,178,2818,1276,3052,1438,
5056,1264,316,66292,12706,4372,1096,274,1114,694,4996,1186,3304,826,586,496,
124,736,184,46,3592,898,2072,518,1754,1586,872,218,1100,2366,2024,506,
1856,464,116,11474,4580,1136,284,920,230,1840,460,364,346,3658,2752,688,
172,310,394,916,952,238,13660,2426,2384,596,2642,1916,638,518,3398,2444,
1526,4586,44726,7838,3218,1898,3428,3374,1544,386,914,2012,656,164,836,932,
998,11116,6016,1504,376,94,2434,1192,298,1138,706,544,136,34,292,334,
886,2074,1072,268,3232,808,202,6148,1432,358,2722,1300,1936,484,370,418,
436,550,3514,7714,3172,874,20218,16330,27994,8362,4540,2920,730,694,1912,478,
1786,2542,2128,532,1966,1804,13640,3410,3962,1766,1694,3596,1712,428,896,224,
56,14,12620,4250,1874,2990,3854,10238,23132,11090,8822,65270,48632,12158,20936,5234,
3224,806,1154,4340,1094,1316,5918,1216,304,76,502,7660,3454,1576,394,1666,
1510,916,1720,430,442,10258,6472,1618,1612,718,550,646,1312,328,82,748,
2044,664,166,538,2962,2368,592,148,1396,7822,3214,1486,838,826,12868,8848,
2212,1324,15598,6130,4150,4390,1726,928,232,58,9280,2320,580,2104,526,478,
460,556,1132,4672,1168,292,784,196,1960,490,1474,3256,814,586,1828,2728,
682,16900,4372,3178,3292,898,1186,2242,2674,2206,1108,17380,5590,3376,844,610,
4186,7174,8632,2158,1090,1204,5798,2456,614,512,128,32,8,2,1340,1304,
326,404,818,50210,25076,3230,2384,596,872,218,902,620,398,4628,2006,1034,
1286,764,4490,21860,36980,20078,6140,48644,8738,33578,19592,4898,4178,166742,62810,27308,
5402,3202,2374,1642,898,1402,808,202,358,1726,2380,3028,850,832,208,52,
292,42658,501352,125338,47284,9148,5200,1300,526,6334,5296,1324,1078,1312,328,82,
670,1906,1030,1246,2392,598,1042,5584,1396,544,136,34,3040,760,190,1408,
352,88,22,718,3514,1600,400,100,508,68326,38770,11398,5620,1336,334,2716,
4012,1834,970,646,1084,1798,1570,4498,20212,4072,1018,664,166,3292,17608,4402,
1732,2056,514,1240,310,880,220,5128,1282,1564,8764,5038,1024,256,64,16,
4,2174,4604,17294,10436,2240,560,140,2390,3362,1544,386,428,1526,2258,1130,
6470,10490,3446,2888,722,554,998,5630,12110,7520,1880,470,1742,1688,422,7088,
1772,1538,860,950,7736,1934,1796,620,2516,6602,3812,2116,13648,3412,2224,556,
388,4288,1072,268,334,2038,1048,262,382,604,1156,4126,4144,1036,478,3982,
19048,4762,3388,1804,622,1252,1876,10084,5602,33706,78484,13312,3328,832,208,52,
724,88006,33286,12766,5746,6196,2452,14674,96106,238864,59716,90922,59044,350446,189712,47428,
73426,54226,53698,52984,13246,4222,1684,1162,1306,1444,2134,1084,3656,914,1226,2372,
1274,3926,8318,3404,21098,19154,11486,4592,1148,500,2630,1238,5234,8380,3070,2440,
610,514,478,982,5626,2680,670,1090,694,3196,1612,20746,6334,4276,1936,484,
376,94,766,1144,286,874,844,2638,2284,6064,1516,430,6040,1510,1978,3088,
772,2014,1846,4654,6976,1744,436,1126,15832,3958,8956,3232,808,202,556,10694,
8288,2072,518,3404,1442,1646,2522,1232,308,344,86,764,1682,974,5624,1406,
2546,6626,12428,4376,1094,1946,1016,254,1574,3188,884,452,1136,284,6398,6758,
3674,1664,416,104,26,296,74,314,404,362,422,1064,266,386,2816,704,
176,44,728,182,818,1538,1264,316,346,1654,1012,87658,113272,28318,10906,10564,
3688,922,2140,688,172,526,484,4612,2014,1042,22000,5500,1318,2680,670,538,
1816,454,1210,2074,3112,778,3118,1456,364,1228,13642,29680,7420,1678,916,1292,
530,1814,968,242,1466,1544,386,7016,1754,1706,1448,362,980,1034,5180,1232,
308,806,590,950,644,4406,1940,5540,3704,926,764,746,1142,716,422,446,
1358,1616,404,10724,4706,8294,3398,1562,1598,93806,61214,17720,4430,2912,728,182,
356,2426,2084,2246,1130,1304,326,410,2416,604,1624,406,1000,250,382,7078,
4702,6508,5674,4162,2242,23602,11002,4414,9424,2356,730,562,1282,7564,2848,712,
178,1120,280,70,760,190,2578,10090,4072,1018,670,3190,3550,8410,3442,1720,
430,1732,748,1768,442,454,976,244,334,1342,5050,2182,1948,7888,1972,658,
2272,568,142,12262,7618,5836,2362,1174,1324,1108,496,124,17824,4456,1114,706,
9994,4036,1072,268,796,8590,29434,11326,44068,28030,85810,37246,112054,82000,20500,4132,
1076,2984,746,716,1676,1850,2450,1208,302,1802,770,578,506,1262,1364,698,
2234,6374,6752,1688,422,1730,938,590,1910,11450,5792,1448,362,608,152,38,
1406,1514,932,464,116,1094,2012,1256,314,2774,18254,13088,3272,818,596,15604,
53002,30538,17902,5542,2368,592,148,766,2350,1168,292,2194,4138,3052,862,1414,
820,1006,790,586,1054,1348,11206,4492,1132,502,478,1252,7804,31580,6212,2474,
8252,1838,980,8876,4346,5048,1262,764,434,1082,2294,1154,1376,344,86,5858,
4022,1640,410,1586,2420,2402,2078,1070,692,3662,1664,416,104,26,1298,2366,
1178,2072,518,3590,6506,21566,8378,8450,5480,1370,7424,1856,464,116,1430,974,
656,164,3530,6830,2852,2126,1088,272,68,746,21998,8540,1892,2096,524,3878,
2690,2240,560,140,1916,650,4310,2288,572,398,440,110,332,1124,1934,1016,
254,386,944,236,542,494,476,380,362,8684,1730,1700,-4246,-5806,-4438,-3862,
-12376,-3094,-8236,-5158,-4726,-6778,9988,2164,814,1186,736,184,46,754,574,7114,
3334,6586,2362,1174,2374,9652,4534,4198,20986,6412,6424,1606,4894,2902,3832,958,
20194,7864,1966,1834,7558,11932,4084,1084,1066,2024,506,482,2480,620,5534,14360,
3590,2750,26960,6740,1556,584,146,1142,1322,788,440,110,5048,1262,2132,692,
422,968,242,3344,836,764,2858,1364,548,5750,3266,1430,6260,1466,842,608,
152,38,752,188,512,128,32,8,2,320,80,20,296,74,3304,826,
3424,856,214,2020,1300,1414,910,634,41680,10420,20920,5230,2254,1138,1372,550,
1624,406,3142,1396,3262,1516,4918,3136,784,196,6664,1666,3448,862,616,154,
5404,1306,6340,1738,3946,4720,1180,514,3164,1874,20702,20066,18326,7166,4088,1022,
1496,374,434,2936,734,896,224,56,14,518,488,122,780536,195134,62834,40154,
61418,35282,11734,7336,1834,982,1288,322,2098,23920,5980,11818,4726,3394,4042,1810,
1024,256,64,16,4,13924,1906,1918,3016,754,530488,132622,1462150,926830,1175410,373222,
178822,114724,16648,4162,4528,1132,1054,3472,868,772,3502,44974,76408,19102,20440,5110,
3610,1648,412,15814,17650,324748,1018,676,610,1324,1108,502,2536,634,532,394,
442,460,1972,664,166,916,466,646,808,202,370,1432,358,1042,23636,6056,
1514,1478,15812,3260,2600,650,2312,578,512,128,32,8,2,296,74,5120,
1280,320,80,20,7226,3788,4796,3086,2474,2114,1088,272,68,308,560,140,
6194,2618,5732,1370,902,5606,9494,13814,13058,5192,1298,782,1178,848,212,3284,
24560,6140,2144,536,134,4148,1100,4220,3548,1736,434,458,764,1010,674,548,
398,962,656,164,326,7064,1766,4634,1820,1250,808,202,1570,4390,1942,1024,
256,64,16,4,3904,976,244,7792,1948,1408,352,88,22,304,76,310,
412,2050,2798,1346,6008,1502,860,458,1796,1232,308,2606,1274,6332,1484,728,
182,7316,4496,1124,1058,2246,1160,290,1760,440,110,338,932,1004,2228,650980,
122356,35608,8902,85792,21448,5362,2308,730,6088,1522,868,460,1606,3856,964,478,
1012,11002,5680,1420,1918,1822,1768,442,1264,316,832,208,52,1930,4684,3388,
1696,424,106,550,1876,784,196,334,6544,1636,604,982,3658,3874,1750,4630,
15376,3844,1018,8086,9784,2446,3440,860,11432,2858,1370,812,974,3656,914,1622,
1658,920,230,1730,7400,1850,992,248,62,1400,350,1712,428,866,2468,950,
1280,320,80,20,302,7058,3566,19478,11702,7328,1832,458,470,1010,806,9658,
9568,2392,598,1666,1684,30952,7738,7948,4438,1438,838,22366,8686,3556,5734,3502,
1612,1366,11188,3976,994,1306,2986,2554,3574,1528,382,442,1792,448,112,28,
304,76,8272,2068,3736,934,6166,3286,1384,346,1582,892,466,1882,1028,3086,
11420,37916,32084,11744,2936,734,848,212,3374,2510,3518,1514,6488,1622,908,470,
476,1190,746,11960,2990,2348,740,1736,434,1790,3158,1484,578,2306,5354,32192,
8048,2012,3842,7298,11672,2918,1394,2600,650,1136,284,10862,7100,1442,12152,3038,
1334,800,200,50,1466,1574,890,1250,6326,2672,668};
unsigned char cflag[3355+1]={
0,0,0,0,0,0,0,0,0,0,0,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,1,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,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,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,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,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,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,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,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,1,1,1,1,1,1,1,
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,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,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,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,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,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,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,2,2,
2,2,2,2,2,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,
4,5,5,5,6,6,0,0,0,0,0,1,1,1,1,1,1,1,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,2,2,2,2,2,2,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,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,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,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,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,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,
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,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,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,
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,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,3,3,4,4,4,4,4,4,4,5,5,5,6,6,6,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,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
4,4,4,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,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,
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,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,0,0,0,
0,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,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,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,
5,5,5,6,6,6,6,6,6,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,
4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,6,6,
6,6,6,7,7,7,7,8,8,8,8,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,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,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,3,3,3,3,3,3,4,4,
4,4,4,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,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,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,3,3,3,3,3,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,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,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,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,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,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,2,2,2,2,2,2,2,2,3,3,3,3,3,
3,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,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,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,1,1,1,1,1,1,1,1,1,1,1,1,1,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,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,3,3,3,3,3,3,3,3,3,3,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,6,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,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,0,0,0,0,
0,0,0,0,0,0,0,0,1,2,3,4,4,4,5,6,7,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,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,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,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,3,3,3,3,3,3,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,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,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,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,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,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,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,255}; //  index=3355 
unsigned int size[67]={
  21,
  33,
  69,
  40,
  60,
  76,
  32,
  47,
  25,
  50,
  61,
  83,
  29,
  24,
  28,
  84,
  12,
  47,
  28,
  36,
  17,
  49,
  65,
  52,
  31,
  48,
  111,
  52,
  64,
  71,
  62,
  77,
  69,
  26,
  51,
  84,
  19,
  14,
  26,
  53,
  33,
  95,
  43,
  96,
  42,
  65,
  17,
  50,
  55,
  41,
  57,
  88,
  47,
  30,
  105,
  35,
  53,
  42,
  26,
  76,
  76,
  24,
  29,
  55,
  41,
  47,
  61};
int cval[67]={
1001,1003,1007,1009,1013,1015,1019,1021,1025,1027,1031,
1033,1037,1039,1043,1045,1049,1051,1055,1057,1061,1063,
1067,1069,1073,1075,1079,1081,1085,1087,1091,1093,1097,
1099,1103,1105,1109,1111,1115,1117,1121,1123,1127,1129,
1133,1135,1139,1141,1145,1147,1151,1153,1157,1159,1163,
1165,1169,1171,1175,1177,1181,1183,1187,1189,1193,1195,
1199};
unsigned int numbc=67;