#include <cstdio> using namespace std; int xxx[] = {1,0,0,0,1,0,0,0,2,0,0,0,0,1,0,0,1,1,0,0,1,1,0,0,2,1,0,0,0,2,0,0,1,2,0,0,1,2,0,0,2,2,0,0,0,3,0,0,1,3,0,0,1,3,0,0,0,2,0,0,0,2,0,0,0,2,1,0,0,2,1,0,0,2,2,0,0,2,2,0,0,2,3,0,0,2,3,0,0,2,4,0,0,2,4,0,0,2,5,0,0,2,5,0,0,2,6,0,0,2,6,0,0,4,0,1,0,0,4,0,0,2,3,1,0,2,3,1,0,4,2,2,0,0,6,1,0,2,5,2,0,2,5,2,0,4,4,3,0,0,8,2,0,2,7,3,0,2,7,3,0,2,4,2,0,2,4,2,0,2,5,3,0,2,5,3,0,2,6,4,0,2,6,4,0,2,7,5,0,2,7,5,0,2,8,6,0,2,8,6,0,4,4,5,0,0,8,4,0,2,7,6,0,2,7,6,0,4,6,8,0,0,10,7,0,2,9,9,0,2,9,9,0,2,8,8,0,2,8,8,0,2,9,10,0,2,9,10,0,2,10,12,0,2,10,12,0,4,8,13,0,0,12,12,0,2,11,15,0,2,11,15,0,2,12,18,0,2,12,18,0,1,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,2,2,0,0,0,0,0,0,0,1,2,1,0,0,0,0,2,2,2,0,0,0,0,0,0,0,4,2,0,0,0,0,2,4,2,1,0,0,0,0,0,1,4,4,0,0,0,0,2,4,4,2,0,0,0,0,0,0,6,6,0,0,0,0,2,6,4,4,0,0,0,0,0,0,0,2,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,2,4,0,0,0,0,2,4,3,0,0,0,0,0,0,0,2,8,2,0,0,0,2,4,6,4,0,0,0,0,0,0,2,12,6,0,0,0,2,4,9,8,2,0,0,0,0,0,2,16,12,0,0,0,2,4,12,12,6,0,0,0,0,0,2,20,20,0,0,0,2,4,15,16,12,0,0,0,0,0,2,24,30,0,0,0,2,4,18,20,20,0,0,0,0,0,6,0,10,0,0,0,0,8,0,12,0,0,0,0,0,0,2,12,10,6,0,0,0,8,6,10,12,0,0,0,0,0,6,8,24,10,1,0,0,8,4,24,14,6,0,0,0,0,2,20,28,20,2,0,0,8,10,22,30,10,1,0,0,0,6,16,46,28,4,0,0,8,8,36,36,20,2,0,0,0,2,28,54,42,6,0,0,8,14,34,56,28,4,0,0,0,2,16,20,16,2,0,0,8,8,16,24,8,0,0,0,0,2,20,32,30,6,0,0,8,10,22,38,20,2,0,0,0,2,24,46,48,12,0,0,8,12,28,54,36,6,0,0,0,2,28,62,70,20,0,0,8,14,34,72,56,12,0,0,0,2,32,80,96,30,0,0,8,16,40,92,80,20,0,0,0,6,16,54,52,16,0,0,8,8,36,52,44,8,0,0,0,2,28,66,84,30,0,0,8,14,34,80,70,19,0,0,0,6,24,92,118,49,0,0,8,12,48,98,106,34,0,0,0,2,36,108,162,72,0,0,8,18,46,130,144,54,0,0,0,2,32,88,128,56,0,0,8,16,40,108,112,40,0,0,0,2,36,112,180,90,0,0,8,18,46,138,162,69,0,0,0,2,40,138,240,132,0,0,8,20,52,170,220,106,0,0,0,6,32,146,248,144,0,0,8,16,60,168,232,116,0,0,0,2,44,170,330,210,0,0,8,22,58,212,308,176,0,0,0,2,48,204,432,306,0,0,8,24,64,256,408,264,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,2,1,0,0,0,0,0,0,0,0,2,2,2,0,0,0,0,0,0,0,0,0,1,2,4,2,1,0,0,0,0,0,0,0,1,2,4,2,1,0,0,0,0,0,0,0,0,2,4,6,4,0,0,0,0,0,0,0,2,3,8,3,2,1,0,0,0,0,0,0,1,3,8,8,6,2,0,0,0,0,0,0,1,3,8,8,6,2,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,3,4,2,0,1,0,0,0,0,0,0,0,3,4,2,0,1,0,0,0,0,0,0,0,2,6,8,6,4,2,0,0,0,0,0,0,2,6,8,6,4,2,0,0,0,0,0,0,2,6,13,16,12,10,1,0,0,0,0,0,2,6,13,16,12,10,1,0,0,0,0,0,2,6,18,26,26,26,6,0,0,0,0,0,2,6,18,26,26,26,6,0,0,0,0,0,2,6,23,36,46,50,19,0,0,0,0,0,2,6,23,36,46,50,19,0,0,0,0,0,2,6,28,46,72,82,44,0,0,0,0,0,2,6,28,46,72,82,44,0,0,0,0,0,0,4,0,26,0,10,0,0,0,0,0,0,4,0,24,0,12,0,4,0,0,0,0,0,1,4,14,23,26,25,14,3,0,0,0,0,1,4,14,23,26,25,14,3,0,0,0,0,0,4,2,46,42,66,50,12,2,0,0,0,2,4,28,29,54,47,44,23,0,0,0,0,1,4,16,52,74,102,102,50,7,0,0,0,1,4,16,52,74,102,102,50,7,0,0,0,0,4,4,67,98,177,192,95,22,1,0,0,2,4,30,66,110,146,174,118,20,0,0,0,1,4,18,81,138,235,294,193,46,2,0,0,1,4,18,81,138,235,294,193,46,2,0,0,0,6,16,32,56,72,64,30,4,0,0,0,0,6,16,32,56,72,64,30,4,0,0,0,0,6,17,46,87,132,155,100,26,1,0,0,0,6,17,46,87,132,155,100,26,1,0,0,0,6,18,60,122,208,286,226,80,6,0,0,0,6,18,60,122,208,286,226,80,6,0,0,0,6,19,74,161,300,461,420,178,19,0,0,0,6,19,74,161,300,461,420,178,19,0,0,0,6,20,88,204,408,684,694,332,44,0,0,0,6,20,88,204,408,684,694,332,44,0,0,0,4,4,64,120,220,348,270,100,14,0,0,0,8,32,56,132,224,300,276,120,8,0,0,0,6,19,74,169,330,551,556,283,42,0,0,0,6,19,74,169,330,551,556,283,42,0,0,0,4,6,84,210,444,886,966,550,114,0,0,0,8,34,92,222,468,794,968,594,101,0,0,0,6,21,102,267,600,1195,1524,1004,221,0,0,0,6,21,102,267,600,1195,1524,1004,221,0,0,0,6,20,88,220,472,892,1066,668,138,0,0,0,6,20,88,220,472,892,1066,668,138,0,0,0,6,21,102,275,634,1313,1780,1283,326,0,0,0,6,21,102,275,634,1313,1780,1283,326,0,0,0,6,22,116,334,816,1818,2722,2176,638,0,0,0,6,22,116,334,816,1818,2722,2176,638,0,0,0,4,8,104,332,796,1968,2898,2340,750,0,0,0,8,36,128,344,872,1800,2880,2432,724,0,0,0,6,23,130,405,1056,2557,4324,3956,1403,0,0,0,6,23,130,405,1056,2557,4324,3956,1403,0,0,0,6,24,144,480,1320,3416,6366,6452,2624,0,0,0,6,24,144,480,1320,3416,6366,6452,2624,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,2,0,0,0,0,0,0,0,0,0,0,0,0,2,3,8,3,2,1,0,0,0,0,0,0,0,0,0,0,0,2,4,6,4,0,0,0,0,0,0,0,0,0,0,0,2,6,10,10,6,2,2,0,0,0,0,0,0,0,0,0,0,0,8,8,12,4,0,0,0,0,0,0,0,0,0,0,0,2,4,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,0,0,0,0,0,0,0,0,0,0,0,0,2,0,8,16,8,0,2,0,2,0,0,0,0,0,0,0,0,0,0,8,12,8,4,0,0,0,0,0,0,0,0,0,2,0,7,20,30,24,11,4,8,4,0,0,0,0,0,0,0,0,0,8,18,32,26,12,4,0,0,0,0,0,0,0,2,0,8,20,48,60,45,28,22,20,2,0,0,0,0,0,0,0,0,8,24,56,64,56,24,8,0,0,0,0,0,0,2,0,9,20,66,96,104,84,58,60,12,0,0,0,0,0,0,0,0,8,30,80,118,132,78,40,4,0,0,0,0,0,2,0,10,20,84,132,188,172,134,140,42,0,0,0,0,0,0,0,0,8,36,104,188,240,184,112,24,0,0,0,0,0,0,0,12,0,36,0,13,0,4,0,1,0,0,0,0,0,0,0,0,12,0,36,0,12,0,0,0,0,0,0,0,0,0,0,10,8,34,62,47,38,30,10,14,2,0,0,0,0,0,0,0,2,22,26,70,70,26,22,2,0,0,0,0,0,0,0,8,8,48,66,151,136,107,94,42,32,1,0,0,0,0,0,0,6,20,62,92,178,158,86,66,4,0,0,0,0,0,0,8,12,50,124,204,286,302,246,202,92,22,0,0,0,0,0,0,2,26,56,178,316,348,304,198,82,2,0,0,0,0,0,8,8,60,140,309,490,579,584,462,298,73,4,0,0,0,0,0,6,24,92,224,496,654,628,558,242,46,0,0,0,0,0,8,12,62,198,394,728,980,1060,1032,644,210,18,0,0,0,0,0,2,30,86,302,738,1058,1186,1078,640,152,8,0,0,0,0,8,8,44,96,136,176,176,128,100,40,12,0,0,0,0,0,0,0,24,48,120,192,216,176,88,32,0,0,0,0,0,0,6,12,52,120,229,378,466,446,410,234,82,10,0,0,0,0,0,0,24,66,182,350,514,558,426,226,54,0,0,0,0,0,6,12,56,156,332,616,896,1032,1082,764,332,60,2,0,0,0,0,0,24,84,248,552,940,1192,1140,784,288,28,0,0,0,0,6,12,60,192,443,906,1478,1922,2246,1850,942,214,12,0,0,0,0,0,24,102,318,798,1506,2130,2358,1914,886,152,4,0,0,0,6,12,64,228,562,1248,2224,3168,4038,3732,2144,572,42,0,0,0,0,0,24,120,392,1088,2224,3424,4216,3856,2080,472,24,0,0,0,4,16,52,128,365,664,970,1292,1259,1000,506,96,6,0,0,0,0,0,32,100,224,576,1060,1308,1468,1040,412,72,0,0,0,0,4,16,64,180,452,998,1740,2406,3004,2756,1620,476,39,0,0,0,0,0,24,102,330,836,1694,2648,3176,2864,1572,382,22,0,0,0,4,16,60,200,591,1390,2606,4246,5563,5910,4090,1410,162,0,0,0,0,0,32,136,396,1138,2612,4226,6032,6178,3954,1294,114,0,0,0,4,16,72,252,710,1816,3812,6332,9516,11024,8380,3396,460,0,0,0,0,0,24,138,494,1506,3594,6650,9870,11386,8402,3156,380,0,0,0,4,16,68,216,584,1416,2816,4424,6264,6792,4844,1856,229,0,0,0,0,0,24,120,416,1168,2656,4704,6544,7056,4840,1672,176,0,0,0,4,16,72,252,724,1890,4140,7134,11140,13636,11174,5080,808,0,0,0,0,0,24,138,506,1548,3838,7436,11520,14100,11270,4786,694,0,0,0,4,16,76,288,872,2420,5724,10612,17916,24092,21980,11292,2136,0,0,0,0,0,24,156,600,1976,5252,10920,18388,24800,22232,10868,1936,0,0,0,4,16,68,272,877,2484,5786,11376,18851,26036,24618,13056,2632,0,0,0,0,0,32,172,608,1972,5508,11112,19668,26948,24692,12696,2392,0,0,0,4,16,80,324,1042,3084,7980,16068,29688,44556,46448,27956,6588,0,0,0,0,0,24,174,710,2498,7210,16334,30218,45682,47086,27316,6204,0,0,0,4,16,84,360,1220,3808,10592,22800,45288,74096,85732,57960,15976,0,0,0,0,0,24,192,824,3072,9480,22992,45816,75712,86912,57072,15344,1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,8,8,6,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,8,8,6,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,6,8,6,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,6,8,6,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,11,24,32,28,16,4,4,0,1,0,0,0,0,0,0,0,0,0,2,4,11,24,32,28,16,4,4,0,1,0,0,0,0,0,0,0,0,0,2,4,14,28,62,98,82,54,32,10,8,2,0,0,0,0,0,0,0,0,2,4,14,28,62,98,82,54,32,10,8,2,0,0,0,0,0,0,0,0,2,4,18,30,91,176,208,206,133,76,38,18,1,0,0,0,0,0,0,0,2,4,18,30,91,176,208,206,133,76,38,18,1,0,0,0,0,0,0,0,2,4,22,32,122,254,392,472,376,278,138,82,10,0,0,0,0,0,0,0,2,4,22,32,122,254,392,472,376,278,138,82,10,0,0,0,0,0,0,0,0,12,0,36,0,13,0,4,0,1,0,0,0,0,0,0,0,0,0,0,0,0,12,0,36,0,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,9,21,44,81,92,67,44,23,7,4,2,0,0,0,0,0,0,0,0,2,9,21,44,81,92,67,44,23,7,4,2,0,0,0,0,0,0,0,0,4,10,30,74,162,220,290,272,190,170,46,40,4,0,0,0,0,0,0,0,0,6,8,66,106,232,318,324,244,82,74,16,15,0,0,0,0,0,0,0,2,7,21,88,181,398,644,810,826,637,371,206,83,10,0,0,0,0,0,0,2,7,21,88,181,398,644,810,826,637,371,206,83,10,0,0,0,0,0,0,4,8,34,114,276,640,1083,1540,1885,1910,1321,902,404,70,6,0,0,0,0,0,0,6,8,92,196,536,1090,1696,2072,1806,1346,796,400,108,0,0,0,0,0,0,2,7,21,118,291,794,1643,2745,3820,4125,3432,2478,1348,394,34,0,0,0,0,0,2,7,21,118,291,794,1643,2745,3820,4125,3432,2478,1348,394,34,0,0,0,0,0,0,8,24,60,130,260,402,436,370,256,144,68,22,4,0,0,0,0,0,0,0,8,24,60,130,260,402,436,370,256,144,68,22,4,0,0,0,0,0,0,0,7,22,78,184,424,812,1219,1478,1394,1060,663,310,91,10,0,0,0,0,0,0,7,22,78,184,424,812,1219,1478,1394,1060,663,310,91,10,0,0,0,0,0,0,6,24,90,230,616,1334,2342,3404,3992,3780,2892,1722,682,132,6,0,0,0,0,0,6,24,90,230,616,1334,2342,3404,3992,3780,2892,1722,682,132,6,0,0,0,0,0,6,24,99,284,822,1957,3847,6309,8531,9344,8342,5896,2857,755,66,1,0,0,0,0,6,24,99,284,822,1957,3847,6309,8531,9344,8342,5896,2857,755,66,1,0,0,0,0,6,24,108,338,1040,2692,5758,10352,15546,18940,18980,15226,8560,2762,346,10,0,0,0,0,6,24,108,338,1040,2692,5758,10352,15546,18940,18980,15226,8560,2762,346,10,0,0,0,0,12,24,104,304,668,1398,2560,3790,4860,4830,4032,2643,1100,252,20,1,0,0,0,0,0,16,80,184,572,1344,2532,4108,4936,4948,3876,2472,1164,284,16,0,0,0,0,0,5,22,102,294,838,2057,4292,7637,11235,13406,13052,10286,5786,1961,271,9,0,0,0,0,5,22,102,294,838,2057,4292,7637,11235,13406,13052,10286,5786,1961,271,9,0,0,0,0,10,28,124,428,1172,2968,6622,12544,20814,28212,31702,29032,19188,7898,1540,102,0,0,0,0,0,16,94,276,968,2729,6380,12943,21300,28688,31616,28437,19020,8115,1594,72,0,0,0,0,5,22,116,410,1314,3756,9198,19447,35098,52076,64089,64794,48799,23692,5748,440,0,0,0,0,5,22,116,410,1314,3756,9198,19447,35098,52076,64089,64794,48799,23692,5748,440,0,0,0,0,4,24,112,346,1076,2922,6744,13520,23000,32032,36756,34558,24096,10798,2356,152,0,0,0,0,4,24,112,346,1076,2922,6744,13520,23000,32032,36756,34558,24096,10798,2356,152,0,0,0,0,4,24,119,406,1328,3897,9742,21297,40124,62468,80743,86250,69876,37467,10590,999,0,0,0,0,4,24,119,406,1328,3897,9742,21297,40124,62468,80743,86250,69876,37467,10590,999,0,0,0,0,4,24,126,466,1592,4992,13312,31166,63546,107816,152656,179986,163290,99714,33436,4026,0,0,0,0,4,24,126,466,1592,4992,13312,31166,63546,107816,152656,179986,163290,99714,33436,4026,0,0,0,0,8,32,144,560,1756,5328,13976,32288,66124,114754,165872,200823,187496,117614,41336,5469,0,0,0,0,0,16,108,376,1444,4792,13248,32228,67412,115948,166904,199712,185664,118308,41872,5272,0,0,0,0,4,24,133,530,1884,6347,18138,45844,102139,191428,300644,397172,411609,294071,120722,19219,0,0,0,0,4,24,133,530,1884,6347,18138,45844,102139,191428,300644,397172,411609,294071,120722,19219,0,0,0,0,4,24,140,594,2188,7830,23704,63718,152244,308648,525684,759342,871660,700828,331668,63980,0,0,0,0,4,24,140,594,2188,7830,23704,63718,152244,308648,525684,759342,871660,700828,331668,63980,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,6,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,6,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,2,8,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,6,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,18,32,26,12,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,7,20,30,24,11,4,8,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,20,56,90,120,96,40,16,0,4,0,2,0,0,0,0,0,0,0,0,0,2,0,8,16,46,80,96,80,58,40,32,8,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,26,72,148,280,338,312,178,60,36,8,14,4,0,0,0,0,0,0,0,0,2,0,9,16,62,104,201,276,260,232,171,100,64,16,6,0,0,0,0,0,0,0,0,0,0,0,0,8,32,88,218,448,710,912,710,448,218,88,62,32,2,0,0,0,0,0,0,0,2,0,10,16,80,124,316,500,652,748,596,476,300,148,52,12,0,0,0,0,0,0,0,0,0,0,4,0,26,0,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,24,0,12,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,48,76,94,124,68,16,20,0,0,0,2,0,0,0,0,0,0,0,0,0,2,0,12,30,72,84,84,72,54,32,12,18,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,9,44,112,230,407,512,481,380,145,104,26,18,7,6,0,0,0,0,0,0,0,2,0,4,30,92,126,290,418,436,420,296,220,92,80,10,4,0,0,0,0,0,0,0,0,0,0,4,0,44,142,324,736,1254,1684,1844,1440,880,484,236,96,62,10,0,0,0,0,0,0,2,0,4,38,96,196,492,836,1184,1554,1580,1298,1012,628,254,126,24,0,0,0,0,0,0,0,0,0,4,9,44,176,466,1135,2222,3562,4716,4954,4270,2739,1510,802,332,127,4,0,0,0,0,0,2,0,4,28,110,242,616,1376,2276,3480,4478,4566,3940,3074,1758,842,368,32,0,0,0,0,0,0,0,0,4,0,52,186,528,1600,3380,6310,9746,11778,11770,9616,6260,3516,1792,568,82,0,0,0,0,0,2,0,4,38,112,304,840,1968,3690,6274,9094,11038,11408,9816,6684,3876,1768,480,12,0,0,0,0,0,0,0,0,4,32,102,272,392,688,940,688,392,272,104,48,24,16,2,0,0,0,0,0,0,0,0,16,16,64,184,320,488,664,664,608,472,280,168,64,24,0,0,0,0,0,0,0,0,0,0,0,4,24,132,366,714,1576,2634,3380,3612,3004,1852,1098,566,252,86,20,0,0,0,0,0,0,0,12,16,76,220,492,972,1650,2486,3176,3172,2804,2172,1272,632,238,50,0,0,0,0,0,0,0,0,0,4,20,150,476,1096,2596,5110,8300,11060,11980,10462,7668,4600,2412,972,252,30,0,0,0,0,0,0,12,14,76,272,656,1480,2960,5202,8008,10288,11256,10454,8032,5112,2536,882,168,0,0,0,0,0,0,0,0,4,20,162,572,1526,3874,8446,15646,24094,30918,32706,28748,20766,12626,5914,1858,294,14,0,0,0,0,0,12,12,82,314,802,2068,4576,8890,15482,23106,29438,31946,29010,21852,13216,5926,1658,162,0,0,0,0,0,0,0,4,20,174,668,1982,5388,12718,25876,44262,63820,76914,77380,64330,44596,24016,8812,1726,128,2,0,0,0,0,12,12,84,348,968,2708,6444,13664,26080,43172,61428,75008,77112,65980,45980,24400,8524,1396,56,0,0,0,0,0,0,4,40,138,452,1290,2684,5314,9496,13310,15604,14854,11384,7400,4048,1796,556,66,4,0,0,0,0,0,8,16,64,264,660,1372,3180,5852,9160,12768,14612,14272,11928,7928,4396,1772,384,24,0,0,0,0,0,0,0,4,12,172,564,1542,4162,9248,18250,30872,43642,51012,49584,39712,26774,14422,5426,1162,98,2,0,0,0,0,8,14,88,288,822,2170,4806,9981,18810,29980,41386,49561,49420,41018,27924,14693,5208,898,40,0,0,0,0,0,0,4,32,174,660,2232,5762,14074,30716,57199,91894,125336,141112,133008,104176,65431,30096,8313,980,41,0,0,0,0,8,12,74,332,966,2626,6920,15488,31792,57374,89672,120840,139634,133880,106718,67510,29680,7594,788,12,0,0,0,0,0,4,12,192,754,2516,7694,20056,46860,95450,168112,251990,319506,337616,298654,213862,112116,37066,5866,294,0,0,0,0,8,12,96,352,1132,3558,9218,22234,49226,95908,164264,246440,314752,338510,302994,217044,112704,35918,5180,210,0,0,0,0,0,4,8,182,680,2056,5872,14480,32264,62080,102608,143272,167976,163560,133376,88088,42344,12780,1784,74,0,0,0,0,8,12,88,328,992,2872,6984,15992,33864,62032,99344,139328,165456,165000,136264,89752,42496,12036,1416,40,0,0,0,0,0,4,8,190,780,2590,7882,20980,50690,106982,196822,310010,414828,463936,435502,333964,191014,71572,13618,856,0,0,0,0,8,10,94,362,1142,3626,9518,23431,53694,108510,193166,303353,408040,463822,440340,338337,192642,70282,12500,681,0,0,0,0,0,4,8,198,880,3146,10156,28756,74104,168162,335132,577608,853504,1059814,1108836,953522,621040,271088,63516,5270,0,0,0,0,8,10,96,388,1312,4428,12332,32350,78952,172008,331724,568350,840656,1055932,1115196,961902,625868,269484,61032,4740,0,0,0,0,0,4,24,202,888,3406,10316,29586,76372,175264,353252,624224,937360,1191972,1275184,1120668,755260,344048,85160,7706,0,0,0,0,8,8,84,392,1292,4216,12504,32804,81356,180004,353864,611784,925676,1184080,1278568,1134728,760264,341500,82844,6944,0,0,0,0,0,4,8,206,988,3772,12960,39136,108034,265718,578770,1102194,1819200,2541024,3006876,2952278,2239742,1172156,349596,39918,0,0,0,0,8,8,102,422,1470,5326,15852,44358,115872,274448,577782,1090776,1794934,2526958,3012776,2967268,2253702,1171984,343676,38134,0,0,0,0,0,4,8,214,1096,4420,16056,51136,149336,391796,914136,1880380,3380024,5172140,6733512,7325734,6238136,3727548,1312432,186596,0,0,0,0,8,8,104,448,1648,6272,19680,58248,160800,406928,917520,1869176,3341584,5141856,6734712,7347360,6267672,3732360,1301008,182272,1,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,1,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,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,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,2,6,13,16,12,10,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,6,13,16,12,10,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,14,28,62,98,82,54,32,10,8,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,14,28,62,98,82,54,32,10,8,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,18,28,91,192,280,360,305,200,140,52,33,4,6,0,1,0,0,0,0,0,0,0,0,0,0,0,2,4,18,28,91,192,280,360,305,200,140,52,33,4,6,0,1,0,0,0,0,0,0,0,0,0,0,0,2,4,22,30,126,260,516,856,1008,1050,814,514,310,108,72,14,12,2,0,0,0,0,0,0,0,0,0,0,2,4,22,30,126,260,516,856,1008,1050,814,514,310,108,72,14,12,2,0,0,0,0,0,0,0,0,0,0,0,6,0,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,9,21,44,81,92,67,44,23,7,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,9,21,44,81,92,67,44,23,7,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,18,28,108,238,440,620,642,506,288,172,74,38,10,12,4,0,0,0,0,0,0,0,0,0,0,0,4,8,20,60,168,288,446,566,534,436,365,180,97,44,16,2,0,0,1,0,0,0,0,0,0,0,0,0,2,5,17,50,167,357,861,1490,2105,2705,2777,2159,1511,913,453,218,77,30,14,1,0,0,0,0,0,0,0,0,2,5,17,50,167,357,861,1490,2105,2705,2777,2159,1511,913,453,218,77,30,14,1,0,0,0,0,0,0,0,0,0,2,22,32,134,408,1170,2478,4387,7034,9353,9742,8702,6400,3973,2344,1228,432,214,24,1,0,0,0,0,0,0,0,4,8,16,72,234,530,1380,2614,4488,6844,8638,9502,8810,6608,4394,2428,948,466,152,64,0,0,0,0,0,0,0,0,2,5,21,54,207,571,1678,3812,7532,13378,20150,25809,28330,25707,19868,13245,7297,3427,1477,443,39,0,0,0,0,0,0,0,2,5,21,54,207,571,1678,3812,7532,13378,20150,25809,28330,25707,19868,13245,7297,3427,1477,443,39,0,0,0,0,0,0,0,0,4,18,36,118,292,516,808,1022,992,804,548,298,148,74,28,8,4,2,0,0,0,0,0,0,0,0,0,0,4,18,36,118,292,516,808,1022,992,804,548,298,148,74,28,8,4,2,0,0,0,0,0,0,0,0,0,0,2,14,41,132,352,883,1805,3127,4730,6091,6503,5649,4157,2675,1460,691,299,113,31,5,0,0,0,0,0,0,0,0,2,14,41,132,352,883,1805,3127,4730,6091,6503,5649,4157,2675,1460,691,299,113,31,5,0,0,0,0,0,0,0,0,2,12,40,152,422,1188,2898,5922,10608,17024,23536,27462,27050,22518,16048,9778,5098,2276,804,194,20,0,0,0,0,0,0,0,2,12,40,152,422,1188,2898,5922,10608,17024,23536,27462,27050,22518,16048,9778,5098,2276,804,194,20,0,0,0,0,0,0,0,2,12,39,162,501,1507,4063,9366,18923,34377,55030,76557,91199,92628,80318,59204,37160,19615,8344,2561,431,21,0,0,0,0,0,0,2,12,39,162,501,1507,4063,9366,18923,34377,55030,76557,91199,92628,80318,59204,37160,19615,8344,2561,431,21,0,0,0,0,0,0,2,12,38,178,570,1806,5364,13486,29756,59294,105206,164552,223234,260874,261520,223816,162662,99106,49104,17978,4000,362,8,0,0,0,0,0,2,12,38,178,570,1806,5364,13486,29756,59294,105206,164552,223234,260874,261520,223816,162662,99106,49104,17978,4000,362,8,0,0,0,0,0,0,8,12,116,360,1124,2660,5996,11652,20028,29592,36598,38348,34058,25684,17278,9676,4614,1928,458,44,6,0,0,0,0,0,0,0,16,72,144,496,1348,3088,6372,12088,19588,28048,35752,38576,34428,26856,17324,9484,4432,1716,552,80,0,0,0,0,0,0,0,0,10,41,146,488,1537,4133,9925,21297,41105,70952,107887,141557,159173,154018,126911,88677,52349,25753,9503,2209,222,7,0,0,0,0,0,0,10,41,146,488,1537,4133,9925,21297,41105,70952,107887,141557,159173,154018,126911,88677,52349,25753,9503,2209,222,7,0,0,0,0,0,0,8,10,132,450,1670,5090,13620,32546,70936,137574,237138,357004,466738,525680,511432,424020,297194,174434,78472,23688,3816,260,8,0,0,0,0,0,12,70,172,668,2046,5816,14968,34604,72006,136492,233052,352586,463648,529602,515640,426294,297004,171484,77783,24452,3984,216,1,0,0,0,0,0,10,39,164,622,2159,6883,19357,48830,112008,232417,435596,726047,1061824,1353923,1491369,1402816,1117258,742750,389308,144341,31095,2885,79,0,0,0,0,0,10,39,164,622,2159,6883,19357,48830,112008,232417,435596,726047,1061824,1353923,1491369,1402816,1117258,742750,389308,144341,31095,2885,79,0,0,0,0,0,8,40,162,544,1836,5556,14714,34716,75012,147752,260778,405140,548402,644176,651060,560888,408604,248444,118524,39560,7370,544,10,0,0,0,0,0,8,40,162,544,1836,5556,14714,34716,75012,147752,260778,405140,548402,644176,651060,560888,408604,248444,118524,39560,7370,544,10,0,0,0,0,0,8,39,168,613,2161,7041,20130,51409,120869,259692,506057,881933,1354167,1820582,2124131,2124772,1805221,1285580,732877,304127,77968,9280,339,0,0,0,0,0,8,39,168,613,2161,7041,20130,51409,120869,259692,506057,881933,1354167,1820582,2124131,2124772,1805221,1285580,732877,304127,77968,9280,339,0,0,0,0,0,8,38,180,676,2466,8618,26274,71582,179756,413192,868478,1647078,2775060,4126166,5360392,6003182,5734040,4611174,3000762,1452778,456036,72682,3918,0,0,0,0,0,8,38,180,676,2466,8618,26274,71582,179756,413192,868478,1647078,2775060,4126166,5360392,6003182,5734040,4611174,3000762,1452778,456036,72682,3918,0,0,0,0,0,8,8,148,540,2224,8132,25192,70608,182160,428000,917254,1772500,3039548,4592732,6082084,6962680,6814546,5632528,3780902,1897752,625528,107552,6654,0,0,0,0,0,8,68,200,824,2768,9268,28008,75180,188364,433344,915312,1758212,3015904,4584896,6091968,6984920,6830780,5624068,3766140,1896708,630056,108164,6144,0,0,0,0,0,8,37,186,747,2811,10437,33836,98343,265720,657396,1498230,3113835,5805351,9632963,14085516,17895349,19501750,18011991,13641658,7883390,3094034,670935,54177,0,0,0,0,0,8,37,186,747,2811,10437,33836,98343,265720,657396,1498230,3113835,5805351,9632963,14085516,17895349,19501750,18011991,13641658,7883390,3094034,670935,54177,0,0,0,0,0,8,36,198,816,3136,12320,42202,129560,370972,973392,2365758,5275328,10629034,19181012,30712808,42989704,51858540,53294524,45286756,29814416,13660260,3625744,381572,0,0,0,0,0,8,36,198,816,3136,12320,42202,129560,370972,973392,2365758,5275328,10629034,19181012,30712808,42989704,51858540,53294524,45286756,29814416,13660260,3625744,381572,0,2,4,9,8,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,2,12,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,2,0,8,20,48,60,45,28,22,20,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,8,24,56,64,56,24,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,9,16,62,104,201,276,260,232,171,100,64,16,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,26,72,148,280,338,312,178,60,36,8,14,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,10,16,82,120,332,560,848,1128,1032,904,708,384,250,56,30,0,6,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,32,88,224,472,824,1272,1256,1000,632,248,200,72,56,8,8,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,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,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,10,8,34,62,47,38,30,10,14,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,22,26,70,70,26,22,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,8,20,60,168,288,446,566,534,436,365,180,97,44,16,2,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,18,28,108,238,440,620,642,506,288,172,74,38,10,12,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,8,24,64,190,476,884,1644,2550,3094,3458,3302,2585,1808,1044,468,240,60,16,8,11,4,0,0,0,0,0,0,0,0,0,0,0,2,6,34,114,266,742,1464,2436,3628,3968,3330,2510,1586,822,476,238,138,42,12,2,0,0,0,0,0,0,0,0,0,0,0,4,8,16,68,224,534,1208,2866,5162,8414,12198,14700,15864,14314,10959,7498,4321,2028,935,296,143,58,32,0,0,0,0,0,0,0,0,0,0,2,14,38,124,388,1010,2376,4876,8462,12526,15832,16288,14448,10612,6720,4004,2196,1026,514,136,48,0,0,0,0,0,0,0,0,0,0,4,8,24,80,244,674,1662,4224,8466,15862,26834,38514,49279,56054,53610,44054,31810,19186,9894,4558,1860,728,312,42,0,0,0,0,0,0,0,0,0,2,6,42,142,404,1208,3278,7498,15558,26882,39990,52154,57478,53026,42714,29726,18480,10640,5240,2048,798,174,0,0,0,0,0,0,0,0,0,4,0,24,48,174,368,496,816,1168,992,824,720,446,240,112,16,20,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,32,96,176,512,864,1152,1264,976,640,368,144,80,64,16,16,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,20,44,159,440,928,1938,3608,5732,7924,9204,9611,8578,6482,4262,2358,1038,474,166,64,36,20,2,0,0,0,0,0,0,0,0,0,0,0,22,72,236,724,1564,3284,5744,8320,10274,10274,8374,5970,3710,2122,1238,586,254,88,24,0,0,0,0,0,0,0,0,0,0,2,0,16,44,166,492,1244,2968,6346,12480,21696,32776,44469,52904,54984,49040,37598,24832,14176,6796,3036,1260,476,152,30,0,0,0,0,0,0,0,0,0,0,16,80,268,852,2308,5556,11504,21192,34064,46788,55224,55728,47768,35468,23440,14136,7712,3516,1372,428,68,0,0,0,0,0,0,0,0,2,0,16,40,169,580,1506,3942,9604,21034,41480,73284,116428,165142,208594,229630,219398,181526,129858,79418,42216,19504,7906,2606,600,70,0,0,0,0,0,0,0,0,0,16,84,288,1002,3036,8100,18880,39428,73190,119098,170786,213846,231342,216294,175946,125946,79880,44420,21100,8178,2312,380,0,0,0,0,0,0,0,2,0,16,40,174,636,1790,5012,13086,31384,68260,133384,236128,377816,543160,690280,770350,749112,632212,459920,288342,154604,70506,25924,6858,1008,56,0,0,0,0,0,0,0,0,16,88,312,1148,3788,10912,27664,63688,130984,237600,385424,554560,700208,771200,739520,619496,454952,291208,159800,73124,25860,6096,592,0,0,0,0,0,0,0,0,20,32,126,424,1248,2884,6598,13248,24174,39800,57483,72180,79526,76800,64936,46028,28462,15360,7061,2996,1134,408,103,4,0,0,0,0,0,0,0,0,0,12,72,352,816,2308,5736,12516,23820,39420,58720,75480,81984,76984,62052,43796,27628,15936,8120,3280,1208,292,8,0,0,0,0,0,0,0,0,0,16,36,136,532,1506,4016,9800,22806,47596,89374,154829,238628,328812,402564,430241,399180,322654,224416,134042,69266,31182,11726,3217,528,42,0,0,0,0,0,0,0,0,6,60,276,1024,2994,8168,19976,44432,88308,155068,244110,339012,408940,429118,392660,313502,221238,136818,72698,32762,11602,2744,264,0,0,0,0,0,0,0,0,16,32,126,504,1772,4920,13206,33452,76968,163012,313332,549702,870072,1231278,1551284,1717704,1661224,1397628,1012862,629424,333008,146320,49393,10690,1112,58,1,0,0,0,0,0,0,6,68,388,1140,3782,11328,29980,72148,156666,310134,550996,880748,1253192,1567770,1715622,1641972,1376876,1007406,635914,342134,150532,48028,9152,728,10,0,0,0,0,0,0,16,32,134,644,1996,6106,17396,46834,115740,262058,548137,1046224,1825392,2884616,4084096,5121184,5657276,5459156,4561416,3274996,2001836,1017142,399116,106598,15600,1002,22,0,0,0,0,0,0,6,60,304,1320,4408,14152,40400,105300,250606,536242,1046200,1844188,2920632,4123928,5139308,5626648,5409846,4534500,3280544,2022868,1030568,400648,103132,13468,638,6,0,0,0,0,0,12,40,130,536,1828,5192,13376,34448,81224,172672,338760,607112,991328,1452504,1892576,2172840,2186928,1915512,1449388,942360,522172,241496,85900,20592,2636,136,2,0,0,0,0,0,0,0,64,288,1136,3784,11232,29792,73968,166016,332848,610512,1007872,1476288,1910976,2173264,2163240,1890648,1441408,949760,533104,246168,85520,18880,1832,40,0,0,0,0,0,0,12,36,128,604,2048,6266,17628,48246,122742,285012,613173,1214404,2209458,3652980,5439977,7208484,8444510,8676256,7751882,5969428,3921418,2156086,933821,287184,51902,4286,114,0,0,0,0,0,0,0,64,296,1282,4530,14516,41506,111008,270874,595864,1207510,2225018,3696348,5494742,7244608,8421578,8614742,7702706,5963198,3947540,2178894,940560,283494,47894,3272,56,0,0,0,0,0,12,36,128,640,2298,7440,22080,63852,173304,431048,995132,2122552,4185388,7561784,12405596,18257392,23924036,27669308,27982476,24489792,18347906,11546896,5807172,2134508,491304,55584,2146,0,0,0,0,0,0,0,64,308,1424,5312,18076,54640,155824,407308,961408,2097416,4188832,7618056,12508172,18368096,23938376,27571192,27854572,24428308,18380504,11605928,5839600,2133232,479800,51036,1700,0,0,0,0,0,12,32,126,568,2248,7292,21966,64180,175154,443084,1031383,2243132,4483178,8224388,13718196,20593708,27545232,32596188,33789181,30339284,23354170,15119192,7872133,3032072,743226,91016,4005,0,0,0,0,0,0,0,64,408,1448,5432,18680,56448,161060,418784,1003208,2205000,4471540,8264484,13828484,20718056,27606216,32513744,33630264,30247496,23364740,15199232,7923848,3026816,729156,85960,3152,0,0,0,0,0,12,32,126,708,2514,8660,27440,83588,241378,643376,1603173,3704584,7962384,15797252,28728420,47320372,69965976,92021224,106608620,107555452,93399126,68619648,40991724,18471968,5549554,896608,53356,0,0,0,0,0,0,0,64,316,1578,6144,22236,71284,216132,604886,1538722,3636408,7921344,15847680,28892632,47594596,70136280,91939632,106329008,107292684,93365830,68745472,41118700,18509048,5520884,875322,49918,0,0,0,0,0,12,32,126,744,2768,9992,33048,105304,320624,905488,2397354,5893440,13546712,28877120,56791376,101851488,165026892,239320864,307457538,345754776,336159704,278022808,188849776,98536264,35417192,7240336,578886,0,0,0,0,0,0,0,64,328,1728,7032,26744,89504,286040,848944,2292960,5765184,13425984,28878688,56990720,102354480,165495456,239397584,307035424,345113208,335889680,278184520,189161336,98703280,35375160,7175904,564752}; int h; int w; int b1[8][8]; int b2[8][8]; int xx[9][9][9][2][33]; void solve() { int p1 = 0; int p2 = 0; for (int r=0; r<h; ++r) for (int c=0; c<w; ++c) if (b1[r][c] == 1) p1 += r + c; for (int r=0; r<h; ++r) for (int c=0; c<w; ++c) if (b2[r][c] == 1) p2 += r + c; if (p1 % 2 != p2 % 2) { printf("0.0\n"); return; } int kr = 0; int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; int k = 0; for (int r=0; r<h; ++r) for (int c=0; c<w; ++c) if (b2[r][c] == 1) { ++k; for (int q=0; q<4; ++q) { int rr = r + dr[q]; int cc = c + dc[q]; if (rr < 0 || cc < 0 || rr >= h || cc >= w) continue; if (b2[rr][cc] == 0) ++kr; } } double res = kr * 2; long long sum = 0; for (int p=0; p<2; ++p) for (int m=1; m<=4*k; ++m) sum += 1LL * m * xx[k][h][w][p][m]; fprintf(stderr, "k: %d, sum: %lld\n", k, sum); res /= sum; printf("%.17lf\n", res); } void init() { int off = 0; for (int k=1; k<=8; ++k) for (int h=1; h<=8; ++h) for (int w=h; w<=8; ++w) { if (k >= h*w) continue; for (int p=0; p<2; ++p) for (int m=1; m<=4*k; ++m) { int xxxx = xxx[off++]; xx[k][h][w][p][m] = xx[k][w][h][p][m] = xxxx; } } } int main() { init(); scanf("%d%d", &h, &w); for (int r=0; r<h; ++r) { char s[64]; scanf("%s", s); for (int c=0; c<w; ++c) { b1[r][c] = s[c] == 'O' ? 1 : 0; } } for (int r=0; r<h; ++r) { char s[64]; scanf("%s", s); for (int c=0; c<w; ++c) { b2[r][c] = s[c] == 'O' ? 1 : 0; } } solve(); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #include <cstdio> using namespace std; int xxx[] = {1,0,0,0,1,0,0,0,2,0,0,0,0,1,0,0,1,1,0,0,1,1,0,0,2,1,0,0,0,2,0,0,1,2,0,0,1,2,0,0,2,2,0,0,0,3,0,0,1,3,0,0,1,3,0,0,0,2,0,0,0,2,0,0,0,2,1,0,0,2,1,0,0,2,2,0,0,2,2,0,0,2,3,0,0,2,3,0,0,2,4,0,0,2,4,0,0,2,5,0,0,2,5,0,0,2,6,0,0,2,6,0,0,4,0,1,0,0,4,0,0,2,3,1,0,2,3,1,0,4,2,2,0,0,6,1,0,2,5,2,0,2,5,2,0,4,4,3,0,0,8,2,0,2,7,3,0,2,7,3,0,2,4,2,0,2,4,2,0,2,5,3,0,2,5,3,0,2,6,4,0,2,6,4,0,2,7,5,0,2,7,5,0,2,8,6,0,2,8,6,0,4,4,5,0,0,8,4,0,2,7,6,0,2,7,6,0,4,6,8,0,0,10,7,0,2,9,9,0,2,9,9,0,2,8,8,0,2,8,8,0,2,9,10,0,2,9,10,0,2,10,12,0,2,10,12,0,4,8,13,0,0,12,12,0,2,11,15,0,2,11,15,0,2,12,18,0,2,12,18,0,1,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,2,2,0,0,0,0,0,0,0,1,2,1,0,0,0,0,2,2,2,0,0,0,0,0,0,0,4,2,0,0,0,0,2,4,2,1,0,0,0,0,0,1,4,4,0,0,0,0,2,4,4,2,0,0,0,0,0,0,6,6,0,0,0,0,2,6,4,4,0,0,0,0,0,0,0,2,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,2,4,0,0,0,0,2,4,3,0,0,0,0,0,0,0,2,8,2,0,0,0,2,4,6,4,0,0,0,0,0,0,2,12,6,0,0,0,2,4,9,8,2,0,0,0,0,0,2,16,12,0,0,0,2,4,12,12,6,0,0,0,0,0,2,20,20,0,0,0,2,4,15,16,12,0,0,0,0,0,2,24,30,0,0,0,2,4,18,20,20,0,0,0,0,0,6,0,10,0,0,0,0,8,0,12,0,0,0,0,0,0,2,12,10,6,0,0,0,8,6,10,12,0,0,0,0,0,6,8,24,10,1,0,0,8,4,24,14,6,0,0,0,0,2,20,28,20,2,0,0,8,10,22,30,10,1,0,0,0,6,16,46,28,4,0,0,8,8,36,36,20,2,0,0,0,2,28,54,42,6,0,0,8,14,34,56,28,4,0,0,0,2,16,20,16,2,0,0,8,8,16,24,8,0,0,0,0,2,20,32,30,6,0,0,8,10,22,38,20,2,0,0,0,2,24,46,48,12,0,0,8,12,28,54,36,6,0,0,0,2,28,62,70,20,0,0,8,14,34,72,56,12,0,0,0,2,32,80,96,30,0,0,8,16,40,92,80,20,0,0,0,6,16,54,52,16,0,0,8,8,36,52,44,8,0,0,0,2,28,66,84,30,0,0,8,14,34,80,70,19,0,0,0,6,24,92,118,49,0,0,8,12,48,98,106,34,0,0,0,2,36,108,162,72,0,0,8,18,46,130,144,54,0,0,0,2,32,88,128,56,0,0,8,16,40,108,112,40,0,0,0,2,36,112,180,90,0,0,8,18,46,138,162,69,0,0,0,2,40,138,240,132,0,0,8,20,52,170,220,106,0,0,0,6,32,146,248,144,0,0,8,16,60,168,232,116,0,0,0,2,44,170,330,210,0,0,8,22,58,212,308,176,0,0,0,2,48,204,432,306,0,0,8,24,64,256,408,264,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,2,1,0,0,0,0,0,0,0,0,2,2,2,0,0,0,0,0,0,0,0,0,1,2,4,2,1,0,0,0,0,0,0,0,1,2,4,2,1,0,0,0,0,0,0,0,0,2,4,6,4,0,0,0,0,0,0,0,2,3,8,3,2,1,0,0,0,0,0,0,1,3,8,8,6,2,0,0,0,0,0,0,1,3,8,8,6,2,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,3,4,2,0,1,0,0,0,0,0,0,0,3,4,2,0,1,0,0,0,0,0,0,0,2,6,8,6,4,2,0,0,0,0,0,0,2,6,8,6,4,2,0,0,0,0,0,0,2,6,13,16,12,10,1,0,0,0,0,0,2,6,13,16,12,10,1,0,0,0,0,0,2,6,18,26,26,26,6,0,0,0,0,0,2,6,18,26,26,26,6,0,0,0,0,0,2,6,23,36,46,50,19,0,0,0,0,0,2,6,23,36,46,50,19,0,0,0,0,0,2,6,28,46,72,82,44,0,0,0,0,0,2,6,28,46,72,82,44,0,0,0,0,0,0,4,0,26,0,10,0,0,0,0,0,0,4,0,24,0,12,0,4,0,0,0,0,0,1,4,14,23,26,25,14,3,0,0,0,0,1,4,14,23,26,25,14,3,0,0,0,0,0,4,2,46,42,66,50,12,2,0,0,0,2,4,28,29,54,47,44,23,0,0,0,0,1,4,16,52,74,102,102,50,7,0,0,0,1,4,16,52,74,102,102,50,7,0,0,0,0,4,4,67,98,177,192,95,22,1,0,0,2,4,30,66,110,146,174,118,20,0,0,0,1,4,18,81,138,235,294,193,46,2,0,0,1,4,18,81,138,235,294,193,46,2,0,0,0,6,16,32,56,72,64,30,4,0,0,0,0,6,16,32,56,72,64,30,4,0,0,0,0,6,17,46,87,132,155,100,26,1,0,0,0,6,17,46,87,132,155,100,26,1,0,0,0,6,18,60,122,208,286,226,80,6,0,0,0,6,18,60,122,208,286,226,80,6,0,0,0,6,19,74,161,300,461,420,178,19,0,0,0,6,19,74,161,300,461,420,178,19,0,0,0,6,20,88,204,408,684,694,332,44,0,0,0,6,20,88,204,408,684,694,332,44,0,0,0,4,4,64,120,220,348,270,100,14,0,0,0,8,32,56,132,224,300,276,120,8,0,0,0,6,19,74,169,330,551,556,283,42,0,0,0,6,19,74,169,330,551,556,283,42,0,0,0,4,6,84,210,444,886,966,550,114,0,0,0,8,34,92,222,468,794,968,594,101,0,0,0,6,21,102,267,600,1195,1524,1004,221,0,0,0,6,21,102,267,600,1195,1524,1004,221,0,0,0,6,20,88,220,472,892,1066,668,138,0,0,0,6,20,88,220,472,892,1066,668,138,0,0,0,6,21,102,275,634,1313,1780,1283,326,0,0,0,6,21,102,275,634,1313,1780,1283,326,0,0,0,6,22,116,334,816,1818,2722,2176,638,0,0,0,6,22,116,334,816,1818,2722,2176,638,0,0,0,4,8,104,332,796,1968,2898,2340,750,0,0,0,8,36,128,344,872,1800,2880,2432,724,0,0,0,6,23,130,405,1056,2557,4324,3956,1403,0,0,0,6,23,130,405,1056,2557,4324,3956,1403,0,0,0,6,24,144,480,1320,3416,6366,6452,2624,0,0,0,6,24,144,480,1320,3416,6366,6452,2624,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,2,0,0,0,0,0,0,0,0,0,0,0,0,2,3,8,3,2,1,0,0,0,0,0,0,0,0,0,0,0,2,4,6,4,0,0,0,0,0,0,0,0,0,0,0,2,6,10,10,6,2,2,0,0,0,0,0,0,0,0,0,0,0,8,8,12,4,0,0,0,0,0,0,0,0,0,0,0,2,4,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,0,0,0,0,0,0,0,0,0,0,0,0,2,0,8,16,8,0,2,0,2,0,0,0,0,0,0,0,0,0,0,8,12,8,4,0,0,0,0,0,0,0,0,0,2,0,7,20,30,24,11,4,8,4,0,0,0,0,0,0,0,0,0,8,18,32,26,12,4,0,0,0,0,0,0,0,2,0,8,20,48,60,45,28,22,20,2,0,0,0,0,0,0,0,0,8,24,56,64,56,24,8,0,0,0,0,0,0,2,0,9,20,66,96,104,84,58,60,12,0,0,0,0,0,0,0,0,8,30,80,118,132,78,40,4,0,0,0,0,0,2,0,10,20,84,132,188,172,134,140,42,0,0,0,0,0,0,0,0,8,36,104,188,240,184,112,24,0,0,0,0,0,0,0,12,0,36,0,13,0,4,0,1,0,0,0,0,0,0,0,0,12,0,36,0,12,0,0,0,0,0,0,0,0,0,0,10,8,34,62,47,38,30,10,14,2,0,0,0,0,0,0,0,2,22,26,70,70,26,22,2,0,0,0,0,0,0,0,8,8,48,66,151,136,107,94,42,32,1,0,0,0,0,0,0,6,20,62,92,178,158,86,66,4,0,0,0,0,0,0,8,12,50,124,204,286,302,246,202,92,22,0,0,0,0,0,0,2,26,56,178,316,348,304,198,82,2,0,0,0,0,0,8,8,60,140,309,490,579,584,462,298,73,4,0,0,0,0,0,6,24,92,224,496,654,628,558,242,46,0,0,0,0,0,8,12,62,198,394,728,980,1060,1032,644,210,18,0,0,0,0,0,2,30,86,302,738,1058,1186,1078,640,152,8,0,0,0,0,8,8,44,96,136,176,176,128,100,40,12,0,0,0,0,0,0,0,24,48,120,192,216,176,88,32,0,0,0,0,0,0,6,12,52,120,229,378,466,446,410,234,82,10,0,0,0,0,0,0,24,66,182,350,514,558,426,226,54,0,0,0,0,0,6,12,56,156,332,616,896,1032,1082,764,332,60,2,0,0,0,0,0,24,84,248,552,940,1192,1140,784,288,28,0,0,0,0,6,12,60,192,443,906,1478,1922,2246,1850,942,214,12,0,0,0,0,0,24,102,318,798,1506,2130,2358,1914,886,152,4,0,0,0,6,12,64,228,562,1248,2224,3168,4038,3732,2144,572,42,0,0,0,0,0,24,120,392,1088,2224,3424,4216,3856,2080,472,24,0,0,0,4,16,52,128,365,664,970,1292,1259,1000,506,96,6,0,0,0,0,0,32,100,224,576,1060,1308,1468,1040,412,72,0,0,0,0,4,16,64,180,452,998,1740,2406,3004,2756,1620,476,39,0,0,0,0,0,24,102,330,836,1694,2648,3176,2864,1572,382,22,0,0,0,4,16,60,200,591,1390,2606,4246,5563,5910,4090,1410,162,0,0,0,0,0,32,136,396,1138,2612,4226,6032,6178,3954,1294,114,0,0,0,4,16,72,252,710,1816,3812,6332,9516,11024,8380,3396,460,0,0,0,0,0,24,138,494,1506,3594,6650,9870,11386,8402,3156,380,0,0,0,4,16,68,216,584,1416,2816,4424,6264,6792,4844,1856,229,0,0,0,0,0,24,120,416,1168,2656,4704,6544,7056,4840,1672,176,0,0,0,4,16,72,252,724,1890,4140,7134,11140,13636,11174,5080,808,0,0,0,0,0,24,138,506,1548,3838,7436,11520,14100,11270,4786,694,0,0,0,4,16,76,288,872,2420,5724,10612,17916,24092,21980,11292,2136,0,0,0,0,0,24,156,600,1976,5252,10920,18388,24800,22232,10868,1936,0,0,0,4,16,68,272,877,2484,5786,11376,18851,26036,24618,13056,2632,0,0,0,0,0,32,172,608,1972,5508,11112,19668,26948,24692,12696,2392,0,0,0,4,16,80,324,1042,3084,7980,16068,29688,44556,46448,27956,6588,0,0,0,0,0,24,174,710,2498,7210,16334,30218,45682,47086,27316,6204,0,0,0,4,16,84,360,1220,3808,10592,22800,45288,74096,85732,57960,15976,0,0,0,0,0,24,192,824,3072,9480,22992,45816,75712,86912,57072,15344,1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,8,8,6,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,8,8,6,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,6,8,6,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,6,8,6,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,11,24,32,28,16,4,4,0,1,0,0,0,0,0,0,0,0,0,2,4,11,24,32,28,16,4,4,0,1,0,0,0,0,0,0,0,0,0,2,4,14,28,62,98,82,54,32,10,8,2,0,0,0,0,0,0,0,0,2,4,14,28,62,98,82,54,32,10,8,2,0,0,0,0,0,0,0,0,2,4,18,30,91,176,208,206,133,76,38,18,1,0,0,0,0,0,0,0,2,4,18,30,91,176,208,206,133,76,38,18,1,0,0,0,0,0,0,0,2,4,22,32,122,254,392,472,376,278,138,82,10,0,0,0,0,0,0,0,2,4,22,32,122,254,392,472,376,278,138,82,10,0,0,0,0,0,0,0,0,12,0,36,0,13,0,4,0,1,0,0,0,0,0,0,0,0,0,0,0,0,12,0,36,0,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,9,21,44,81,92,67,44,23,7,4,2,0,0,0,0,0,0,0,0,2,9,21,44,81,92,67,44,23,7,4,2,0,0,0,0,0,0,0,0,4,10,30,74,162,220,290,272,190,170,46,40,4,0,0,0,0,0,0,0,0,6,8,66,106,232,318,324,244,82,74,16,15,0,0,0,0,0,0,0,2,7,21,88,181,398,644,810,826,637,371,206,83,10,0,0,0,0,0,0,2,7,21,88,181,398,644,810,826,637,371,206,83,10,0,0,0,0,0,0,4,8,34,114,276,640,1083,1540,1885,1910,1321,902,404,70,6,0,0,0,0,0,0,6,8,92,196,536,1090,1696,2072,1806,1346,796,400,108,0,0,0,0,0,0,2,7,21,118,291,794,1643,2745,3820,4125,3432,2478,1348,394,34,0,0,0,0,0,2,7,21,118,291,794,1643,2745,3820,4125,3432,2478,1348,394,34,0,0,0,0,0,0,8,24,60,130,260,402,436,370,256,144,68,22,4,0,0,0,0,0,0,0,8,24,60,130,260,402,436,370,256,144,68,22,4,0,0,0,0,0,0,0,7,22,78,184,424,812,1219,1478,1394,1060,663,310,91,10,0,0,0,0,0,0,7,22,78,184,424,812,1219,1478,1394,1060,663,310,91,10,0,0,0,0,0,0,6,24,90,230,616,1334,2342,3404,3992,3780,2892,1722,682,132,6,0,0,0,0,0,6,24,90,230,616,1334,2342,3404,3992,3780,2892,1722,682,132,6,0,0,0,0,0,6,24,99,284,822,1957,3847,6309,8531,9344,8342,5896,2857,755,66,1,0,0,0,0,6,24,99,284,822,1957,3847,6309,8531,9344,8342,5896,2857,755,66,1,0,0,0,0,6,24,108,338,1040,2692,5758,10352,15546,18940,18980,15226,8560,2762,346,10,0,0,0,0,6,24,108,338,1040,2692,5758,10352,15546,18940,18980,15226,8560,2762,346,10,0,0,0,0,12,24,104,304,668,1398,2560,3790,4860,4830,4032,2643,1100,252,20,1,0,0,0,0,0,16,80,184,572,1344,2532,4108,4936,4948,3876,2472,1164,284,16,0,0,0,0,0,5,22,102,294,838,2057,4292,7637,11235,13406,13052,10286,5786,1961,271,9,0,0,0,0,5,22,102,294,838,2057,4292,7637,11235,13406,13052,10286,5786,1961,271,9,0,0,0,0,10,28,124,428,1172,2968,6622,12544,20814,28212,31702,29032,19188,7898,1540,102,0,0,0,0,0,16,94,276,968,2729,6380,12943,21300,28688,31616,28437,19020,8115,1594,72,0,0,0,0,5,22,116,410,1314,3756,9198,19447,35098,52076,64089,64794,48799,23692,5748,440,0,0,0,0,5,22,116,410,1314,3756,9198,19447,35098,52076,64089,64794,48799,23692,5748,440,0,0,0,0,4,24,112,346,1076,2922,6744,13520,23000,32032,36756,34558,24096,10798,2356,152,0,0,0,0,4,24,112,346,1076,2922,6744,13520,23000,32032,36756,34558,24096,10798,2356,152,0,0,0,0,4,24,119,406,1328,3897,9742,21297,40124,62468,80743,86250,69876,37467,10590,999,0,0,0,0,4,24,119,406,1328,3897,9742,21297,40124,62468,80743,86250,69876,37467,10590,999,0,0,0,0,4,24,126,466,1592,4992,13312,31166,63546,107816,152656,179986,163290,99714,33436,4026,0,0,0,0,4,24,126,466,1592,4992,13312,31166,63546,107816,152656,179986,163290,99714,33436,4026,0,0,0,0,8,32,144,560,1756,5328,13976,32288,66124,114754,165872,200823,187496,117614,41336,5469,0,0,0,0,0,16,108,376,1444,4792,13248,32228,67412,115948,166904,199712,185664,118308,41872,5272,0,0,0,0,4,24,133,530,1884,6347,18138,45844,102139,191428,300644,397172,411609,294071,120722,19219,0,0,0,0,4,24,133,530,1884,6347,18138,45844,102139,191428,300644,397172,411609,294071,120722,19219,0,0,0,0,4,24,140,594,2188,7830,23704,63718,152244,308648,525684,759342,871660,700828,331668,63980,0,0,0,0,4,24,140,594,2188,7830,23704,63718,152244,308648,525684,759342,871660,700828,331668,63980,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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,6,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,6,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,2,8,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,6,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,18,32,26,12,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,7,20,30,24,11,4,8,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,20,56,90,120,96,40,16,0,4,0,2,0,0,0,0,0,0,0,0,0,2,0,8,16,46,80,96,80,58,40,32,8,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,26,72,148,280,338,312,178,60,36,8,14,4,0,0,0,0,0,0,0,0,2,0,9,16,62,104,201,276,260,232,171,100,64,16,6,0,0,0,0,0,0,0,0,0,0,0,0,8,32,88,218,448,710,912,710,448,218,88,62,32,2,0,0,0,0,0,0,0,2,0,10,16,80,124,316,500,652,748,596,476,300,148,52,12,0,0,0,0,0,0,0,0,0,0,4,0,26,0,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,24,0,12,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,48,76,94,124,68,16,20,0,0,0,2,0,0,0,0,0,0,0,0,0,2,0,12,30,72,84,84,72,54,32,12,18,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,9,44,112,230,407,512,481,380,145,104,26,18,7,6,0,0,0,0,0,0,0,2,0,4,30,92,126,290,418,436,420,296,220,92,80,10,4,0,0,0,0,0,0,0,0,0,0,4,0,44,142,324,736,1254,1684,1844,1440,880,484,236,96,62,10,0,0,0,0,0,0,2,0,4,38,96,196,492,836,1184,1554,1580,1298,1012,628,254,126,24,0,0,0,0,0,0,0,0,0,4,9,44,176,466,1135,2222,3562,4716,4954,4270,2739,1510,802,332,127,4,0,0,0,0,0,2,0,4,28,110,242,616,1376,2276,3480,4478,4566,3940,3074,1758,842,368,32,0,0,0,0,0,0,0,0,4,0,52,186,528,1600,3380,6310,9746,11778,11770,9616,6260,3516,1792,568,82,0,0,0,0,0,2,0,4,38,112,304,840,1968,3690,6274,9094,11038,11408,9816,6684,3876,1768,480,12,0,0,0,0,0,0,0,0,4,32,102,272,392,688,940,688,392,272,104,48,24,16,2,0,0,0,0,0,0,0,0,16,16,64,184,320,488,664,664,608,472,280,168,64,24,0,0,0,0,0,0,0,0,0,0,0,4,24,132,366,714,1576,2634,3380,3612,3004,1852,1098,566,252,86,20,0,0,0,0,0,0,0,12,16,76,220,492,972,1650,2486,3176,3172,2804,2172,1272,632,238,50,0,0,0,0,0,0,0,0,0,4,20,150,476,1096,2596,5110,8300,11060,11980,10462,7668,4600,2412,972,252,30,0,0,0,0,0,0,12,14,76,272,656,1480,2960,5202,8008,10288,11256,10454,8032,5112,2536,882,168,0,0,0,0,0,0,0,0,4,20,162,572,1526,3874,8446,15646,24094,30918,32706,28748,20766,12626,5914,1858,294,14,0,0,0,0,0,12,12,82,314,802,2068,4576,8890,15482,23106,29438,31946,29010,21852,13216,5926,1658,162,0,0,0,0,0,0,0,4,20,174,668,1982,5388,12718,25876,44262,63820,76914,77380,64330,44596,24016,8812,1726,128,2,0,0,0,0,12,12,84,348,968,2708,6444,13664,26080,43172,61428,75008,77112,65980,45980,24400,8524,1396,56,0,0,0,0,0,0,4,40,138,452,1290,2684,5314,9496,13310,15604,14854,11384,7400,4048,1796,556,66,4,0,0,0,0,0,8,16,64,264,660,1372,3180,5852,9160,12768,14612,14272,11928,7928,4396,1772,384,24,0,0,0,0,0,0,0,4,12,172,564,1542,4162,9248,18250,30872,43642,51012,49584,39712,26774,14422,5426,1162,98,2,0,0,0,0,8,14,88,288,822,2170,4806,9981,18810,29980,41386,49561,49420,41018,27924,14693,5208,898,40,0,0,0,0,0,0,4,32,174,660,2232,5762,14074,30716,57199,91894,125336,141112,133008,104176,65431,30096,8313,980,41,0,0,0,0,8,12,74,332,966,2626,6920,15488,31792,57374,89672,120840,139634,133880,106718,67510,29680,7594,788,12,0,0,0,0,0,4,12,192,754,2516,7694,20056,46860,95450,168112,251990,319506,337616,298654,213862,112116,37066,5866,294,0,0,0,0,8,12,96,352,1132,3558,9218,22234,49226,95908,164264,246440,314752,338510,302994,217044,112704,35918,5180,210,0,0,0,0,0,4,8,182,680,2056,5872,14480,32264,62080,102608,143272,167976,163560,133376,88088,42344,12780,1784,74,0,0,0,0,8,12,88,328,992,2872,6984,15992,33864,62032,99344,139328,165456,165000,136264,89752,42496,12036,1416,40,0,0,0,0,0,4,8,190,780,2590,7882,20980,50690,106982,196822,310010,414828,463936,435502,333964,191014,71572,13618,856,0,0,0,0,8,10,94,362,1142,3626,9518,23431,53694,108510,193166,303353,408040,463822,440340,338337,192642,70282,12500,681,0,0,0,0,0,4,8,198,880,3146,10156,28756,74104,168162,335132,577608,853504,1059814,1108836,953522,621040,271088,63516,5270,0,0,0,0,8,10,96,388,1312,4428,12332,32350,78952,172008,331724,568350,840656,1055932,1115196,961902,625868,269484,61032,4740,0,0,0,0,0,4,24,202,888,3406,10316,29586,76372,175264,353252,624224,937360,1191972,1275184,1120668,755260,344048,85160,7706,0,0,0,0,8,8,84,392,1292,4216,12504,32804,81356,180004,353864,611784,925676,1184080,1278568,1134728,760264,341500,82844,6944,0,0,0,0,0,4,8,206,988,3772,12960,39136,108034,265718,578770,1102194,1819200,2541024,3006876,2952278,2239742,1172156,349596,39918,0,0,0,0,8,8,102,422,1470,5326,15852,44358,115872,274448,577782,1090776,1794934,2526958,3012776,2967268,2253702,1171984,343676,38134,0,0,0,0,0,4,8,214,1096,4420,16056,51136,149336,391796,914136,1880380,3380024,5172140,6733512,7325734,6238136,3727548,1312432,186596,0,0,0,0,8,8,104,448,1648,6272,19680,58248,160800,406928,917520,1869176,3341584,5141856,6734712,7347360,6267672,3732360,1301008,182272,1,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,1,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,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,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,2,6,13,16,12,10,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,6,13,16,12,10,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,14,28,62,98,82,54,32,10,8,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,14,28,62,98,82,54,32,10,8,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,18,28,91,192,280,360,305,200,140,52,33,4,6,0,1,0,0,0,0,0,0,0,0,0,0,0,2,4,18,28,91,192,280,360,305,200,140,52,33,4,6,0,1,0,0,0,0,0,0,0,0,0,0,0,2,4,22,30,126,260,516,856,1008,1050,814,514,310,108,72,14,12,2,0,0,0,0,0,0,0,0,0,0,2,4,22,30,126,260,516,856,1008,1050,814,514,310,108,72,14,12,2,0,0,0,0,0,0,0,0,0,0,0,6,0,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,9,21,44,81,92,67,44,23,7,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,9,21,44,81,92,67,44,23,7,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,18,28,108,238,440,620,642,506,288,172,74,38,10,12,4,0,0,0,0,0,0,0,0,0,0,0,4,8,20,60,168,288,446,566,534,436,365,180,97,44,16,2,0,0,1,0,0,0,0,0,0,0,0,0,2,5,17,50,167,357,861,1490,2105,2705,2777,2159,1511,913,453,218,77,30,14,1,0,0,0,0,0,0,0,0,2,5,17,50,167,357,861,1490,2105,2705,2777,2159,1511,913,453,218,77,30,14,1,0,0,0,0,0,0,0,0,0,2,22,32,134,408,1170,2478,4387,7034,9353,9742,8702,6400,3973,2344,1228,432,214,24,1,0,0,0,0,0,0,0,4,8,16,72,234,530,1380,2614,4488,6844,8638,9502,8810,6608,4394,2428,948,466,152,64,0,0,0,0,0,0,0,0,2,5,21,54,207,571,1678,3812,7532,13378,20150,25809,28330,25707,19868,13245,7297,3427,1477,443,39,0,0,0,0,0,0,0,2,5,21,54,207,571,1678,3812,7532,13378,20150,25809,28330,25707,19868,13245,7297,3427,1477,443,39,0,0,0,0,0,0,0,0,4,18,36,118,292,516,808,1022,992,804,548,298,148,74,28,8,4,2,0,0,0,0,0,0,0,0,0,0,4,18,36,118,292,516,808,1022,992,804,548,298,148,74,28,8,4,2,0,0,0,0,0,0,0,0,0,0,2,14,41,132,352,883,1805,3127,4730,6091,6503,5649,4157,2675,1460,691,299,113,31,5,0,0,0,0,0,0,0,0,2,14,41,132,352,883,1805,3127,4730,6091,6503,5649,4157,2675,1460,691,299,113,31,5,0,0,0,0,0,0,0,0,2,12,40,152,422,1188,2898,5922,10608,17024,23536,27462,27050,22518,16048,9778,5098,2276,804,194,20,0,0,0,0,0,0,0,2,12,40,152,422,1188,2898,5922,10608,17024,23536,27462,27050,22518,16048,9778,5098,2276,804,194,20,0,0,0,0,0,0,0,2,12,39,162,501,1507,4063,9366,18923,34377,55030,76557,91199,92628,80318,59204,37160,19615,8344,2561,431,21,0,0,0,0,0,0,2,12,39,162,501,1507,4063,9366,18923,34377,55030,76557,91199,92628,80318,59204,37160,19615,8344,2561,431,21,0,0,0,0,0,0,2,12,38,178,570,1806,5364,13486,29756,59294,105206,164552,223234,260874,261520,223816,162662,99106,49104,17978,4000,362,8,0,0,0,0,0,2,12,38,178,570,1806,5364,13486,29756,59294,105206,164552,223234,260874,261520,223816,162662,99106,49104,17978,4000,362,8,0,0,0,0,0,0,8,12,116,360,1124,2660,5996,11652,20028,29592,36598,38348,34058,25684,17278,9676,4614,1928,458,44,6,0,0,0,0,0,0,0,16,72,144,496,1348,3088,6372,12088,19588,28048,35752,38576,34428,26856,17324,9484,4432,1716,552,80,0,0,0,0,0,0,0,0,10,41,146,488,1537,4133,9925,21297,41105,70952,107887,141557,159173,154018,126911,88677,52349,25753,9503,2209,222,7,0,0,0,0,0,0,10,41,146,488,1537,4133,9925,21297,41105,70952,107887,141557,159173,154018,126911,88677,52349,25753,9503,2209,222,7,0,0,0,0,0,0,8,10,132,450,1670,5090,13620,32546,70936,137574,237138,357004,466738,525680,511432,424020,297194,174434,78472,23688,3816,260,8,0,0,0,0,0,12,70,172,668,2046,5816,14968,34604,72006,136492,233052,352586,463648,529602,515640,426294,297004,171484,77783,24452,3984,216,1,0,0,0,0,0,10,39,164,622,2159,6883,19357,48830,112008,232417,435596,726047,1061824,1353923,1491369,1402816,1117258,742750,389308,144341,31095,2885,79,0,0,0,0,0,10,39,164,622,2159,6883,19357,48830,112008,232417,435596,726047,1061824,1353923,1491369,1402816,1117258,742750,389308,144341,31095,2885,79,0,0,0,0,0,8,40,162,544,1836,5556,14714,34716,75012,147752,260778,405140,548402,644176,651060,560888,408604,248444,118524,39560,7370,544,10,0,0,0,0,0,8,40,162,544,1836,5556,14714,34716,75012,147752,260778,405140,548402,644176,651060,560888,408604,248444,118524,39560,7370,544,10,0,0,0,0,0,8,39,168,613,2161,7041,20130,51409,120869,259692,506057,881933,1354167,1820582,2124131,2124772,1805221,1285580,732877,304127,77968,9280,339,0,0,0,0,0,8,39,168,613,2161,7041,20130,51409,120869,259692,506057,881933,1354167,1820582,2124131,2124772,1805221,1285580,732877,304127,77968,9280,339,0,0,0,0,0,8,38,180,676,2466,8618,26274,71582,179756,413192,868478,1647078,2775060,4126166,5360392,6003182,5734040,4611174,3000762,1452778,456036,72682,3918,0,0,0,0,0,8,38,180,676,2466,8618,26274,71582,179756,413192,868478,1647078,2775060,4126166,5360392,6003182,5734040,4611174,3000762,1452778,456036,72682,3918,0,0,0,0,0,8,8,148,540,2224,8132,25192,70608,182160,428000,917254,1772500,3039548,4592732,6082084,6962680,6814546,5632528,3780902,1897752,625528,107552,6654,0,0,0,0,0,8,68,200,824,2768,9268,28008,75180,188364,433344,915312,1758212,3015904,4584896,6091968,6984920,6830780,5624068,3766140,1896708,630056,108164,6144,0,0,0,0,0,8,37,186,747,2811,10437,33836,98343,265720,657396,1498230,3113835,5805351,9632963,14085516,17895349,19501750,18011991,13641658,7883390,3094034,670935,54177,0,0,0,0,0,8,37,186,747,2811,10437,33836,98343,265720,657396,1498230,3113835,5805351,9632963,14085516,17895349,19501750,18011991,13641658,7883390,3094034,670935,54177,0,0,0,0,0,8,36,198,816,3136,12320,42202,129560,370972,973392,2365758,5275328,10629034,19181012,30712808,42989704,51858540,53294524,45286756,29814416,13660260,3625744,381572,0,0,0,0,0,8,36,198,816,3136,12320,42202,129560,370972,973392,2365758,5275328,10629034,19181012,30712808,42989704,51858540,53294524,45286756,29814416,13660260,3625744,381572,0,2,4,9,8,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,2,12,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,2,0,8,20,48,60,45,28,22,20,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,8,24,56,64,56,24,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,9,16,62,104,201,276,260,232,171,100,64,16,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,26,72,148,280,338,312,178,60,36,8,14,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,10,16,82,120,332,560,848,1128,1032,904,708,384,250,56,30,0,6,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,32,88,224,472,824,1272,1256,1000,632,248,200,72,56,8,8,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,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,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,10,8,34,62,47,38,30,10,14,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,22,26,70,70,26,22,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,8,20,60,168,288,446,566,534,436,365,180,97,44,16,2,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,18,28,108,238,440,620,642,506,288,172,74,38,10,12,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,8,24,64,190,476,884,1644,2550,3094,3458,3302,2585,1808,1044,468,240,60,16,8,11,4,0,0,0,0,0,0,0,0,0,0,0,2,6,34,114,266,742,1464,2436,3628,3968,3330,2510,1586,822,476,238,138,42,12,2,0,0,0,0,0,0,0,0,0,0,0,4,8,16,68,224,534,1208,2866,5162,8414,12198,14700,15864,14314,10959,7498,4321,2028,935,296,143,58,32,0,0,0,0,0,0,0,0,0,0,2,14,38,124,388,1010,2376,4876,8462,12526,15832,16288,14448,10612,6720,4004,2196,1026,514,136,48,0,0,0,0,0,0,0,0,0,0,4,8,24,80,244,674,1662,4224,8466,15862,26834,38514,49279,56054,53610,44054,31810,19186,9894,4558,1860,728,312,42,0,0,0,0,0,0,0,0,0,2,6,42,142,404,1208,3278,7498,15558,26882,39990,52154,57478,53026,42714,29726,18480,10640,5240,2048,798,174,0,0,0,0,0,0,0,0,0,4,0,24,48,174,368,496,816,1168,992,824,720,446,240,112,16,20,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,32,96,176,512,864,1152,1264,976,640,368,144,80,64,16,16,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,20,44,159,440,928,1938,3608,5732,7924,9204,9611,8578,6482,4262,2358,1038,474,166,64,36,20,2,0,0,0,0,0,0,0,0,0,0,0,22,72,236,724,1564,3284,5744,8320,10274,10274,8374,5970,3710,2122,1238,586,254,88,24,0,0,0,0,0,0,0,0,0,0,2,0,16,44,166,492,1244,2968,6346,12480,21696,32776,44469,52904,54984,49040,37598,24832,14176,6796,3036,1260,476,152,30,0,0,0,0,0,0,0,0,0,0,16,80,268,852,2308,5556,11504,21192,34064,46788,55224,55728,47768,35468,23440,14136,7712,3516,1372,428,68,0,0,0,0,0,0,0,0,2,0,16,40,169,580,1506,3942,9604,21034,41480,73284,116428,165142,208594,229630,219398,181526,129858,79418,42216,19504,7906,2606,600,70,0,0,0,0,0,0,0,0,0,16,84,288,1002,3036,8100,18880,39428,73190,119098,170786,213846,231342,216294,175946,125946,79880,44420,21100,8178,2312,380,0,0,0,0,0,0,0,2,0,16,40,174,636,1790,5012,13086,31384,68260,133384,236128,377816,543160,690280,770350,749112,632212,459920,288342,154604,70506,25924,6858,1008,56,0,0,0,0,0,0,0,0,16,88,312,1148,3788,10912,27664,63688,130984,237600,385424,554560,700208,771200,739520,619496,454952,291208,159800,73124,25860,6096,592,0,0,0,0,0,0,0,0,20,32,126,424,1248,2884,6598,13248,24174,39800,57483,72180,79526,76800,64936,46028,28462,15360,7061,2996,1134,408,103,4,0,0,0,0,0,0,0,0,0,12,72,352,816,2308,5736,12516,23820,39420,58720,75480,81984,76984,62052,43796,27628,15936,8120,3280,1208,292,8,0,0,0,0,0,0,0,0,0,16,36,136,532,1506,4016,9800,22806,47596,89374,154829,238628,328812,402564,430241,399180,322654,224416,134042,69266,31182,11726,3217,528,42,0,0,0,0,0,0,0,0,6,60,276,1024,2994,8168,19976,44432,88308,155068,244110,339012,408940,429118,392660,313502,221238,136818,72698,32762,11602,2744,264,0,0,0,0,0,0,0,0,16,32,126,504,1772,4920,13206,33452,76968,163012,313332,549702,870072,1231278,1551284,1717704,1661224,1397628,1012862,629424,333008,146320,49393,10690,1112,58,1,0,0,0,0,0,0,6,68,388,1140,3782,11328,29980,72148,156666,310134,550996,880748,1253192,1567770,1715622,1641972,1376876,1007406,635914,342134,150532,48028,9152,728,10,0,0,0,0,0,0,16,32,134,644,1996,6106,17396,46834,115740,262058,548137,1046224,1825392,2884616,4084096,5121184,5657276,5459156,4561416,3274996,2001836,1017142,399116,106598,15600,1002,22,0,0,0,0,0,0,6,60,304,1320,4408,14152,40400,105300,250606,536242,1046200,1844188,2920632,4123928,5139308,5626648,5409846,4534500,3280544,2022868,1030568,400648,103132,13468,638,6,0,0,0,0,0,12,40,130,536,1828,5192,13376,34448,81224,172672,338760,607112,991328,1452504,1892576,2172840,2186928,1915512,1449388,942360,522172,241496,85900,20592,2636,136,2,0,0,0,0,0,0,0,64,288,1136,3784,11232,29792,73968,166016,332848,610512,1007872,1476288,1910976,2173264,2163240,1890648,1441408,949760,533104,246168,85520,18880,1832,40,0,0,0,0,0,0,12,36,128,604,2048,6266,17628,48246,122742,285012,613173,1214404,2209458,3652980,5439977,7208484,8444510,8676256,7751882,5969428,3921418,2156086,933821,287184,51902,4286,114,0,0,0,0,0,0,0,64,296,1282,4530,14516,41506,111008,270874,595864,1207510,2225018,3696348,5494742,7244608,8421578,8614742,7702706,5963198,3947540,2178894,940560,283494,47894,3272,56,0,0,0,0,0,12,36,128,640,2298,7440,22080,63852,173304,431048,995132,2122552,4185388,7561784,12405596,18257392,23924036,27669308,27982476,24489792,18347906,11546896,5807172,2134508,491304,55584,2146,0,0,0,0,0,0,0,64,308,1424,5312,18076,54640,155824,407308,961408,2097416,4188832,7618056,12508172,18368096,23938376,27571192,27854572,24428308,18380504,11605928,5839600,2133232,479800,51036,1700,0,0,0,0,0,12,32,126,568,2248,7292,21966,64180,175154,443084,1031383,2243132,4483178,8224388,13718196,20593708,27545232,32596188,33789181,30339284,23354170,15119192,7872133,3032072,743226,91016,4005,0,0,0,0,0,0,0,64,408,1448,5432,18680,56448,161060,418784,1003208,2205000,4471540,8264484,13828484,20718056,27606216,32513744,33630264,30247496,23364740,15199232,7923848,3026816,729156,85960,3152,0,0,0,0,0,12,32,126,708,2514,8660,27440,83588,241378,643376,1603173,3704584,7962384,15797252,28728420,47320372,69965976,92021224,106608620,107555452,93399126,68619648,40991724,18471968,5549554,896608,53356,0,0,0,0,0,0,0,64,316,1578,6144,22236,71284,216132,604886,1538722,3636408,7921344,15847680,28892632,47594596,70136280,91939632,106329008,107292684,93365830,68745472,41118700,18509048,5520884,875322,49918,0,0,0,0,0,12,32,126,744,2768,9992,33048,105304,320624,905488,2397354,5893440,13546712,28877120,56791376,101851488,165026892,239320864,307457538,345754776,336159704,278022808,188849776,98536264,35417192,7240336,578886,0,0,0,0,0,0,0,64,328,1728,7032,26744,89504,286040,848944,2292960,5765184,13425984,28878688,56990720,102354480,165495456,239397584,307035424,345113208,335889680,278184520,189161336,98703280,35375160,7175904,564752}; int h; int w; int b1[8][8]; int b2[8][8]; int xx[9][9][9][2][33]; void solve() { int p1 = 0; int p2 = 0; for (int r=0; r<h; ++r) for (int c=0; c<w; ++c) if (b1[r][c] == 1) p1 += r + c; for (int r=0; r<h; ++r) for (int c=0; c<w; ++c) if (b2[r][c] == 1) p2 += r + c; if (p1 % 2 != p2 % 2) { printf("0.0\n"); return; } int kr = 0; int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; int k = 0; for (int r=0; r<h; ++r) for (int c=0; c<w; ++c) if (b2[r][c] == 1) { ++k; for (int q=0; q<4; ++q) { int rr = r + dr[q]; int cc = c + dc[q]; if (rr < 0 || cc < 0 || rr >= h || cc >= w) continue; if (b2[rr][cc] == 0) ++kr; } } double res = kr * 2; long long sum = 0; for (int p=0; p<2; ++p) for (int m=1; m<=4*k; ++m) sum += 1LL * m * xx[k][h][w][p][m]; fprintf(stderr, "k: %d, sum: %lld\n", k, sum); res /= sum; printf("%.17lf\n", res); } void init() { int off = 0; for (int k=1; k<=8; ++k) for (int h=1; h<=8; ++h) for (int w=h; w<=8; ++w) { if (k >= h*w) continue; for (int p=0; p<2; ++p) for (int m=1; m<=4*k; ++m) { int xxxx = xxx[off++]; xx[k][h][w][p][m] = xx[k][w][h][p][m] = xxxx; } } } int main() { init(); scanf("%d%d", &h, &w); for (int r=0; r<h; ++r) { char s[64]; scanf("%s", s); for (int c=0; c<w; ++c) { b1[r][c] = s[c] == 'O' ? 1 : 0; } } for (int r=0; r<h; ++r) { char s[64]; scanf("%s", s); for (int c=0; c<w; ++c) { b2[r][c] = s[c] == 'O' ? 1 : 0; } } solve(); return 0; } |