#include <bits/stdc++.h> using namespace std; const long long MAX = 1000000000000000000; long long MAP[18][10][10] = { {{1,0,0,0,0,0,0,0,0,0}, {0,1,0,0,0,0,0,0,0,0}, {0,0,1,0,0,0,0,0,0,0}, {0,0,0,1,0,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0}, {0,0,0,0,0,0,1,0,0,0}, {0,0,0,0,0,0,0,1,0,0}, {0,0,0,0,0,0,0,0,1,0}, {0,0,0,0,0,0,0,0,0,1}}, {{10,0,0,0,0,0,0,0,0,0}, {1,1,1,1,1,1,1,1,1,1}, {2,0,2,0,2,0,2,0,2,0}, {1,0,2,1,1,1,1,0,2,1}, {2,0,1,0,1,0,3,0,3,0}, {7,0,0,0,0,3,0,0,0,0}, {3,0,1,0,0,0,2,0,4,0}, {2,0,1,0,1,1,1,1,3,0}, {3,0,0,0,1,0,3,0,3,0}, {3,0,0,0,2,0,0,0,4,1}}, {{100,0,0,0,0,0,0,0,0,0}, {34,1,8,2,9,6,13,2,22,3}, {44,0,10,0,8,0,20,0,18,0}, {40,0,11,1,9,5,12,0,20,2}, {48,0,6,0,5,0,26,0,15,0}, {87,0,0,0,0,13,0,0,0,0}, {51,0,9,0,5,0,17,0,18,0}, {47,0,9,0,8,5,20,1,10,0}, {54,0,4,0,3,0,25,0,14,0}, {47,0,11,0,8,4,8,0,21,1}}, {{1000,0,0,0,0,0,0,0,0,0}, {552,1,68,3,55,33,141,3,138,6}, {632,0,58,0,33,0,162,0,115,0}, {613,0,79,1,39,21,105,0,139,3}, {681,0,39,0,16,0,157,0,107,0}, {958,0,0,0,0,42,0,0,0,0}, {694,0,61,0,18,0,107,0,120,0}, {694,0,42,0,28,21,160,1,54,0}, {755,0,32,0,6,0,124,0,83,0}, {684,0,87,0,19,15,61,0,133,1}}, {{10000,0,0,0,0,0,0,0,0,0}, {7263,1,466,4,214,132,1017,4,889,10}, {7913,0,353,0,98,0,920,0,716,0}, {7931,0,474,1,110,74,613,0,793,4}, {8431,0,256,0,37,0,716,0,560,0}, {9875,0,0,0,0,125,0,0,0,0}, {8480,0,324,0,42,0,551,0,603,0}, {8490,0,158,0,68,64,851,1,368,0}, {8853,0,204,0,10,0,549,0,384,0}, {8426,0,435,0,36,40,454,0,608,1}}, {{100000,0,0,0,0,0,0,0,0,0}, {85662,1,2670,5,615,435,5671,5,4921,15}, {89196,0,1897,0,230,0,4875,0,3802,0}, {89061,0,2301,1,245,245,4231,0,3911,5}, {91445,0,1356,0,71,0,4138,0,2990,0}, {99619,0,0,0,0,381,0,0,0,0}, {91008,0,1505,0,80,0,4376,0,3031,0}, {91302,0,615,0,135,245,4841,1,2861,0}, {92717,0,1055,0,15,0,3697,0,2516,0}, {90197,0,2061,0,60,160,4866,0,2655,1}}, {{1000000,0,0,0,0,0,0,0,0,0}, {920207,1,13460,6,1451,1466,36695,6,26687,21}, {933774,0,9528,0,462,0,34239,0,21997,0}, {929707,0,11421,1,471,951,37161,0,20282,6}, {942703,0,7026,0,181,0,30959,0,19131,0}, {998807,0,0,0,0,1193,0,0,0,0}, {938492,0,8066,0,255,0,36145,0,17042,0}, {944711,0,2723,0,356,1071,31657,1,19481,0}, {949299,0,5682,0,381,0,27476,0,17162,0}, {934209,0,11514,0,272,660,40587,0,12757,1}}, {{10000000,0,0,0,0,0,0,0,0,0}, {9491909,1,69420,7,3829,5341,274919,7,154539,28}, {9561834,0,52424,0,4088,0,249074,0,132580,0}, {9538181,0,65849,1,4599,3570,278572,0,109221,7}, {9618057,0,43660,0,8380,0,215859,0,114044,0}, {9996471,0,0,0,0,3529,0,0,0,0}, {9600907,0,53390,0,9030,0,243916,0,92757,0}, {9660218,0,20538,0,7203,3997,199990,1,108053,0}, {9666134,0,41076,0,15568,0,183288,0,93934,0}, {9594062,0,71365,0,7483,2219,259728,0,65142,1}}, {{100000000,0,0,0,0,0,0,0,0,0}, {96727773,1,417722,8,60180,18656,1905346,8,870270,36}, {97183454,0,365524,0,102076,0,1628882,0,720064,0}, {97126097,0,443468,1,92100,11516,1765044,0,561766,8}, {97570603,0,350312,0,153721,0,1354532,0,570832,0}, {99990575,0,0,0,0,9425,0,0,0,0}, {97548654,0,400655,0,136444,0,1460419,0,453828,0}, {97878586,0,253627,0,103832,12272,1241804,1,509878,0}, {97929955,0,346480,0,197436,0,1108366,0,417763,0}, {97622405,0,447454,0,93256,6160,1497504,0,333220,1}}, {{1000000000,0,0,0,0,0,0,0,0,0}, {979578102,1,3025242,9,939045,58029,11961897,9,4437621,45}, {982663764,0,2861164,0,1237482,0,9826356,0,3411234,0}, {982918871,0,3050403,1,974745,31869,10347712,0,2676390,9}, {985518393,0,2716767,0,1431757,0,7878618,0,2454465,0}, {999977349,0,0,0,0,22651,0,0,0,0}, {985857171,0,2737101,0,1135440,0,8275969,0,1994319,0}, {986865866,0,2468514,0,872481,32121,7594662,1,2166355,0}, {988296759,0,2465967,0,1451817,0,6168711,0,1616746,0}, {986706155,0,2547882,0,689718,14760,8430852,0,1610632,1}}, {{10000000000,0,0,0,0,0,0,0,0,0}, {9878382430,1,21873040,10,8732485,159430,70484777,10,20367762,55}, {9900526094,0,19875933,0,9375140,0,55772770,0,14450063,0}, {9904869365,0,18549872,1,6746485,77665,57999579,0,11757023,10}, {9921215165,0,17225847,0,8984341,0,42958482,0,9616165,0}, {9999950419,0,0,0,0,49581,0,0,0,0}, {9925270623,0,15470020,0,6592905,0,44579845,0,8086607,0}, {9925210327,0,17504924,0,5177200,74305,43064918,1,8968325,0}, {9939663569,0,13905250,0,7668415,0,32619365,0,6143401,0}, {9930928773,0,12496527,0,3684560,31620,45658394,0,7200125,1}}, {{100000000000,0,0,0,0,0,0,0,0,0}, {99326016765,1,136901413,11,56961531,392601,393138130,11,86589471,66}, {99474404786,0,114029719,0,52283957,0,300029554,0,59251984,0}, {99508935359,0,95437529,1,35198031,170951,309861453,0,50396665,11}, {99599615145,0,88964480,0,43316516,0,226544220,0,41559639,0}, {99999899712,0,0,0,0,100288,0,0,0,0}, {99629431515,0,72658872,0,29983250,0,231848266,0,36078097,0}, {99605068461,0,97084560,0,24155681,156101,225852154,1,47683042,0}, {99695226958,0,64420389,0,32267631,0,174572310,0,33512712,0}, {99660525302,0,52704410,0,15720617,62095,237397424,0,33590151,1}}, {{1000000000000,0,0,0,0,0,0,0,0,0}, {996499124003,1,722201372,12,289887214,882036,2099243511,12,388661761,78}, {997325950061,0,548127065,0,234585078,0,1585621052,0,305716744,0}, {997544339519,0,419808061,1,149913534,346710,1621936570,0,263655593,12}, {997934645314,0,388888545,0,172724905,0,1222418124,0,281323112,0}, {999999810115,0,0,0,0,189885,0,0,0,0}, {998128620262,0,292607074,0,114337410,0,1226533916,0,237901338,0}, {997878260436,0,446614093,0,94543912,303744,1191689622,1,388588192,0}, {998338308785,0,258797528,0,115887102,0,985390717,0,301615868,0}, {998299654938,0,194685645,0,57220132,113784,1249370002,0,198955498,1}}, {{10000000000000,0,0,0,0,0,0,0,0,0}, {9981948713433,1,3271729383,13,1229099287,1836159,11182203514,13,2366418106,91}, {9985836512869,0,2285533238,0,903400550,0,8637913830,0,2336639513,0}, {9987211394494,0,1619971288,1,559349921,657761,8723126763,0,1885499759,13}, {9988456300026,0,1508398229,0,629428255,0,6892012101,0,2513861389,0}, {9999999659867,0,0,0,0,340133,0,0,0,0}, {9989816998846,0,1047530068,0,417721980,0,6761320944,0,1956428162,0}, {9987751222276,0,1773930652,0,339754688,555373,6750044184,1,3384492826,0}, {9990122610763,0,962243490,0,459303364,0,5680583376,0,2775259007,0}, {9990887874782,0,644837349,0,218548824,197080,6864707499,0,1383834465,1}}, {{100000000000000,0,0,0,0,0,0,0,0,0}, {99902031287356,1,13114173697,14,4756606869,3586506,61491912211,14,18602433227,105}, {99919641710032,0,8606104340,0,3668907088,0,48528107058,0,19555171482,0}, {99929264352695,0,5647574611,1,2424698563,1180739,48266305206,0,14395888171,14}, {99931699651720,0,5483870016,0,3371107195,0,38898245701,0,20547125368,0}, {99999999418663,0,0,0,0,581337,0,0,0,0}, {99942017318716,0,3467777861,0,2569780759,0,37225384302,0,14719738362,0}, {99927873948748,0,6254904215,0,1614558232,964523,39307821385,1,24947802896,0}, {99939809553494,0,3566556644,0,4129671651,0,31435810812,0,21058407399,0}, {99949448192672,0,1963761996,0,1683101448,325780,37753002938,0,9151615165,1}}, {{1000000000000000,0,0,0,0,0,0,0,0,0}, {999441785434096,1,48104723380,15,24218431805,6638885,342906589613,15,142978182070,120}, {999530394990365,0,30615528854,0,27720348105,0,267931309640,0,143337823036,0}, {999601642329051,0,18366321393,1,21015375585,2023260,261504612384,0,97469338311,15}, {999593910499764,0,19811642068,0,38273670076,0,208454487722,0,139549700370,0}, {999999999045449,0,0,0,0,954551,0,0,0,0}, {999671553418406,0,11087644490,0,30658069785,0,193542768631,0,93158098688,0}, {999596377529707,0,19974463570,0,14620363805,1604205,217262336300,1,151763702412,0}, {999636863478955,0,13916789960,0,56183937930,0,161986434194,0,131049358961,0}, {999724777284070,0,5649374913,0,21235704485,517755,195567420696,0,52769698080,1}}, {{10000000000000000,0,0,0,0,0,0,0,0,0}, {9996797304009863,1,167526488628,16,233925901576,11738656,1849155959180,16,952075901928,136}, {9997280671340441,0,107723197271,0,331483705352,0,1393872382200,0,886249374736,0}, {9997801672282131,0,57668744012,1,250479263736,3332376,1325951950092,0,564224427636,16}, {9997619051982521,0,74116160124,0,468171031201,0,1042289009976,0,796371816178,0}, {9999999998485887,0,0,0,0,1514113,0,0,0,0}, {9998179884076364,0,35679377951,0,355983047880,0,927930426481,0,500523071324,0}, {9997909326894869,0,58643574930,0,156560419056,2571616,1094162376972,1,781304162556,0}, {9997832483391271,0,57128708096,0,630784474456,0,789834040308,0,689769385869,0}, {9998560580374487,0,15803521564,0,234139390192,795680,925632437780,0,263843480296,1}}, {{100000000000000000,0,0,0,0,0,0,0,0,0}, {99981980972837834,1,574289772576,17,2661527233449,19952441,9348828582989,17,5434361620523,153}, {99984541917142935,0,387158434419,0,3589960401658,0,6781742947852,0,4699221073136,0}, {99988218706190613,0,180552032329,1,2569422345249,5304425,6202558665292,0,2828755462074,17}, {99986225932168174,0,287637011553,0,4590583290265,0,4970554559287,0,3925292970721,0}, {99999999997669469,0,0,0,0,2330531,0,0,0,0}, {99990104052509256,0,118324717262,0,3289671369520,0,4145913647648,0,2342037756314,0}, {99989902464958499,0,160145819015,0,1426962514565,3993521,5009166641964,1,3501256072435,0}, {99987242858821151,0,236438712690,0,5518031810925,0,3833552629569,0,3169118025665,0}, {99992750965596212,0,44175064060,0,2039166442570,1187824,4001253338345,0,1164438370988,1} }}; long long DEG16[100][10] = {{10000000000000000,0,0,0,0,0,0,0,0,0}, {9996797304009863,1,167526488628,16,233925901576,11738656,1849155959180,16,952075901928,136}, {9997280671340441,0,107723197271,0,331483705352,0,1393872382200,0,886249374736,0}, {9997801672282131,0,57668744012,1,250479263736,3332376,1325951950092,0,564224427636,16}, {9997619051982521,0,74116160124,0,468171031201,0,1042289009976,0,796371816178,0}, {9999999998485887,0,0,0,0,1514113,0,0,0,0}, {9998179884076364,0,35679377951,0,355983047880,0,927930426481,0,500523071324,0}, {9997909326894869,0,58643574930,0,156560419056,2571616,1094162376972,1,781304162556,0}, {9997832483391271,0,57128708096,0,630784474456,0,789834040308,0,689769385869,0}, {9998560580374487,0,15803521564,0,234139390192,795680,925632437780,0,263843480296,1}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9994261945610933,1,892963347572,0,59454354254,2446200,4699681168004,0,85953073020,16}, {9998435783967383,0,23986901781,0,479845606496,0,631279381712,0,429104142628,0}, {9996583865270339,0,1028674347432,1,531029478832,458376,1493582512064,136,362847931124,1696}, {9998396352410331,0,30163814464,0,211174140057,0,762828092068,0,599481543080,0}, {9999999999634207,0,0,0,0,365793,0,0,0,0}, {9997950366458293,0,49090268244,0,796984668480,0,628495112015,0,575063492968,0}, {9995801501839084,0,1608162692296,0,1124163919000,152,716002643700,1,750168905751,16}, {9998847323516331,0,9270006488,0,315533727736,0,605214503092,0,222658246353,0}, {9998852192413575,0,210297156632,0,73528852376,146116,572826001676,136,291155429472,17}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9998695148143421,0,16743673425,0,151142490056,657120,735823586056,0,401141449922,0}, {9994782649202603,0,759465152960,0,31790429305,0,4373458159452,0,52637055680,0}, {9998214730940383,0,239769279280,0,41768228600,58096,1483463428913,0,20268064728,0}, {9998587445266527,0,18281639152,0,606793867696,0,432142761172,0,355336465453,0}, {9999999999936448,0,0,0,0,63552,0,0,0,0}, {9997320155691684,0,699272406113,0,747039349296,0,1031550780304,0,201981772603,0}, {9999110868929762,0,3118167956,0,175504951457,153456,618583618907,0,91924178462,0}, {9998753924702511,0,14399662504,0,270034311040,0,524925949893,0,436715374052,0}, {9998269089265517,0,6779542176,0,0,101360,1675482339946,0,48648751001,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9996400686404393,0,86812248974,1,27281734512,64208,3425054591448,0,60164956464,0}, {9998012127541779,0,44731235124,0,938956789680,0,543556341401,0,460628092016,0}, {9994855594034827,0,772333727412,0,77197848312,677040,4264811786712,0,30061925696,1}, {9996624260093327,0,1139208316649,0,1140647606080,0,566963417720,0,528920566224,0}, {9999999999687679,0,0,0,0,312321,0,0,0,0}, {9999034748857889,0,5902436528,0,399012541216,0,378031962810,0,182304201557,0}, {9996548230434575,16,1091974861661,0,270296,1681680,1240758881048,0,1119033870724,0}, {9999042457830389,0,267817063526,0,53660186192,0,433103149824,0,202961770069,0}, {9997696929574774,0,536570553152,0,663549847201,118356,853186251013,16,249763655368,120}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9997626800240683,0,795625374320,0,150976183601,0,1040591911552,0,386006289844,0}, {9999032419091851,0,8019522192,0,193510080416,0,472064344100,0,293986961441,0}, {9997932068270957,0,112812677729,0,136,1920,1735974771516,0,219144277742,0}, {9995304729745629,0,680443465164,0,13801100080,0,3969927432399,0,31098256728,0}, {9999999999925248,0,0,0,0,74752,0,0,0,0}, {9998551148539717,0,247500813852,0,17477888418,0,1169406519668,0,14466238345,0}, {9996047663535267,0,23455289960,0,10896,262200,1763430874141,0,2165450027536,0}, {9998664952974977,0,15525277114,0,717332637840,0,317915662725,0,284273447344,0}, {9998883270276594,0,22007942090,0,272,310368,573807928603,0,520913542073,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9996993118306365,0,1219524081310,0,943036067040,17,306885365948,0,537436179320,0}, {9997747431959048,0,444357307304,0,979558275712,0,727470434338,0,101182023598,0}, {9997779993539211,0,18240155212,240,7695856,10881,1881145797320,0,320612801280,0}, {9999321494757934,0,1659556056,0,221659860240,0,381334605556,0,73851220214,0}, {9999999999711712,0,0,0,0,288288,0,0,0,0}, {9998993459921822,0,6403564386,0,324590106516,0,370818492472,0,304727914804,0}, {9999365393342039,0,183064441640,0,20425768456,28057,312565128588,16,118551291204,0}, {9998638973104936,0,4026780884,0,0,0,1304110263956,0,52889850224,0}, {9998236991224361,0,75621809272,0,2732850120,11576,1502110234007,0,182543870664,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9999454858014507,0,27922900,0,784944,7280,402718196057,0,142395074312,0}, {9996614947772643,0,54113931885,0,14007313320,0,3284419242176,0,32511739976,0}, {9999238563829421,0,3764065024,0,119950967152,142096,474735871800,0,162985124507,0}, {9998058991607297,0,41013307942,0,1029842583120,0,515868990872,0,354283510769,0}, {9999999999985632,0,0,0,0,14368,0,0,0,0}, {9995425776194943,0,620224710264,0,38458603064,0,3898961056528,0,16579435201,0}, {9997195730508435,0,1324666155208,0,321116235440,0,791909638964,0,366577461953,0}, {9997326543904103,0,741453102876,0,1108586178960,0,473428460941,0,349988353120,0}, {9999103929768136,0,98717689312,0,25721055480,12320,760580339456,0,11051135296,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9999183735111719,0,31067123656,0,410213440,59484,337423647688,1,447363831412,12600}, {9999143031659185,0,4264712632,0,472746683137,0,234921228604,0,145035716442,0}, {9998250631444404,0,5468063920,0,572978003728,3636,1099507624048,0,71414860264,0}, {9996776579809739,0,1057313697800,0,41360,0,1100535590205,0,1065570860896,0}, {9999999999990559,0,0,0,0,9441,0,0,0,0}, {9999110713033987,0,358690003308,0,36686524000,0,362403627892,0,131506810813,0}, {9996441651717089,0,311268628934,0,66994543776,222784,3172771533448,0,7313353969,0}, {9998106258624880,0,334550628040,0,882984822720,0,544530291408,0,131675632952,0}, {9998205629406735,0,13769395496,0,3600,54080,1728727289848,136,51873850105,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9999494353745955,0,392597812,0,100618321440,21840,382799109796,0,21836203157,0}, {9998231299966433,0,584674065544,0,128995776256,0,703678608753,0,351351583014,0}, {9997209325449237,0,905048113016,0,9798896,1920,1737407791650,0,148208845281,0}, {9999264845017515,0,3509085236,0,233164540336,0,293398926733,0,205082430180,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9998295781781223,0,65069822100,0,16,0,1441043887061,0,198104509600,0}, {9998638138663450,0,1058746654,0,0,17880,1333771235720,0,27031336296,0}, {9995855161575143,0,629793852980,0,4597410800,0,3492802532316,0,17644628761,0}, {9999314652879393,0,111747809296,0,3315443977,240,564729337580,0,5554529514,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9997699875641553,0,391155125976,0,845286842672,47280,819547719108,0,244134623170,241}, {9998847325982679,0,248341322176,0,6035466768,0,888800259288,0,9496969089,0}, {9996475750146699,0,22254844112,0,8508820321,14740,3476546429752,0,16939744376,0}, {9996251460315483,0,20209090128,0,1920,0,1662977385836,0,2065353206633,0}, {9999999999989360,0,0,0,0,10640,0,0,0,0}, {9998704919873536,0,13860111124,0,792049811280,0,268883852940,0,220286351120,0}, {9998511768194779,0,12812566740,0,36063731376,0,1411526925000,0,27828582105,0}, {9999278548602061,0,10425677336,0,17,0,378395419178,0,332630301408,0}, {9995568083803435,0,619286171824,0,87293735240,152880,3713928595932,0,11407540689,0}}; long long DEG15[1000][10] = {{1000000000000000,0,0,0,0,0,0,0,0,0}, {999441785434096,1,48104723380,15,24218431805,6638885,342906589613,15,142978182070,120}, {999530394990365,0,30615528854,0,27720348105,0,267931309640,0,143337823036,0}, {999601642329051,0,18366321393,1,21015375585,2023260,261504612384,0,97469338311,15}, {999593910499764,0,19811642068,0,38273670076,0,208454487722,0,139549700370,0}, {999999999045449,0,0,0,0,954551,0,0,0,0}, {999671553418406,0,11087644490,0,30658069785,0,193542768631,0,93158098688,0}, {999596377529707,0,19974463570,0,14620363805,1604205,217262336300,1,151763702412,0}, {999636863478955,0,13916789960,0,56183937930,0,161986434194,0,131049358961,0}, {999724777284070,0,5649374913,0,21235704485,517755,195567420696,0,52769698080,1}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999168901575061,1,147996088340,0,7318548660,1531635,648495467273,0,27286789015,15}, {999722656229965,0,6907309210,0,45644639265,0,138570753455,0,86221068105,0}, {999315993277160,0,238760478290,1,32572132755,309428,330919726930,120,81754073936,1380}, {999682389518315,0,11002777976,0,20717730571,0,158929986683,0,126959986455,0}, {999999999753954,0,0,0,0,246046,0,0,0,0}, {999662497948227,0,11147593903,0,80263703520,0,127795276816,0,118295477534,0}, {999252130781474,0,296674648158,0,137619023220,135,156253029997,1,157322517000,15}, {999780405256444,0,3233910810,0,32021606100,0,136661365059,0,47677861587,0}, {999753628360293,0,22405194228,0,20438063640,104525,135656700008,120,67871577170,16}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999727411154567,0,6364922911,0,15654953280,438375,161887883932,0,88680646935,0}, {999238231448049,0,119287000440,0,4606737466,0,620110627735,0,17764186310,0}, {999630158268677,0,38288094292,0,10072167275,42435,318096155106,0,3385272215,0}, {999756282234273,0,4776600135,0,65217877740,0,96750138740,0,76973149112,0}, {999999999954715,0,0,0,0,45285,0,0,0,0}, {999486876964153,0,178310326111,0,51637050675,0,233843512466,0,49332146595,0}, {999816944621401,0,1282660150,0,19031037496,106940,141467007195,0,21274566818,0}, {999751645624105,0,5617289165,0,29260689315,0,113321122657,0,100155274758,0}, {999670183698169,0,2371375081,0,0,73710,319874562228,0,7570290812,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999533571030833,0,27249660428,1,9639484885,47103,410032778030,0,19506998720,0}, {999674935694062,0,10025850345,0,107573466000,0,105152224951,0,102312764642,0}, {999225127806973,0,138968835631,0,11396858560,453180,614209326200,0,10296719455,1}, {999377646693056,0,229874328976,0,154226351125,0,120324511525,0,117928115318,0}, {999999999785244,0,0,0,0,214756,0,0,0,0}, {999820260273170,0,1913085338,0,45753047355,0,90258571441,0,41815022696,0}, {999498760256997,15,167376326671,0,194160,780780,211740346914,0,122122094463,0}, {999814980577657,0,21987013416,0,16083318645,0,95862944180,0,51086146102,0}, {999553436310022,0,135351059605,0,47197640701,85170,206403391629,15,57611512753,105}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999542414319213,0,157823392890,0,11198311636,0,210862778486,0,77701197775,0}, {999793769285561,0,3257360905,0,22248940365,0,110256113028,0,70468300141,0}, {999667793502015,0,20475702549,0,120,1575,269276248591,0,42454545150,0}, {999297315309882,0,103667469395,0,2338051200,0,585549788053,0,11129381470,0}, {999999999946525,0,0,0,0,53475,0,0,0,0}, {999685729728739,0,39865026440,0,4702971975,0,267285109465,0,2417163381,0}, {999435656036155,0,4948941040,0,8415,173460,250614142727,0,308780698203,0}, {999774584326408,0,3823725390,0,87298020810,0,68162976262,0,66130951130,0}, {999727779823289,0,8166264255,0,240,213150,136802051205,0,127251647861,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999431059469948,0,238857698188,0,137506917240,16,72380742580,0,120195172028,0}, {999607792836898,0,123917073133,0,77356805541,0,164056188733,0,26877095695,0}, {999678209579467,0,6379527995,210,535200,8401,247362729894,0,68047618833,0}, {999860373052137,0,679741673,0,27140846460,0,93727739865,0,18078619865,0}, {999999999800710,0,0,0,0,199290,0,0,0,0}, {999802265883929,0,2665351253,0,39424029645,0,80541662695,0,75103072478,0}, {999866066667826,0,18496741720,0,6360390870,21471,77830139790,15,31246038308,0}, {999748934034860,0,1464154150,0,0,0,243804184260,0,5797626730,0}, {999639193889369,0,22362145275,0,601260660,8975,285293670100,0,52549025621,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999873893445591,0,16306255,0,518940,5460,105350111786,0,20739611968,0}, {999561448159372,0,17817052306,0,5350430085,0,404350834542,0,11033523695,0}, {999827688290152,0,1595144895,0,14633711835,101130,115161220472,0,40921531516,0}, {999679811226503,0,9515217105,0,133686382830,0,92556458175,0,84430715387,0}, {999999999989297,0,0,0,0,10703,0,0,0,0}, {999290289872521,0,110495233250,0,6572452608,0,586601927210,0,6040514411,0}, {999508099897096,0,166076869380,0,73663394805,0,168246703133,0,83913135586,0}, {999491075632295,0,163870275600,0,165688291860,0,96287238925,0,83078561320,0}, {999791660400332,0,16941942165,0,7023326415,9555,182681580503,0,1692741030,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999829923599068,0,10272761535,0,158143440,42645,62539518096,1,97105925660,9555}, {999845242598914,0,1257580005,0,61137055981,0,56888868475,0,35473896625,0}, {999717017441188,0,2116298104,0,77055731025,2850,182619418610,0,21191108223,0}, {999516931135603,0,166968563415,0,31815,0,188978429932,0,127121839235,0}, {999999999992754,0,0,0,0,7246,0,0,0,0}, {999851761828441,0,28583648410,0,11832154425,0,72038433603,0,35783935121,0}, {999395918076147,0,53080859606,0,11150940885,152895,537200414673,0,2649555794,0}, {999664413506742,0,93077423460,0,72829326570,0,136437574735,0,33242168493,0}, {999750705162429,0,2874122840,0,2940,38355,230196361740,120,16224311576,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999884889051674,0,192023780,0,13186380480,16380,95900244577,0,5832283109,0}, {999634002520411,0,127855897743,0,11691383110,0,152663522241,0,73786676495,0}, {999498484014308,0,144686071490,0,5944590,1575,312700966731,0,44123001306,0}, {999844315693641,0,1522503153,0,29990350390,0,71243522131,0,52927930685,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999709002729898,0,13220916660,0,15,0,240455702311,0,37320651116,0}, {999763636311642,0,443515445,0,0,13860,231910643988,0,4009515065,0}, {999354248509011,0,96927307680,0,908048535,0,541227822910,0,6688311864,0}, {999836867879168,0,24438336981,0,1312311786,210,136728680825,0,652791030,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999568564204856,0,106633003238,0,79997968290,34335,185119795926,0,59684993144,211}, {999738585826811,0,41446748960,0,1809563730,0,216488037938,0,1669822561,0}, {999522673945249,0,7800283640,0,3298555261,11445,460082053490,0,6145150915,0}, {999461276113724,0,4209425340,0,1575,0,233870380390,0,300644078971,0}, {999999999991810,0,0,0,0,8190,0,0,0,0}, {999781763731807,0,3422092405,0,108643209675,0,51625015818,0,54545950295,0}, {999675590367064,0,4433956935,0,10476077720,0,299846011530,0,9653586751,0}, {999811559668331,0,4137289435,0,16,0,95457824370,0,88845217848,0}, {999291913212579,0,122540553230,0,15162716340,109200,566285793950,0,4097614701,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999781892154197,0,6147781185,0,264360635,0,158846775765,0,52848928218,0}, {999537514804522,0,177911940615,0,143774532840,0,51570581808,0,89228140215,0}, {999765568439894,0,155325565055,0,274614810,0,43689016395,0,35142363846,0}, {999680739282350,0,80018118945,0,108050747805,0,117956578125,0,13235272775,0}, {999999999950635,0,0,0,0,49365,0,0,0,0}, {999716549119602,0,2441466538,0,479130,0,238785994455,0,42222940275,0}, {999693697374660,0,20483324830,0,169132005,470,257339600895,0,28310567140,0}, {999890678879205,0,364006145,0,36161405280,0,57779535390,0,15016173980,0}, {999839474405409,0,18339485635,0,85290,0,110480402040,0,31705621626,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999590548061145,1,119566740785,0,16920,225225,143269620780,0,146615335144,0}, {999835461648786,0,1186764661,0,49811541780,0,59438771413,0,54101273360,0}, {999776206593539,0,1034880,1,19320,21945,154041054115,0,69751276200,0}, {999897461509054,0,21369435250,0,4785255931,0,53979982550,0,22403817215,0}, {999999999995574,0,0,0,0,4426,0,0,0,0}, {999810647030789,0,904092191,0,0,0,182134577302,0,6314299718,0}, {999706048898861,0,72606864650,0,61387806495,18740,118845743520,1,41110667733,0}, {999736428404695,0,15012432645,0,561470910,0,215833398918,0,32164292832,0}, {999528756960364,0,216694300305,0,105180480420,0,107112127200,0,42256131710,1}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999685652293367,0,32105791,0,17798235,0,208561286417,0,105736516190,0}, {999911747353493,0,5247860,0,162646,0,73922291399,0,14324944602,0}, {999667871602161,0,122870126940,0,20927246460,0,151554776021,0,36776248418,0}, {999584007260134,0,11051788205,0,2709546840,0,396318440220,0,5912964601,0}, {999999999999335,0,0,0,0,665,0,0,0,0}, {999874945087663,0,774477916,0,19720857975,0,73639089091,0,30920487355,0}, {999309682060223,0,201224729165,0,145385340706,5670,341269505001,0,2438359235,0}, {999683298379794,0,9010286040,0,153594395955,0,87914709811,0,66182228400,0}, {999716387686055,0,19297484535,0,0,210,236825431436,0,27489397764,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999827953637497,0,80368023778,1,1926197028,10220,87816824390,0,1935307086,0}, {999354560866166,0,91067519085,0,3073853840,0,547848068886,0,3449692023,0}, {999868868921070,0,42330695533,0,4595564185,8855,35331434330,0,48873376026,1}, {999590285187333,0,177813645911,0,47428886505,0,113363507885,0,71108772366,0}, {999999999990339,0,0,0,0,9661,0,0,0,0}, {999588710689603,0,106941889735,0,169080584400,0,80594016570,0,54672819692,0}, {999637247387485,0,20641547804,0,55517889015,0,235508743676,0,51084432020,0}, {999835155158108,0,17601576090,0,3099546450,0,142851449990,0,1292269362,0}, {999778963642185,0,85396424465,0,11985205066,665,55405173645,0,68249553974,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999510027806887,0,951352220,0,1,46410,220869870857,0,268150923625,0}, {999861468195224,0,6533272740,0,95255160,0,50539847940,0,81363428936,0}, {999898227587165,0,1751106751,0,16172636565,32775,26560348460,0,57288288284,0}, {999858013502706,0,958738395,0,76113947910,0,35849678769,0,29064132220,0}, {999999999989570,0,0,0,0,10430,0,0,0,0}, {999759476150289,0,832985605,0,63614864040,0,165892453850,0,10183546216,0}, {999850797531104,0,2302451415,0,15,49140,81606584416,0,65293383910,0}, {999541847799099,0,161740074825,0,4725,0,170923006606,0,125489114745,0}, {999725261265926,0,83528001510,0,0,1365,180519300853,0,10691430346,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999778232192542,0,1354402030,0,3797495,1711,218066284650,0,2343321572,0}, {999867376472895,0,40954766000,0,8113609140,0,60422962460,0,23132189505,0}, {999594606807822,0,177337610719,0,111087737895,1,31480395095,0,85487448468,0}, {999472607338845,0,48684616755,0,5962051530,0,471092374425,0,1653618445,0}, {999999999999775,0,0,0,0,225,0,0,0,0}, {999730631649615,0,59740356936,0,103716112500,0,89028815216,0,16883065733,0}, {999766612556524,0,47734731900,0,31674881295,1,153110851965,0,866978315,0}, {999769863129035,0,2670247560,0,210,0,217966858765,0,9499764430,0}, {999696612954419,0,2685931760,15,245700,1590,236467039695,0,64233826821,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999845987143445,0,38098278198,0,10441791585,0,97604505047,0,7868281725,0}, {999917404866092,0,88466206,0,17484960675,0,60409655002,0,4612052025,0}, {999628745736988,0,194000182005,0,300525,4305,163937056405,0,13316719772,0}, {999721144620799,0,94852410135,0,10403127750,0,105279855035,0,68319986281,0}, {999999999948130,0,0,0,0,51870,0,0,0,0}, {999582021466249,0,132756300470,0,1699425,0,259067150960,0,26153382896,0}, {999761258995989,0,9734364900,0,7258680,1575,132371870940,0,96627507916,0}, {999878773984709,0,645571500,0,37924616730,0,44752844201,0,37902982860,0}, {999636915473841,0,100298945595,0,115650,0,168808283170,0,93977181744,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999932048084529,0,14169662075,0,1320495540,3075,41703404755,1,10758350025,0}, {999753630485028,0,7760106530,0,1,0,202826329396,0,35783079045,0}, {999707339499179,0,552591141,0,27134600235,120,254286174695,0,10687134630,0}, {999816105974064,0,195365510,0,0,0,180300605571,0,3398054855,0}, {999999999990324,0,0,0,0,9676,0,0,0,0}, {999415225607494,0,94676257420,0,239872845,0,486028731045,0,3829531196,0}, {999756867682259,0,7276493280,0,0,1710,211365784160,0,24490038591,0}, {999894107345986,0,15042988085,0,410089800,0,90075749944,0,363826185,0}, {999679293452935,0,147359979055,0,107655,0,152506710389,0,20839749966,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999887260973783,0,51433453190,0,1643460,0,61023751646,0,280177921,0}, {999660278157039,0,71670976315,0,105698032455,0,128807130261,0,33545703930,0}, {999945999709809,0,1973750,0,36975,0,36061911345,0,17936368121,0}, {999788362978613,0,42144176495,0,543730110,0,167884823704,0,1064291078,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999543315432279,0,4842572820,0,1749187440,0,446845537441,0,3247270020,0}, {999688606398145,0,150749675135,0,26020809585,15,83291210040,0,51331907080,0}, {999493537015414,0,3659455815,0,210,0,214619693870,0,288183834691,0}, {999897447165389,0,281240730,0,10969059466,19110,77276328785,0,14026186520,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999907118933858,0,1184352458,0,683214315,665,28878933108,0,62134565595,1}, {999783514133935,0,3187220520,0,125480024670,0,44721979219,0,43096641656,0}, {999783615463873,0,234833385,0,951827896,30,215067532325,0,130342491,0}, {999763599936502,0,2247135534,0,4412659800,0,225894717368,0,3845550796,0}, {999999999997030,0,0,0,0,2970,0,0,0,0}, {999877420977532,0,1915182405,0,0,0,64129394198,0,56534445865,0}, {999479513878829,0,48019501985,0,56035995,3500,323221433630,0,149189146061,0}, {999360170250635,0,94659748935,0,8089361281,0,534998819188,0,2081819961,0}, {999887402432431,0,119018460,0,38769298260,785,36613625025,0,37095625039,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999609150301332,0,170150742545,0,60027732765,0,120964242413,0,39706980945,0}, {999753611248940,0,5607416010,0,296639295,0,168186293570,0,72298402185,0}, {999778286254063,0,727205575,0,0,1575,209058844844,0,11927693943,0}, {999631695785307,0,121531150905,0,144530282715,0,39995593220,0,62247187853,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999785554727405,0,167657462835,0,66403155,0,27716152200,0,19005254405,0}, {999899091440084,0,5383436640,0,4075131060,1680,90571767160,0,878223376,0}, {999717470595363,0,47858172825,0,139532232840,0,89054607411,0,6084391561,0}, {999566794745953,0,141143648625,0,14200515435,0,104065873671,0,173795216316,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999812080788000,0,268347290,0,5120340,0,157949643725,0,29696100645,0}, {999745275489966,0,798681135,0,1448371,0,230132904658,0,23791475870,0}, {999917569680340,0,2338745495,0,0,12068,35328572782,0,44762987950,1365}, {999733611399311,0,18407881170,0,45466100,0,221449454912,0,26485798507,0}, {999999999999880,0,0,0,0,120,0,0,0,0}, {999909270753775,0,210110802,0,44979114180,0,33391259688,0,12148761555,0}, {999514165178416,0,9936131201,0,2433661231,3165,463589493834,0,9875532153,0}, {999866732866142,0,13644267170,0,11565,0,92849749060,0,26773106063,0}, {999755586438888,0,699804246,0,98984095665,665,132511146460,0,12218514076,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999897457377784,0,12225414505,0,2655252601,0,87186839890,0,475115220,0}, {999606389954368,0,121706698380,0,2255,0,126406157281,0,145497187716,0}, {999915953172001,0,4725900229,0,782431875,15,78005687470,0,532808410,0}, {999855344616517,0,505504394,0,58684799355,0,47619727678,0,37845352056,0}, {999999999999320,0,0,0,0,680,0,0,0,0}, {999824125302395,0,96915,0,1575,0,115661592958,0,60213006157,0}, {999661234756174,0,111858343995,0,120457447110,16395,68526176136,0,37923260190,0}, {999911524086922,0,28812672945,0,3371877915,0,41324849479,0,14966512739,0}, {999741679698516,0,90013451010,0,139335,0,128174564013,0,40132147126,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999533224837356,0,36221619610,0,14474565540,42315,415707134949,0,371800230,0}, {999856758962189,0,548687088,0,0,0,134954279213,0,7738071510,0}, {999658880773139,0,33773401280,0,14813939130,0,272823838080,0,19708048371,0}, {999771952699524,0,44679958388,0,88219040910,0,72366373357,0,22781927821,0}, {999999999967225,0,0,0,0,32775,0,0,0,0}, {999814609488153,0,9657913545,0,489338850,0,157105375875,0,18137883577,0}, {999758281192526,0,644759550,0,210,11193,235123014860,15,5951021646,0}, {999646128327009,0,148348622010,0,92133427530,0,87570796281,0,25818827170,0}, {999734451703432,0,77412374320,0,574247145,1470,179660046238,105,7901627290,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999787063285070,0,3826383590,0,11403,19110,180010290036,0,29100010791,0}, {999758505926666,0,19984810,0,8396115,0,160998456034,0,80467236375,0}, {999933860549750,0,19918470,0,6552147420,1365,58631848405,0,935534590,0}, {999933060121260,0,1766865,0,44100,0,52707598855,0,14230468920,0}, {999999999971047,0,0,0,0,28953,0,0,0,0}, {999749835839296,0,94308588675,0,19494111225,0,102281129179,0,34080331625,0}, {999540851290979,0,38949264826,0,121182626565,1575,285992904385,0,13023911670,0}, {999606549605647,0,6530634968,0,1243602360,0,382689486735,0,2986670290,0}, {999643279555329,0,83174657045,0,1184821,210,250264841572,0,23279761023,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999716604473234,0,180401288340,0,38047829820,455,61711943631,0,3234464520,0}, {999908696273292,0,341495973,0,24938283825,0,43878904920,0,22145041990,0}, {999643246252016,0,14807730,0,2734095,15,177208184264,0,179528021880,0}, {999349063396157,0,201922102540,0,142016566632,0,304384949866,0,2612984805,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999690486365117,0,8245999350,0,163058712180,0,89000492753,0,49208430600,0}, {999748954212861,0,93054418641,0,9555,0,90595371978,0,67395986965,0}, {999760193297849,0,11036791185,0,0,0,205826068580,0,22943842386,0}, {999551750004662,0,119626702995,0,19530,630630,143750424825,0,184872217358,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999824537010171,0,125147136,0,0,1785,173444642540,0,1893198368,0}, {999835062418039,0,94789042845,0,1319822910,0,67886612040,0,942104166,0}, {999469416134819,0,180335501640,0,37478613900,24585,312420807596,0,348917460,0}, {999424225852169,0,77542079870,0,1104924500,0,495203976436,0,1923167025,0}, {999999999999320,0,0,0,0,680,0,0,0,0}, {999886380156215,0,52036907882,0,3353763106,0,23670821422,0,34558351375,0}, {999899712372434,0,19806132885,0,531532365,0,79066182786,0,883779530,0}, {999645378076028,0,195201154530,0,27333726420,0,70510099951,0,61576943071,0}, {999685743409025,0,1203159090,0,149199050000,0,72077776800,0,91776605085,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999940683255121,0,35419961340,0,196441471,15,19907973458,0,3792368595,0}, {999670005323379,0,63564343605,0,162376517160,0,70674169511,0,33379646345,0}, {999708408884459,0,53955025140,0,88784130450,8400,104835127340,0,44016824196,15}, {999756244499934,0,16164753885,0,45523107645,0,149251265276,0,32816373260,0}, {999999999991810,0,0,0,0,8190,0,0,0,0}, {999871653069161,0,17995344150,0,1130629500,0,108305986464,0,914970725,0}, {999834390578542,0,73321157673,0,4951,105,83842272779,0,8445985950,0}, {999811468158072,0,102506508751,0,10608953460,0,32650278532,0,42766101185,0}, {999534955792688,0,1584125406,0,857266410,2270,461145967156,0,1456846070,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999668328594775,0,91310438445,0,0,0,172719792717,0,67641174063,0}, {999523621103305,0,732410679,0,0,0,211821864986,0,263824621030,0}, {999833478470615,0,64587874560,0,15,455,99480036525,0,2453617830,0}, {999890559203793,0,4092908225,0,52932880,0,40021018006,0,65273937096,0}, {999999999998425,0,0,0,0,1575,0,0,0,0}, {999922318811103,0,1052633505,0,7828466520,0,22192699987,0,46607388885,0}, {999742381734037,0,50299023511,0,37743385680,0,148507482467,0,21068374305,0}, {999862973394044,0,819064965,0,88235799015,0,24965732996,0,23006008980,0}, {999788503430989,0,20072851860,0,32399006640,0,73738336681,0,85286373830,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999759872655279,0,1738752885,0,6430263840,0,227516704035,0,4441623961,0}, {999794965428581,0,316695305,0,46427119830,0,154018814030,0,4271942254,0}, {999733115445922,0,56464985878,0,120,8190,208948892235,0,1470667655,0}, {999903266133066,0,1099128215,0,1,0,52268837413,0,43365901305,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999581143113407,0,151687345775,0,435,0,152722046895,0,114447493488,0}, {999376081388298,0,100838137801,0,17323115643,20475,503956739893,0,1800597890,0}, {999790870585791,0,60763384500,0,0,0,143490904339,0,4875125370,0}, {999722149117029,0,2358028261,0,9975,0,275394014895,0,98829840,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999748154000897,0,17483360615,0,0,0,231082982745,0,3279655743,0}, {999805345858920,0,506971650,0,24448125,0,190964618230,0,3158103075,0}, {999747161869591,0,2514870295,0,12883005,0,172812902500,0,77497474609,0}, {999867334196886,0,57047687103,0,5168132970,0,56770214205,0,13679768836,0}, {999999999998635,0,0,0,0,1365,0,0,0,0}, {999681482838156,0,127165765203,0,108837618450,0,19946509880,0,62567268311,0}, {999874763247869,0,89171322256,0,3060,15,32760111805,0,3305314995,0}, {999541979666780,0,50378946810,0,2588166960,0,404076275730,0,976943720,0}, {999841358070819,0,124589027615,0,353500875,0,15665283320,0,18034117371,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999636517446614,0,7871542155,1,90520329915,105,265016055655,0,74625555,0}, {999761567497435,0,35845319120,0,135934683885,0,59262764806,0,7389734754,0}, {999807928592989,0,71811567885,0,2955,8295,91230539135,0,29029288740,1}, {999844130949204,0,36097360811,0,21072426390,0,98195547570,0,503716025,0}, {999999999990429,0,0,0,0,9571,0,0,0,0}, {999785961312804,0,2701069455,0,0,0,205551782790,0,5785834951,0}, {999900595355375,0,113584486,0,10935,0,98572117204,0,718932000,0}, {999719123913461,0,929735835,0,521640,0,241731737508,0,38214091556,0}, {999888380180990,0,40127710680,0,264811,19398,61320698910,0,10171125211,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999743659839469,0,12312360300,0,57882825,0,203107882651,0,40862034755,0}, {999871822818224,0,41776399386,0,4369365000,0,76201317825,0,5830099565,0}, {999795527614418,0,48628852205,0,0,0,155261103131,0,582430246,0}, {999939613182783,0,38354905,0,21693887670,0,35019411131,0,3635163511,0}, {999999999999985,0,0,0,0,15,0,0,0,0}, {999690261943684,0,170794803861,0,4354350,0,130909193584,0,8029704521,0}, {999866890892844,0,8682872885,0,14660,0,85058336510,0,39367883101,0}, {999797714539269,0,64166208450,0,7831893825,0,69332776396,0,60954582060,0}, {999517062439089,0,5729189025,0,680,0,223944202931,0,253264168275,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999850598303749,0,3583245,0,748456035,455,145533063255,0,3116593260,1}, {999651651322633,0,129862345535,0,403585,0,204169118336,0,14316809911,0}, {999660860109294,0,83302408815,0,456,45045,102968847815,0,152868588575,0}, {999805581916088,0,5335426410,0,4684680,0,99081360556,0,89996612266,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999899645499284,0,247301600,0,44833289865,0,29115898071,0,26158011180,0}, {999824277061279,0,7754663415,0,60901200360,210,99105956025,0,7961118711,0}, {999727581056310,0,61790945415,0,38326,0,139047973896,0,71579986053,0}, {999824564239979,0,212955,0,1365,3395,120418699325,0,55016842981,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999811221773639,0,21464902176,0,120,210,64092905015,0,103220418840,0}, {999945639002319,0,17024932520,0,952074060,0,29032941925,0,7351049176,0}, {999860214147279,0,3104773220,0,0,9570,56112118895,0,80568951036,0}, {999801450713394,0,4104830150,0,0,0,159372290171,0,35072166285,0}, {999999999999125,0,0,0,0,875,0,0,0,0}, {999736151456084,0,306186485,0,36141165061,0,220562533655,0,6838658715,0}, {999808594192016,0,2374447755,0,4326572250,0,183688129941,0,1016658038,0}, {999853615786235,0,93031290,0,0,0,142466744235,0,3824438240,0}, {999719665252127,0,72390003800,0,0,0,207474243153,0,470500920,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999800470131086,0,41314545853,0,65481105690,3076,66006460410,0,26727753885,0}, {999483272449588,0,93204254535,0,31663740,0,421421797397,0,2069834740,0}, {999638014022600,0,125408036145,0,54660101925,665,100717447595,0,81200391070,0}, {999820846563922,0,5045034225,0,0,0,159680470358,0,14427931495,0}, {999999999998304,0,0,0,0,1696,0,0,0,0}, {999936007566325,0,8462260620,0,100676955,0,55165893585,0,263602515,0}, {999669103557272,0,178544629200,0,87302158125,0,43532090558,0,21517564845,0}, {999772849524555,0,100785016425,0,36960,0,108119976995,0,18245445065,0}, {999728399858569,0,148823088050,0,120,121,121977721695,0,799331445,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999845313876418,0,1421880405,0,45047706075,5460,84991215706,0,23225315936,0}, {999900462133029,0,49452571455,0,475020,0,49887036705,0,197783791,0}, {999802246238486,0,88425,0,1429416,0,146126878490,0,51625365183,0}, {999710795837259,0,45025720575,0,132675648106,0,94750604385,0,16752189675,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999961856224299,0,459525,0,11403,0,23109517675,0,15033787098,0}, {999772845108431,0,14067246229,0,162949161375,105,22769136055,0,27369347805,0}, {999833937425440,0,41321954871,0,113975253,0,124026109246,0,600535190,0}, {999771435065497,0,83449725976,0,31686723915,0,100109591727,0,13318892885,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999761107095547,0,3764064634,15,21840,0,216571238904,0,18557579060,0}, {999572565478110,0,2832310995,0,848167320,0,422121585039,0,1632458536,0}, {999808013873907,0,164453364027,0,14745840,120,25444530270,0,2073485821,15}, {999692474691400,0,165106379250,0,28315489035,0,61145302147,0,52958138168,0}, {999999999999880,0,0,0,0,120,0,0,0,0}, {999530194989789,0,3152267756,0,15,0,195115668770,0,271537073670,0}, {999613447987634,0,37331084700,15,115186920240,210,233904741436,0,129265765,0}, {999929007134635,0,131682930,0,13853741265,0,46909135245,0,10098305925,0}, {999624787768900,0,55510228980,0,614872171,0,164886537529,0,154200592420,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999448542827796,0,177640519740,0,98271476775,420,273134873940,0,2410301329,0}, {999947563458323,0,697574283,0,683212755,0,16676628239,0,34379126400,0}, {999926044135733,0,13628319856,0,1,105,46438086745,0,13889457560,0}, {999785399980301,0,2927776644,0,134474567955,0,44525368545,0,32672306555,0}, {999999999981982,0,0,0,0,18018,0,0,0,0}, {999839109632213,0,117424860,0,670282670,0,160064763412,0,37896845,0}, {999775455855941,0,19433485505,0,0,15,190309718286,0,14800940253,0}, {999835834185526,0,1234919136,0,1558557015,0,160044046727,0,1328291596,0}, {999808225788448,0,2444384671,0,225,0,187428573266,0,1901253390,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999829592351509,0,15736508195,0,29900587096,1695,123670393705,0,1100157800,0}, {999924423340580,0,806563695,0,0,0,42214050055,0,32556045670,0}, {999894994608118,0,56051499525,0,210926625,1485,48179051336,0,563912911,0}, {999555837698412,0,35685547716,0,23063040,0,288521679787,0,119932011045,0}, {999999999998409,0,0,0,0,1591,0,0,0,0}, {999433901484539,0,72979630369,0,3516518460,0,488570971942,0,1031394690,0}, {999827033121484,0,1881928000,0,1607731126,8310,145913763220,0,23563447845,15}, {999922060930951,0,40919516,0,29947375815,0,21240224880,0,26710548838,0}, {999930735423071,0,35388370305,0,1276611315,1695,12533064178,0,20066529436,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999838182370205,0,5268623080,0,706500795,0,153051427385,0,2791078535,0}, {999673980499257,0,180364584120,0,36693346690,0,75505405978,0,33456163955,0}, {999829422189816,0,3474535275,0,0,0,159418699751,0,7684575158,0}, {999728064996837,0,5006028300,0,340136175,0,174403733343,0,92185105345,0}, {999999999998635,0,0,0,0,1365,0,0,0,0}, {999811707490379,0,459258555,0,0,0,172789705905,0,15043545161,0}, {999705744996405,0,1205834595,0,4702698015,9555,286662408610,0,1684052820,0}, {999711255140280,0,75655228035,0,138413773680,0,34152047360,0,40523810645,0}, {999605638290131,0,15632520255,0,62084112519,5460,313395334890,0,3249736745,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999742489153842,0,6406186185,0,28567924477,0,173389634231,0,49147101265,0}, {999804948195464,0,169236050950,0,8034845,0,16598198820,0,9209519921,0}, {999752676972087,0,6672550879,0,683212530,665,217575413146,0,22391850693,0}, {999925901534621,0,5349587460,0,1708106400,0,66363685036,0,677086483,0}, {999999999999880,0,0,0,0,120,0,0,0,0}, {999734350852296,0,26360056170,0,165754774185,0,70633350385,0,2900966964,0}, {999833781545616,0,107929371335,0,3343500615,120,21890055184,0,33055527130,0}, {999600652824061,0,124093849440,0,7074202800,0,96264653034,0,171914470665,0}, {999869185474154,0,23843119875,0,1000764765,0,86196029795,0,19774610746,665}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999815493836591,0,6017200595,0,45135090,0,134234640273,0,44209187451,0}, {999861261602404,0,115746960,0,767145,0,122226202266,0,16395681225,0}, {999576288063679,0,72248085,0,0,9555,212575049610,0,211064629071,0}, {999772432102789,0,218760550,0,4323930,0,215201936396,0,12142876335,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999935340436412,0,1216714815,0,0,0,27533744178,0,35909104595,0}, {999918302185427,0,1379560,0,890,455,59215257195,0,22481176473,0}, {999761957795759,0,19959950718,0,9549660,0,193473490997,0,24599212866,0}, {999927705825208,0,430521435,0,17797557276,8190,16516192206,0,37549895685,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999938602141886,0,4591144041,0,14190540,60060,35126486243,0,21665977230,0}, {999919058406492,0,139357195,0,52253777940,0,18949013045,0,9599445328,0}, {999548423903234,0,14881293015,0,412206795,0,257398085520,0,178884511436,0}, {999545391755466,0,6362053575,0,1159052895,0,441533148574,0,5553989490,0}, {999999999998095,0,0,0,0,1905,0,0,0,0}, {999881101766073,0,12354946215,0,891,0,86886619201,0,19656667620,0}, {999958846995172,0,17398215,15,14572950,0,21981592225,0,19139441423,0}, {999802838089372,0,222622500,0,76028727840,0,115587279798,0,5323280490,0}, {999603061053002,0,23146530,0,80430371595,4530,223204079303,0,93281345040,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999927808684366,0,476289450,0,0,9555,45217068051,0,26497948578,0}, {999927885749709,0,7323261690,0,2732850120,0,61717428778,0,340709703,0}, {999781558980594,0,3149333397,0,120,0,214337091274,0,954594615,0}, {999632591967833,0,121244880960,0,330,0,111654074066,0,134509076811,0}, {999999999999985,0,0,0,0,15,0,0,0,0}, {999940988552287,0,3172209288,0,226951740,0,55308685905,0,303600780,0}, {999848183315749,0,47684809006,0,0,105,94046136560,0,10085738580,0}, {999867298900751,0,211536083,0,64365161445,0,42229268806,0,25895132915,0}, {999930917137779,0,11987272150,0,0,210,55397508661,0,1698081200,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999793452069055,0,19561935890,0,17658515,0,186050342715,0,917993825,0}, {999853326843460,0,4200,0,15,0,98637994110,0,48035158215,0}, {999808256596347,0,442545620,0,53603550,225,186025292585,0,5221961673,0}, {999714279104009,0,83050965525,0,107633360835,0,65809207071,0,29227362560,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999913208434467,0,39127551155,0,2218737885,0,36206084928,0,9239191565,0}, {999840404058847,0,31466723195,0,101684520,0,124932784265,0,3094749173,0}, {999822676394392,0,56184757475,0,9828,0,90230754335,0,30908083970,0}, {999736399903058,0,122520058445,0,71583046095,0,13827405447,0,55669586955,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999782267272463,0,88896381,0,15,0,201139118180,0,16504712961,0}, {999610874876853,0,30496740125,0,7210985175,0,351181594076,0,235803771,0}, {999880575428628,0,57426070362,0,17746,105,30892101411,0,31106381748,0}, {999890794221530,0,328862370,0,0,0,99645983100,0,9230933000,0}, {999999999999985,0,0,0,0,15,0,0,0,0}, {999706213749437,0,27919681170,0,13009170438,0,237137667925,0,15719731030,0}, {999834399605219,0,228165,0,8235045,0,123812459871,0,41779471700,0}, {999804083407832,0,25592489600,0,116537270850,0,42727525277,0,11059306441,0}, {999783904545530,0,72435021339,0,20070014965,0,116088271791,0,7502146375,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999857468770454,0,30639243945,0,13290412815,0,98408242886,0,193329900,0}, {999875931215710,0,5903773365,0,397567170,0,108457863040,0,9309580715,0}, {999809257696206,0,15296059173,0,1575134330,0,167290096066,0,6581014210,15}, {999772546849104,0,587288661,0,15,0,224043365575,0,2822496645,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999741004411534,0,92409766400,0,80094463215,0,72139489276,0,14351869575,0}, {999690683284640,0,1021986765,0,120045,210,254892215810,0,53402392530,0}, {999781431895475,0,49387427940,0,892536375,0,163224281700,0,5063858510,0}, {999958910116336,0,522776003,0,943002060,120,16558687771,0,23065417710,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999914448568464,0,58599994680,0,2154602115,16380,12961450981,0,11835367380,0}, {999844791006360,0,2128571460,0,3045,0,134644539033,0,18435880102,0}, {999925889227447,0,16647113598,0,6430263855,0,46425469605,0,4607925495,0}, {999809775690436,0,11810835,0,3643005,0,131958554089,0,58250301635,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999956088482815,0,7836200,0,8092126770,0,35148856190,0,662698025,0}, {999948805497856,0,465683610,0,225,4095,44465613694,0,6263200520,0}, {999939503181495,0,570410,0,9990,0,39750100595,0,20746137510,0}, {999664118490676,0,177751208370,0,7282290,420,153384751366,0,4738266878,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999873476095326,0,243356040,0,937345500,0,103848548835,0,21494654299,0}, {999822679978624,0,66392345985,0,15651034351,0,64720151920,0,30556489120,0}, {999938030342446,0,25957870830,0,504203700,0,27172163375,0,8335418984,665}, {999612367512924,0,31245283645,0,82364393475,0,267734635506,0,6288174450,0}, {999999999989080,0,0,0,0,10920,0,0,0,0}, {999633084632695,0,3751631151,0,512311800,0,361209131145,0,1442293209,0}, {999868129689735,0,3610962755,0,76915020,0,70187284520,0,57995146395,1575}, {999698878739304,0,86174069475,0,330330,0,201945815316,0,13001045575,0}, {999897585891409,0,54008811675,0,13114920,0,35220653700,0,13171528296,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999845243253042,0,4967890020,0,0,210,94915174228,0,54873682500,0}, {999763295728097,0,162428000490,0,31822851060,0,41216618150,0,1236802203,0}, {999756286780562,0,73860360,0,5085039960,0,201533981008,0,37020338110,0}, {999930246047266,0,134971200,0,29546667696,0,24906269553,0,15166044285,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999683675303919,0,2423540,0,2282280,0,148146431796,0,168173558465,0}, {999745977171755,0,70278477570,0,0,0,130726924755,0,53017425920,0}, {999418413461765,0,189461493470,0,129198147015,0,258813916490,0,4112981260,0}, {999900411444525,0,4039035,0,23195055,0,97352023675,0,2209297710,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999801383884911,0,931214130,0,72538476465,1,117397539623,0,7748884870,0}, {999704159491632,0,7185777965,0,159916537365,0,93651730830,0,35086462208,0}, {999968710135426,0,8675075670,0,140324940,241,19954660983,0,2519802740,0}, {999788324354295,0,83597177575,0,0,0,76856224495,0,51222243635,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999806507220530,0,5576566415,0,0,0,167086189480,0,20830023575,0}, {999910766546242,0,4096079187,0,2300705,1,81493836015,0,3641237850,0}, {999581433405395,0,106728273060,0,1785,0,129785808475,0,182052511285,0}, {999827894089921,0,97332960,0,17535696360,15,150028254318,0,4444626426,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999671249132364,0,10262841606,0,65874528720,1365,135673562600,0,116939933345,0}, {999850409604890,0,33329730,0,0,0,148014184370,0,1542881010,0}, {999893314998110,0,205731435,0,225,0,104094774575,0,2384495655,0}, {999841361109955,0,105286728540,0,831426275,0,52100228035,0,420507195,0}, {999999999998620,0,0,0,0,1380,0,0,0,0}, {999554400470249,0,163855428030,0,35598162600,0,245988187728,0,157751393,0}, {999683290728005,0,509052210,0,0,0,249058551260,0,67141668525,0}, {999501685924435,0,67340281765,0,271476780,0,429661973925,0,1040343095,0}, {999873160091006,0,13863438345,0,18219175,0,57653342591,0,55304908883,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999840437008166,0,3691466058,0,0,226,146798258410,0,9073267140,0}, {999891134816879,0,68174987875,0,2292907855,0,15707769690,0,22689517701,0}, {999685566261934,0,21026458245,0,210,8190,289957198021,0,3450073400,0}, {999939231030560,0,12588114365,0,160137705,0,47240324175,0,780393195,0}, {999999999999894,0,0,0,0,106,0,0,0,0}, {999680230009071,0,211982407410,0,13945932000,0,40337844949,0,53503806570,0}, {999723314750136,0,120090884025,0,210,0,141209992079,0,15384373550,0}, {999715632026176,0,810281346,0,158611282830,0,54622970403,0,70323439245,0}, {999620855027335,0,18075706194,0,8378125281,1,351991931894,0,699209295,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999792119735039,0,78960397638,0,564684120,0,128277921690,0,77261513,0}, {999949427707805,0,27544521715,0,77837775,0,21580624765,0,1369307940,0}, {999932495224239,0,33215419658,0,125580,0,34151417168,0,137813355,0}, {999736511480575,0,34258480380,0,145569824400,0,64907630710,0,18752583935,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999761863978579,0,33123009705,0,115328863650,0,66262477776,0,23421670290,0}, {999741228121725,0,26052414515,0,0,0,225067526255,0,7651937505,0}, {999846584944807,0,11860236018,0,34799531130,0,88133299875,0,18621988170,0}, {999970495794498,0,218675,0,0,0,12601407207,0,16902579620,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999753954614095,0,84624160635,0,1179285345,210,111270010560,0,48971929155,0}, {999902237667387,0,17751045978,0,322972650,0,79109495215,0,578818770,0}, {999786794434363,0,1266318900,0,225,1,206065551450,0,5873695061,0}, {999846165497444,0,63902604515,0,450,0,81144108426,0,8787789165,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999822599266377,0,122169521805,0,8766027270,0,18829420273,0,27635764275,0}, {999806861537877,0,3312336380,0,11220540,13651,183433786558,0,6381104994,0}, {999568585448940,0,925887865,0,435014580,0,429351078480,0,702570135,0}, {999852667361495,0,4968501720,0,97192080,0,114255613080,0,28011331625,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999764495536027,0,122720245095,0,17016613020,0,40428432195,0,55339173663,0}, {999699730262935,0,64726438885,0,0,0,159142258080,0,76401040100,0}, {999834985185675,0,84946051725,0,502341840,0,72951144385,0,6615276375,0}, {999545397387100,0,602002765,0,0,0,199553323295,0,254447286840,0}, {999999999998425,0,0,0,0,1575,0,0,0,0}, {999851857397655,0,65797180035,0,0,0,81381789758,0,963632552,0}, {999942725156229,0,28761930,0,6288645090,2730,47747855683,0,3209578338,0}, {999917792743564,0,2503835895,0,26966940,0,30239222496,0,49437231105,0}, {999892673806625,0,31914023505,0,37703505840,0,36669797110,0,1038866920,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999946847372270,0,32155614940,0,0,121,20085425969,0,911586700,0}, {999929938453767,0,884914695,0,3084378795,0,23427510048,0,42664742695,0}, {999944551304782,0,130818870,0,120,120,19374732590,0,35943143518,0}, {999809127168024,0,36906877498,0,32248796580,0,101872877913,0,19844279985,0}, {999999999999879,0,0,0,0,121,0,0,0,0}, {999865023129264,0,729494235,0,95266800720,0,21268982733,0,17711593048,0}, {999798820852615,0,4442963645,0,64600106445,785,96216082860,0,35919993650,0}, {999840734220219,0,25270167518,0,25913607720,0,44149819113,0,63932185430,0}, {999866269332028,0,36202785,0,314837005,1,133347365666,0,32262515,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999698951934070,0,144969556425,0,0,0,146287911420,0,9790598085,0}, {999828301549402,0,604297275,0,2563781220,0,166901324115,0,1629047988,0}, {999799851522845,0,148445365355,0,1785,0,46313273595,0,5389836420,0}, {999824180556542,0,120170610,0,29679838188,0,144464326945,0,1555107715,0}, {999999999999320,0,0,0,0,680,0,0,0,0}, {999763906112697,0,65091873798,0,15,0,170315894875,0,686118615,0}, {999861105024504,0,8137007718,0,0,0,130500501910,0,257465868,0}, {999941672610730,0,475074225,0,0,0,31559773845,0,26292541200,0}, {999791849366977,0,26844899655,0,403132710,8190,155868806893,0,25033785575,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999621644743674,0,44022189393,0,14774760,785,229341768083,0,104976523305,0}, {999634981417440,0,137480098995,0,15,0,132500050225,0,95038433325,0}, {999773018620813,0,47038618575,0,2865604770,121,170559170121,0,6517985600,0}, {999450067067625,0,75643476865,0,8619030420,0,464893724865,0,776700225,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999838653339944,0,40686520695,0,0,0,118719970721,0,1940168640,0}, {999943749144013,0,31309425,0,21404135745,121,17702632521,0,17112778175,0}, {999765393425147,0,3542647983,0,1785,0,231042133010,0,21792075,0}, {999699834200935,0,78308555535,0,91050828975,120,115062625686,0,15743788749,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999762036692785,0,15830396715,0,13952301090,0,207064561160,0,1116048250,0}, {999794697358547,0,11280341520,0,0,0,192685766460,0,1336533473,0}, {999704701992788,0,150641729973,0,41953201290,0,86893562864,0,15809513085,0}, {999821196291692,0,175987905,0,98484360,0,173632301055,0,4896934988,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999721306366947,0,1594443515,0,15,0,178375967010,0,98723222513,0}, {999768214910317,0,63067301430,0,0,105,148082498388,0,20635289760,0}, {999858675997070,0,73905986715,0,3045050190,0,57046247700,0,7326718325,0}, {999796862221152,0,63767385,0,0,210,195874755280,0,7199255973,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999442084894282,0,139435760380,0,691892580,300300,215998601798,0,201788550660,0}, {999756285441130,0,83221968216,0,102832441530,0,14678275369,0,42981873755,0}, {999910294325730,0,59412944970,0,1384503135,120,28326260265,0,581965780,0}, {999878425036876,0,101301424618,0,680,0,17252168795,0,3021369031,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999603038886768,0,54308007998,0,862140825,0,341250667390,0,540297019,0}, {999838881578130,0,18704458073,0,0,0,86467697061,0,55946266736,0}, {999853067005439,0,127931629376,0,79493505,0,9593882545,0,9327989135,0}, {999977902256595,0,1418392010,0,951599040,120,19014690620,0,713061615,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999952341271871,0,1047643231,0,1931079150,210,44270905483,0,409100055,0}, {999704988148354,0,2996980890,0,79750671000,0,212238279705,0,25920051,0}, {999910750416299,0,5828012425,0,611148735,15,82461747405,0,348675121,0}, {999772086123299,0,20094743035,0,163774550940,0,41332978016,0,2711604710,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999867518860024,0,50523170880,0,211,0,64232873930,0,17725094955,0}, {999663929337729,0,82704504575,0,7565543520,0,62460797666,0,183339816510,0}, {999896466462700,0,26821939630,0,12729491775,0,63485263415,0,496842480,0}, {999882000403273,0,23595220705,0,14303590665,0,67233904757,0,12866880600,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999954436819179,0,2926333050,0,0,2850,22709641570,0,19927203351,0}, {999804539175514,0,2953105410,0,0,0,188878733525,0,3628985551,0}, {999867494876860,0,45744860,0,1150710,0,101379265795,0,31078961775,0}, {999909794678749,0,72206435,0,1366,0,89943721590,0,189391860,0}, {999999999999565,0,0,0,0,435,0,0,0,0}, {999742753267330,0,274231545,0,1430900,0,236277318055,0,20693752170,0}, {999755611526292,0,28634893486,0,76328737485,2955,110329182600,0,29095657167,15}, {999915702330139,0,30931970475,0,720825,0,39966135951,0,13398842610,0}, {999962951565279,0,497922196,0,0,3075,21034439670,0,15516069675,105}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999888724253329,0,2771314455,0,1014136515,0,3424740180,0,104065555521,0}, {999760703342055,0,18456614610,0,15091440,0,179162476825,0,41662475070,0}, {999905720453399,0,29059675415,0,17492236546,0,45022383150,0,2705251490,0}, {999893040265080,0,43622716020,0,1508827320,0,57916063955,0,3912127625,0}, {999999999999985,0,0,0,0,15,0,0,0,0}, {999844663403844,0,25836369240,0,0,0,129220571446,0,279655470,0}, {999835604557543,0,78440086860,0,470,0,83784191267,0,2171163860,0}, {999953203826724,0,15395835,0,25213519695,0,18701423345,0,2865834401,0}, {999499153844209,0,114317016626,0,63190747620,0,271478496915,0,51859894630,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999519469892465,0,2534040970,0,795314520,680,474452479545,0,2748271820,0}, {999750776918205,0,139977889445,0,32162130,0,104536814630,0,4676215590,0}, {999862922113617,0,22730,0,6233942925,0,126727087613,0,4116833115,0}, {999879780843155,0,5994574440,0,1905,0,83689176755,0,30535403745,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999859704171463,0,39358493125,0,4905851615,0,44135580792,0,51895903005,0}, {999795183454633,0,228273420,0,108649150675,120,87016644732,0,8922476420,0}, {999537739019600,0,5174831025,0,120,0,228323854090,0,228762295165,0}, {999929339322284,0,3044870340,0,62614364685,120,4277923431,0,723519140,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999859392942149,0,88986613325,0,56035980,0,44648827005,0,6915581541,0}, {999863545742378,0,114660,0,748456021,0,134279049643,0,1426637298,0}, {999928154640712,0,5205150615,0,379321800,0,66260518860,0,368013,0}, {999705263101885,0,135564806061,0,75075,0,152025328849,0,7146688130,0}, {999999999999335,0,0,0,0,665,0,0,0,0}, {999681261016594,0,89757762390,0,0,0,87566016725,0,141415204291,0}, {999943954724870,0,5965925420,0,33286678425,15,14381283360,0,2411387910,0}, {999847227630151,0,2694625275,0,2657655,0,71791595724,0,78283491195,0}, {999934327090164,0,1743543795,0,970494540,0,62584682685,0,374188816,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999933411663405,0,10268004453,0,180180,0,52678954811,0,3641197151,0}, {999911197065466,0,85954050,0,49503113205,0,21633806529,0,17580060750,0}, {999674869351596,0,915493691,3003,837992625,1365,317977666875,0,5399490845,0}, {999842697669997,0,9993953585,0,47865416235,0,93105414958,0,6337545225,0}, {999999999999985,0,0,0,0,15,0,0,0,0}, {999804635575721,0,34372500411,0,11508,0,107876746340,0,53115166020,0}, {999942029620575,0,3746663115,0,31036111,0,39972708559,0,14219971640,0}, {999844122851767,0,19320,0,105,0,110829056550,0,45048072258,0}, {999916359298141,0,969341835,0,6841674840,0,71090705779,0,4738979405,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999780449072553,0,55285198365,0,70922676825,1365,72498660267,0,20844390625,0}, {999856494807697,0,10826152155,0,15,0,64817023463,0,67862016670,0}, {999955446409584,0,2669690805,0,1575,0,10608394301,0,31275503735,0}, {999949697200427,0,22082703105,0,644053620,0,22887065827,0,4688977021,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999909453955418,0,1466395206,0,0,0,37648680236,0,51430969140,0}, {999850832012275,0,60667747210,0,40950,0,72421534305,0,16078665260,0}, {999849193529857,0,1954684215,0,0,0,115377131298,0,33474654630,0}, {999839312798454,0,58992570,0,0,0,27919692600,0,132708516376,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999724535350571,0,23389158,0,59692263540,2835,215735455595,0,13538301,0}, {999768479776351,0,198789801,0,44960525610,0,182312600580,0,4048307658,0}, {999663153025023,0,20022131836,0,16367567580,9555,300271140311,0,186125695,0}, {999836968116864,0,1647713096,0,9512242740,0,151460393435,0,411533865,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999881000623308,0,49156293,0,0,0,114439770435,0,4510449964,0}, {999769500996041,0,30034499498,0,1531635,5460,140334209631,0,60128757735,0}, {999750467493079,0,83755580133,0,0,0,165615478077,0,161448711,0}, {999772818590299,0,14221641750,0,22819106310,0,163314645770,0,26826015871,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999800419386909,0,55125,0,196396200,0,198807716176,0,576445590,0}, {999839659761854,0,22397327796,0,86644973415,0,37111782225,0,14186154710,0}, {999788958396832,0,25164610590,0,91455330,15,161702469900,0,24083067333,0}, {999558012740960,0,89894933730,0,15,0,351046338680,0,1045986615,0}, {999999999991810,0,0,0,0,8190,0,0,0,0}, {999732988814835,0,96948466680,0,38110493850,0,77708529485,0,54243695150,0}, {999649354439359,0,8025471090,0,92591787,0,209246734916,0,133280762848,0}, {999874094836210,0,3396286215,0,0,0,114684188205,0,7824689370,0}, {999943544528957,0,5143713213,0,1935404835,8190,49356523170,0,19821635,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999776938152551,0,72483120,0,0,2940,220901621143,1,2087740245,0}, {999964155069911,0,4248077595,0,17343691,0,31387346335,0,192162468,0}, {999757637188811,0,5304837331,0,172758915,0,30834916045,0,206050298898,0}, {999763119133058,0,118628984985,0,72322645395,0,33322430452,0,12606806110,0}, {999999999997164,0,0,0,0,2836,0,0,0,0}, {999839533762032,0,62929538975,0,11403,0,78475165309,0,19061522281,0}, {999779273968031,0,45069326865,0,137291700,105,171862877233,0,3656536066,0}, {999792450030374,0,120202084485,0,15,0,86638254386,0,709630740,0}, {999815270353051,0,21469184100,0,0,0,139699849070,0,23560613779,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999827385824579,0,147770529975,0,99908446,0,10205016425,0,14538720575,0}, {999893394877524,0,574545420,0,34163584695,0,60710195056,0,11156797305,0}, {999900714592779,0,1217222370,0,0,2730,81598237590,0,16469944531,0}, {999913226062627,0,44386656405,0,114660,0,42228716763,0,158449545,0}, {999999999999335,0,0,0,0,665,0,0,0,0}, {999839114443173,0,15765,0,655748,0,123890635434,0,36994249880,0}, {999932003932949,0,40695170336,0,8420641776,0,11344904991,0,7535349948,0}, {999733538916456,0,26394504466,0,156794858220,0,75844157770,0,7427563088,0}, {999966568631253,0,1840486,0,2106653640,0,31239815463,0,83059158,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999925365103042,0,6951914376,0,0,225,19048452224,0,48634530133,0}, {999964018519206,0,131715,0,3045,0,17399265150,0,18582080884,0}, {999825514058368,0,1389823830,0,31975331115,15,134049969341,0,7070817331,0}, {999817496907189,0,20635842390,0,135183513465,0,11297813866,0,15385923090,0}, {999999999994435,0,0,0,0,5565,0,0,0,0}, {999873907305891,0,38787156409,0,12345375,0,87005646465,0,287545860,0}, {999837609347019,0,13373548420,0,31300880535,0,50619693206,0,67096530820,0}, {999837091128547,0,60833243933,0,26769577800,0,63392715277,0,11913334443,0}, {999813919362979,0,33243736500,0,686455771,682110,138250035425,0,13899727215,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999669903431784,0,18894924405,0,94191217575,210,207035853226,0,9974572800,0}, {999775816422232,0,1280683005,0,2940,0,214312262838,0,8590628985,0}, {999962722498356,0,1303185,0,1776232200,0,34247233369,0,1252732890,0}, {999610269756109,0,1540109056,0,373753380,0,387047783790,0,768597665,0}, {999999999999790,0,0,0,0,210,0,0,0,0}, {999823173601058,0,155849532790,0,9014580,0,20188446379,0,779405193,0}, {999730795315579,0,47860306515,0,161070,15,210946658466,0,10397558355,0}, {999699527961473,0,168015109893,0,29651054370,0,44175808229,0,58630066035,0}, {999773628555730,0,11612720100,0,20962305,0,197243992360,0,17493769505,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999863414042476,0,18365089743,0,0,1,116735968390,0,1484899390,0}, {999571049975175,0,2654531880,0,0,0,175575142270,0,250720350675,0}, {999776008573530,0,130633634250,0,56128772700,0,35134828330,0,2094191190,0}, {999617189961955,0,37923167100,0,123274112535,0,221557967397,0,54791013,0}, {999999999999999,0,0,0,0,1,0,0,0,0}, {999950297843127,0,56213535,0,16428218625,0,26307907483,0,6909817230,0}, {999928255794832,0,61116998040,0,61786650,210,9451547463,0,1113872805,0}, {999636979607300,0,57497668950,0,522080940,0,152201125610,0,152799517200,0}, {999703182135879,0,4702845,0,105,1,154373275524,0,142439885646,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999839133329886,0,92401426683,0,0,1365,66306986805,0,2158255261,0}, {999502763753329,0,170412842955,0,91516961070,0,232097163971,0,3209278675,0}, {999805645173951,0,11166261016,0,0,0,116269349430,0,66919215603,0}, {999972975885884,0,446141585,0,644413785,0,8824501081,0,17109057665,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999930284566013,0,15305235095,0,0,0,30093672567,0,24316526325,0}, {999891052489664,0,44223387000,0,3798584791,105,45696567795,0,15228970645,0}, {999791278636875,0,2582281585,0,133715102430,0,48268494645,0,24155484465,0}, {999854363135409,0,5242999050,0,24114720630,210,114046305811,0,2232838890,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999803816654941,0,106202103840,0,1365,0,41823902363,0,48157337491,0}, {999885052406199,0,62786025,0,487638936,0,114385487485,0,11681355,0}, {999872878477334,0,9747967740,0,0,0,112219459801,0,5154095125,0}, {999821106446120,0,10135585425,0,0,0,157414409365,0,11343559090,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999891876334319,0,730270390,0,458558101,0,106540585470,0,394251720,0}, {999611610596125,0,70995860565,0,2045,165165,131748015204,0,185645360896,0}, {999834966388810,0,1776187140,0,15,0,162481792640,0,775631395,0}, {999813492178134,0,161651858100,0,680,0,8540603171,0,16315359915,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999748402328819,0,25090026330,0,15,210,195483064211,0,31024580415,0}, {999859142530887,0,8651763121,0,18015917010,0,113596157502,0,593631480,0}, {999851971133893,0,55433865,0,0,120,147319889301,0,653542821,0}, {999954779020038,0,309451415,0,0,0,28098258962,0,16813269585,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999902343521216,0,62395370499,0,136906770,0,34865737400,0,258464115,0}, {999823618951727,0,112644575905,0,124488,0,46796470385,0,16939877495,0}, {999634185658494,0,24185707455,0,7567560,0,244792586561,0,96828479930,0}, {999583121545745,0,171771618000,0,15473626350,1365,229589968650,0,43239890,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999918934932382,0,156290,0,3060,1575,80819387130,0,245519563,0}, {999515451604718,0,55900729982,0,1179283560,0,426961224533,0,507157207,0}, {999759999448811,0,164716947213,0,330331,0,73433110805,0,1850162840,0}, {999858174116995,0,583444800,0,999893895,0,129073215590,0,11169328720,0}, {999999999999879,0,0,0,0,121,0,0,0,0}, {999948239141457,0,13335688,0,21528356230,0,12403946970,0,17815219655,0}, {999889866193345,0,3873828273,0,42525,1380,91561753587,0,14698180890,0}, {999933898446178,0,44440592208,0,895182060,0,7221510424,0,13544269130,0}, {999957509797400,0,100690920,0,4153809660,1680,14775128220,0,23460572120,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999933821198725,0,21333886340,0,172202940,0,42603412525,0,2069299470,0}, {999867182752522,0,6284363730,0,401531130,0,124394068880,0,1737283738,0}, {999896148475578,0,14727525,0,3706316315,0,97028723655,0,3101756927,0}, {999714888169385,0,193016944050,0,20127547440,0,43013443825,0,28953895300,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999867652210235,0,3342775815,0,0,0,125957990555,0,3047023395,0}, {999777334653269,0,568533840,0,147623035560,0,27216709715,0,47257067616,0}, {999716423775560,0,4323338565,0,369134220,0,171864423870,0,107019327785,0}, {999650332024305,0,21884118720,0,438964320,0,317189961695,0,10154930960,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999964368276204,0,1027640685,0,15,0,31458564375,0,3145518721,0}, {999836570710132,0,269919783,0,0,0,144527067780,0,18632302305,0}, {999948085178835,0,32431983450,0,125411730,0,17543589960,0,1813836025,0}, {999747892396414,0,902256110,0,1809457650,0,248591675491,0,804214335,0}, {999999999999670,0,0,0,0,330,0,0,0,0}, {999776154443869,0,42644725341,0,125121511515,0,31650159942,0,24429159333,0}, {999901631614572,0,52751874175,0,15,6306435,43164453685,0,2445751118,0}, {999676632640056,0,12535511625,0,66058402410,0,243187053105,0,1586392804,0}, {999800814136613,0,25717993051,0,89678604016,1590,53599243050,0,30190021680,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999869695524904,0,5719841855,0,16516980480,0,39008349376,0,69059303385,0}, {999840004833375,0,4802076105,0,22536204600,0,102989181880,0,29667704040,0}, {999776887439993,0,81951892740,0,0,0,64427568011,0,76733099256,0}, {999827984495279,0,158723787213,0,0,0,9345788628,0,3945928880,0}, {999999999998425,0,0,0,0,1575,0,0,0,0}, {999816005815402,0,4227203610,0,582982400,0,166301422733,0,12882575855,0}, {999983994996454,0,4982306446,0,0,0,8921293805,0,2101403295,0}, {999945601444296,0,5272179293,0,593422830,0,48064096301,0,468857280,0}, {999893131124891,0,36810542630,0,0,0,9984139714,0,60074192765,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999895504342334,0,41414378175,0,345,0,59748119800,0,3333159346,0}, {999746982994439,0,13255187030,0,180570570180,0,57495007176,0,1696241175,0}, {999737871876458,0,123462587445,0,41556039736,0,87449470655,0,9660025706,0}, {999846121710945,0,116831530845,0,2842925085,0,11356755560,0,22847077565,0}, {999999999999880,0,0,0,0,120,0,0,0,0}, {999626159871294,0,101603447400,0,3515380260,0,94554126046,0,174167175000,0}, {999603914400874,0,195513360,0,151561410,330,395499944811,0,238579215,0}, {999891896419163,0,17701730865,0,1303908606,0,78609642685,0,10488298681,0}, {999910824191054,0,2920332481,0,105,120,31029418780,0,55226057460,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999882816592946,0,442056828,0,59824159395,5460,32844996776,0,24072188595,0}, {999871261536261,0,3219093633,0,50720670,0,101610259680,0,23858389756,0}, {999799047281164,0,48065925066,0,0,0,113797703210,0,39089090560,0}, {999899506705929,0,55545455,0,46410,0,92781672461,0,7656029745,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999588644711376,0,24164868,0,0,0,204097458165,0,207233665591,0}, {999868368377874,0,680,0,0,0,92142003551,0,39489617895,0}, {999803277350820,0,48949895,0,11505585,0,191073841265,0,5588352435,0}, {999865099543616,0,51091580750,0,0,0,82627372549,0,1181503085,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999724996719264,0,62693030766,0,379321800,15,180935747428,0,30995180727,0}, {999951005033651,0,630772221,0,0,0,20743967753,0,27620226375,0}, {999892408909550,0,9524890830,0,176486730,15,96649888715,0,1239824160,0}, {999940840278917,0,209055,0,120,0,43287931583,0,15871580325,0}, {999999999999790,0,0,0,0,210,0,0,0,0}, {999784019000295,0,26570446910,0,1397775,0,168112680220,0,21296474800,0}, {999877017160247,0,976584170,0,90300,0,121880781978,0,125383305,0}, {999944064901140,0,248509460,0,8134521060,0,14953205780,0,32598862560,0}, {999713396107744,0,202198875845,0,989863875,0,83401311436,0,13841100,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999802952613657,0,34605353520,0,54872197380,0,98482142863,0,9087692580,0}, {999951829555590,0,3352202805,0,2078505,0,27491966455,0,17324196645,0}, {999873432731169,0,4636545760,0,0,0,118064776761,0,3865946310,0}, {999923769801844,0,106226720,0,56731193610,0,11874472455,0,7518305371,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999654647945894,0,8329153875,0,283558275,0,189344605461,0,147394736495,0}, {999878609552345,0,29948515175,0,10908654120,0,34568664390,0,45964613970,0}, {999584891418206,0,3951997405,0,503993490,0,407652905706,0,2999685193,0}, {999866850796561,0,10586385,0,105387882810,0,27584205993,0,166528251,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999918909453855,0,2078505,0,660870,0,21482147145,0,59605659625,0}, {999886170638616,0,13070391421,0,15,0,88354390765,0,12404579183,0}, {999840333868546,0,853892750,0,3322158840,0,153692829976,0,1797249888,0}, {999975334373963,0,3667800,0,1161825,0,15218309339,0,9442487073,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999841350274666,0,62412470,0,51840514635,0,104799024525,0,1947773704,0}, {999780760077041,0,88751854780,0,17624900685,210,56130474224,0,56732693060,0}, {999624786370974,0,4064025,0,99226822905,0,213586012636,0,62396729460,0}, {999754601845465,0,90506860080,0,0,1575,154401822350,0,489470530,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999899116549866,0,753576090,0,210,0,84003079653,0,16126794181,0}, {999955972896366,0,216592740,0,0,0,27018600099,0,16791910795,0}, {999762661077714,0,2510654055,0,210,0,199997358220,0,34830909801,0}, {999950934586950,0,4182734300,0,2655252600,0,41990152673,0,237273477,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999800020868190,0,2268722705,0,15,0,197300361410,0,410047680,0}, {999712480037850,0,288596805,0,3060,0,127998454890,0,159232907395,0}, {999671784313915,0,117787536330,0,30,0,96145580320,0,114282569405,0}, {999626426395995,0,81971941545,0,53916594335,420,237360006470,0,325061235,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999477345780938,0,76701762806,0,17036141956,2730,427990181250,0,926130320,0}, {999959576724661,0,3023745530,0,32852820,0,37205065069,0,161611920,0}, {999802942521000,0,107880140139,0,38610000,0,64909789560,0,24228939301,0}, {999893875027351,0,33085739505,0,0,0,68420802814,0,4618430330,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999876085874341,0,88710315,0,65690637870,0,40793581328,0,17341196146,0}, {999788983032217,0,952638120,0,680,0,210024186478,0,40142505,0}, {999955328019838,0,8048774370,0,0,0,35727598272,0,895607520,0}, {999882756957967,0,6642153080,0,0,150150,75133800147,0,35466938656,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999940702747229,0,3762034824,0,0,90300,55407635357,0,127492290,0}, {999866216241136,0,11201434885,0,64324275,0,122161859681,0,356140023,0}, {999806769627825,0,9805097115,0,0,0,181508800295,0,1916474765,0}, {999867918333114,0,105,0,0,0,96763358971,0,35318307810,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999832851217524,0,142916910,0,187297110,0,157878358315,0,8940210141,0}, {999863016628310,0,40849757160,0,0,455,80654242215,0,15479371860,0}, {999752251310054,0,58767959970,0,88798725015,0,79168387501,0,21013617460,0}, {999733214726325,0,1887991980,0,7387380,0,171494917650,0,93394976665,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999826059519194,0,246472800,0,210,8190,173693906930,0,92675,1}, {999907952480799,0,50245231855,0,1358611800,0,35218041935,0,5225633611,0}, {999910486448455,0,8616474603,0,244679191,1575,80314900871,0,337495305,0}, {999870846397748,0,26257534656,0,60442200,0,101387635080,0,1447990316,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999879661108331,0,31490396210,0,0,0,66703695774,0,22144799685,0}, {999925437621978,0,33032448555,0,1634712170,1575,39895194370,0,21352,0}, {999802383252297,0,84422001300,0,65900586571,0,7397097024,0,39897062808,0}, {999845604856499,0,88844571615,0,127698480,0,17582359095,0,47840514311,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999899976553309,0,75469165905,0,0,0,18255200435,0,6299080351,0}, {999819725333969,0,31232880,0,0,0,166845617570,0,13397815581,0}, {999508177775170,0,10950024540,0,33229770,0,455835387935,0,25003582585,0}, {999678562669784,0,28912780865,0,2927882686,0,289458804465,0,137862200,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999915913737932,0,43048588695,0,1365,0,20948113750,0,20089558258,0}, {999906552635519,0,81044883591,0,413775180,0,4251884975,0,7736820735,0}, {999916984354220,0,206565900,0,0,0,72569521265,0,10239558615,0}, {999895801469784,0,300660481,0,37478581140,0,57427914990,0,8991373605,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999899290947051,0,58006253165,0,1786,0,18989148327,0,23713649671,0}, {999758881452155,0,21766402905,0,10166987730,0,198439711820,0,10745445390,0}, {999728317606699,0,3956486725,0,48932924040,0,218774894010,0,18088526,0}, {999827796114290,0,47985,0,3599115,0,122181314375,0,50018924235,0}, {999999999999999,0,0,0,0,1,0,0,0,0}, {999814665254434,0,13751785101,0,141683086545,0,25290859755,0,4609014165,0}, {999692835365766,0,179186579355,0,1,5460,118619054064,0,9358995354,0}, {999837150632979,0,71172575566,0,11744868135,0,75345972135,0,4585951185,0}, {999871355868819,0,35017902480,0,210,1575,83384814360,0,10241412556,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999947103208505,0,16390426965,0,2792549760,0,26157811219,0,7556003551,0}, {999909868032505,0,22769305630,0,8411157756,0,58774759589,0,176744520,0}, {999751606671526,0,106058544075,0,23929564935,0,117064466865,0,1340752599,0}, {999921488865481,0,3383751820,0,300570270,0,70538744799,0,4288067630,0}, {999999999998425,0,0,0,0,1575,0,0,0,0}, {999812377219979,0,20341150651,0,613407795,0,163310745115,0,3357476460,0}, {999809949119546,0,3330210,0,244680765,0,189418772825,0,384096654,0}, {999789900934043,0,590851425,0,0,0,208108909187,0,1399305345,0}, {999968941833980,0,10001265615,0,4911031125,0,16015586935,0,130282345,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999908834780475,0,5717075,0,0,0,90813789320,0,345713130,0}, {999812380409112,0,51765744450,0,68712949995,0,59947770670,0,7193125773,0}, {999791199523402,0,45651616740,0,646277835,1,147069317525,0,15433264497,0}, {999715865374476,0,310697625,0,275760,0,253335502521,0,30488149618,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999829412187465,0,28609761470,0,1319055675,0,135233062805,0,5425932585,0}, {999936773369614,0,16093387290,0,2583945,4201,29313003380,0,17817651570,0}, {999976078149565,0,131492340,0,645705060,0,8151464295,0,14993188740,0}, {999838141885872,0,4796279113,0,5903188215,0,81695385540,0,69463261260,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999836761210496,0,473142090,0,2479216740,0,160205479334,0,80951340,0}, {999936495429510,0,50252925480,0,814043700,0,6267525285,0,6170076025,0}, {999760460148807,0,18872755546,0,15918630,0,153653176500,0,66998000517,0}, {999889484839499,0,1159526551,0,680,0,98481414965,0,10874218305,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999942716808689,0,17358913515,0,2563781220,0,34011469955,0,3349026621,0}, {999877507803896,0,95595318,0,52240788600,0,50511700941,0,19644111245,0}, {999847528702540,0,6575251,0,1440105,0,112605831778,0,39857450326,0}, {999822256708149,0,29902040075,0,0,0,147746776380,0,94475396,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999901551291899,0,104556900,0,35505,0,90948479275,0,7395636421,0}, {999970857454906,0,3025171,0,9390381000,0,19232205623,0,516933300,0}, {999875956308399,0,52615733865,0,14583605611,0,31675835175,0,25168516950,0}, {999968392525696,0,99660890,0,15,0,28476431549,0,3031381850,0}, {999999999999999,0,0,0,0,1,0,0,0,0}, {999931789936845,0,170850,0,1785,0,34124637892,0,34085252628,0}, {999813919424038,0,66908205,0,2045949360,0,183686150887,0,281567510,0}, {999715897267242,0,152641940340,0,43723680,0,128743100940,0,2673967798,0}, {999729635056047,0,2201063250,0,164847560790,0,94420494148,0,8895825765,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999862799942886,0,3077131718,0,1786,0,93790632975,0,40332290635,0}, {999850004832794,0,131855130,0,1106837550,0,134251026431,0,14505448095,0}, {999591719988030,0,1489732726,0,1318852080,0,400854552839,0,4616874325,0}, {999882128231587,0,42674914485,0,10726252320,0,38215920993,0,26254680615,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999950291528774,0,21327254265,0,184264080,0,23120318050,0,5076634831,0}, {999570454635710,0,896539567,0,0,0,225054318913,0,203594505810,0}, {999678643308303,0,23669811480,0,50908747890,0,244157939572,0,2620192755,0}, {999847363964251,0,3280400075,0,0,0,148809980275,0,545655399,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999927973465266,0,35053320,0,0,0,62787258960,0,9204222454,0}, {999666349685834,0,2189644566,0,186696510,0,330557025205,0,716947885,0}, {999873993431116,0,1236705,0,97181760,0,125067765858,0,840384561,0}, {999894515322080,0,2130023100,0,43303260,0,57790551010,0,45520800550,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999743282172941,0,94595983375,0,76650,0,155360835873,0,6760931161,0}, {999718198948027,0,17761914935,0,10597036905,0,219140906198,0,34301193935,0}, {999911762595931,0,51069560115,0,4949490,0,29532230270,0,7630664194,0}, {999729016236669,0,63973940271,0,0,5005,72711517945,0,134298300110,0}}; long long small_coefficients[17*2 + 1][17 + 1]; long long coefficients[17*3 + 1][17*2 + 1][17 + 1]; long long factorials[20]; int mno(long long x){ if(x < 10){ return x; } long long y = 1; while(x > 0 && y > 0){ y *= (x % 10); x /= 10; } return mno(y); } // so, basically, we start with some factor, and we fill in // the remaining first D digits. vector<long long> generate_counter(int D, vector<long long> factors){ int original_size = factors.size(); vector<long long> RES(10, 0); for(int l = 0; l < factors.size(); l++){ if(factors[l] < 10){ for(int i = 0; i < 10; i++){ RES[i] += MAP[D][factors[l]][i]; } factors.erase(factors.begin() + l); l--; continue; } if(D == 16){ vector<long long> vec; for(int i = 0; i < 10; i++){ RES[i] += DEG16[factors[l]][i]; } factors.erase(factors.begin() + l); l--; continue; } if(D == 15){ vector<long long> vec; for(int i = 0; i < 10; i++){ RES[i] += DEG15[factors[l]][i]; } factors.erase(factors.begin() + l); l--; continue; } } if(factors.size() > 0){ int amts[3]; // if we can append any 5 whatsoever, and if the factor is not even. if(D >= 1){ amts[0] = 0; amts[1] = 1; amts[2] = 0; long long v0 = 1; long long v1 = 5; long long v2 = 1; long long v, summand; while(true){ // this is the crux of the algorithm. // first assume there is a five somewhere. // then adding any 2 will make things 0, // so we only have prime factors 3, 5, 7. // position 0 is 3, position 1 is 5, position 2 is 7. summand = factorials[D]/(factorials[amts[1]]*factorials[amts[2]]*factorials[D-amts[1]-amts[2]]) * small_coefficients[amts[0]][D - amts[1] - amts[2]]; v = v0 * v1 * v2; for(int l = 0; l < factors.size(); l++){ RES[mno(v * factors[l])] += summand; } if(amts[0] == 2*(D - amts[1] - amts[2])){ amts[0] = 0; v0 = 1; } else { amts[0]++; v0 *= 3; continue; } if(amts[1] + amts[2] == D){ amts[1] = 1; v1 = 5; } else { amts[1]++; v1 *= 5; continue; } if(amts[2] == D - 1){ amts[2] = 0; v2 = 1; } else { amts[2]++; v2 *= 7; continue; } break; } } amts[0] = 0; amts[1] = 0; amts[2] = 0; long long v0 = 1; long long v1 = 1; long long v2 = 1; long long v, summand; while(true){ // again, this is the crux of the algorithm. // we assume there is NO five anywhere. // So we only have prime factors 2, 3, 7. // position 0 is 2, position 1 is 3, position 2 is 7. summand = coefficients[amts[0]][amts[1]][D - amts[2]]; if(summand > 0){ summand *= factorials[D] / (factorials[amts[2]] * factorials[D - amts[2]]); v = v0 * v1 * v2; for(int l = 0; l < factors.size(); l++){ RES[mno(v * factors[l])] += summand; } amts[0]++; v0 *= 2; continue; } else { amts[0] = 0; v0 = 1; } if(amts[1] == 2*(D - amts[2])){ amts[1] = 0; v1 = 1; } else { amts[1]++; v1 *= 3; continue; } if(amts[2] == D){ amts[2] = 0; v2 = 1; } else { amts[2]++; v2 *= 7; continue; } break; } } // all the remaining cases will give us necessarily a 0. long long z = original_size; for(int i = 0; i < D; i++){ z *= 10ll; } for(int i = 0; i < 10; i++){ z -= RES[i]; } RES[0] += z; return RES; } void process(){ long long N; cin >> N; N++; long long x = 1; long long leading_digit = 1; long long power = 1; int degrees = 0; vector<long long> counter(10, 0); vector<long long> ans(10, 0); while(x <= N){ // we include all of them exclusive of the upper range. for(int i = 0; i < 10; i++){ ans[i] += counter[i]; } if(degrees == 18) break; counter = generate_counter(degrees, {leading_digit}); leading_digit++; x += power; if(leading_digit == 10){ leading_digit = 1; power *= 10ll; degrees++; } } if(leading_digit == 1){ leading_digit = 9; degrees--; power /= 10ll; } x -= power; // cout << N << endl; // cout << x << endl; if(N >= MAX){ for(long long l = MAX; l < N; l++){ ans[mno(l)]++; } for(int i = 0; i < 10; i++){ cout << ans[i] << ' '; } cout << '\n'; return; } else { power /= 10ll; } // cout << power << endl; // so now we have the following situation: // MAX > N >= x // and we wish to calculate for all the numbers up to, but excluding, N. // currently, ans calculates for all the numbers up to, but excluding, x. vector<long long> digits; long long N_copy = N; while(N > 0){ digits.push_back(N%10ll); N /= 10ll; } N = N_copy; long long factor = digits.back(); for(int i = digits.size() - 2; i >= 0; i--){ // cout << x << endl; vector<long long> input; if(x <= N){ // we increase x. int upper_range = digits[i]; if(i != 0 && digits[i - 1] >= 5){ upper_range = digits[i] + 1; } for(long long d = 0; d < upper_range; d++){ input.push_back(factor * d); } vector<long long> counter = generate_counter(i, input); for(int j = 0; j < 10; j++){ ans[j] += counter[j]; } x += power * upper_range; } else { // we decrease x. int lower_range = digits[i]; if(i != 0 && digits[i - 1] >= 5){ lower_range = digits[i] + 1; } for(long long d = 9; d >= lower_range; d--){ input.push_back(factor * d); } vector<long long> counter = generate_counter(i, input); for(int j = 0; j < 10; j++){ ans[j] -= counter[j]; } x -= power * (10ll - lower_range); } factor *= digits[i]; power /= 10ll; } for(int i = 0; i < 10; i++){ cout << ans[i] << ' '; } cout << '\n'; } void find_coefficients(){ // firstly find the small coefficients. for(int i = 0; i < 17*2 + 1; i++){ for(int k = 0; k < 17 + 1; k++){ small_coefficients[i][k] = 0; if(i > 2*k){ continue; } long long sum = 0; for(int s = max(0, i - k); 2*s <= i; s++){ // so we have: s nines, i - 2*s threes, and k + s - i ones sum += factorials[k]/(factorials[s] * factorials[i - 2*s] * factorials[k + s - i]); } small_coefficients[i][k] = sum; // cout << "i = " << i << " k = " << k << " sum = " << sum << endl; } } // cout << "HERE" << endl; // and now the big coefficients. for(int i = 0; i < 17*3 + 1; i++){ for(int j = 0; j < 17*2 + 1; j++){ for(int k = 0; k < 17 + 1; k++){ // here is how it looks like: // there is i factors of 2 // there is j factors of 3 // all of them are distributed over k fields. coefficients[i][j][k] = 0; if(i > 3*k || j > 2*k){ continue; } // let a be the amount of number 6, and b the amount of fields in which I place values divisible by 2. for(int a = 0; a <= min(min(i, j), k); a++){ for(int b = 0; b <= k - a; b++){ if(i - a > 3*b || i - a - b < 0 || j - a > 2*(k - a - b)){ continue; } long long val = factorials[k] / factorials[a]; val /= factorials[b]; val /= factorials[k - a - b]; // now I place the values 2, 4, 8 on b fields. val *= small_coefficients[i - a - b][b]; // and finally, I place the values 1, 3, 9 on k - a - b fields. val *= small_coefficients[j - a][k - a - b]; coefficients[i][j][k] += val; } } } } } } // the normal main function int main(){ // std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now(); cin.tie(NULL); ios_base::sync_with_stdio(0); factorials[0] = 1; for(long long i = 1; i < 20; i++){ factorials[i] = i * factorials[i - 1]; } find_coefficients(); // cout << "DONE" << endl; int T; cin >> T; for(int v = 0; v < T; v++){ process(); } // std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now(); // std::cerr << "Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[µs]" << std::endl; // std::cerr << "Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds> (end - begin).count() << "[ns]" << std::endl; } // main function used to generate initial MAP values. /* int main(){ cin.tie(NULL); ios_base::sync_with_stdio(0); factorials[0] = 1; for(long long i = 1; i < 20; i++){ factorials[i] = i * factorials[i - 1]; } find_coefficients(); int d = 15; for(long long factor = 0; factor < 1000; factor++){ // cout << "d = " << d << " " << "factor = " << factor << endl; vector<long long> vec = generate_counter(d, factor); cout << "{"; for(int j = 0; j < 10; j++){ cout << vec[j]; if(j != 9){ cout << ','; } } cout << "}"; if(factor != 99){ cout << ","; } cout << '\n'; } } */
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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 | #include <bits/stdc++.h> using namespace std; const long long MAX = 1000000000000000000; long long MAP[18][10][10] = { {{1,0,0,0,0,0,0,0,0,0}, {0,1,0,0,0,0,0,0,0,0}, {0,0,1,0,0,0,0,0,0,0}, {0,0,0,1,0,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0}, {0,0,0,0,0,0,1,0,0,0}, {0,0,0,0,0,0,0,1,0,0}, {0,0,0,0,0,0,0,0,1,0}, {0,0,0,0,0,0,0,0,0,1}}, {{10,0,0,0,0,0,0,0,0,0}, {1,1,1,1,1,1,1,1,1,1}, {2,0,2,0,2,0,2,0,2,0}, {1,0,2,1,1,1,1,0,2,1}, {2,0,1,0,1,0,3,0,3,0}, {7,0,0,0,0,3,0,0,0,0}, {3,0,1,0,0,0,2,0,4,0}, {2,0,1,0,1,1,1,1,3,0}, {3,0,0,0,1,0,3,0,3,0}, {3,0,0,0,2,0,0,0,4,1}}, {{100,0,0,0,0,0,0,0,0,0}, {34,1,8,2,9,6,13,2,22,3}, {44,0,10,0,8,0,20,0,18,0}, {40,0,11,1,9,5,12,0,20,2}, {48,0,6,0,5,0,26,0,15,0}, {87,0,0,0,0,13,0,0,0,0}, {51,0,9,0,5,0,17,0,18,0}, {47,0,9,0,8,5,20,1,10,0}, {54,0,4,0,3,0,25,0,14,0}, {47,0,11,0,8,4,8,0,21,1}}, {{1000,0,0,0,0,0,0,0,0,0}, {552,1,68,3,55,33,141,3,138,6}, {632,0,58,0,33,0,162,0,115,0}, {613,0,79,1,39,21,105,0,139,3}, {681,0,39,0,16,0,157,0,107,0}, {958,0,0,0,0,42,0,0,0,0}, {694,0,61,0,18,0,107,0,120,0}, {694,0,42,0,28,21,160,1,54,0}, {755,0,32,0,6,0,124,0,83,0}, {684,0,87,0,19,15,61,0,133,1}}, {{10000,0,0,0,0,0,0,0,0,0}, {7263,1,466,4,214,132,1017,4,889,10}, {7913,0,353,0,98,0,920,0,716,0}, {7931,0,474,1,110,74,613,0,793,4}, {8431,0,256,0,37,0,716,0,560,0}, {9875,0,0,0,0,125,0,0,0,0}, {8480,0,324,0,42,0,551,0,603,0}, {8490,0,158,0,68,64,851,1,368,0}, {8853,0,204,0,10,0,549,0,384,0}, {8426,0,435,0,36,40,454,0,608,1}}, {{100000,0,0,0,0,0,0,0,0,0}, {85662,1,2670,5,615,435,5671,5,4921,15}, {89196,0,1897,0,230,0,4875,0,3802,0}, {89061,0,2301,1,245,245,4231,0,3911,5}, {91445,0,1356,0,71,0,4138,0,2990,0}, {99619,0,0,0,0,381,0,0,0,0}, {91008,0,1505,0,80,0,4376,0,3031,0}, {91302,0,615,0,135,245,4841,1,2861,0}, {92717,0,1055,0,15,0,3697,0,2516,0}, {90197,0,2061,0,60,160,4866,0,2655,1}}, {{1000000,0,0,0,0,0,0,0,0,0}, {920207,1,13460,6,1451,1466,36695,6,26687,21}, {933774,0,9528,0,462,0,34239,0,21997,0}, {929707,0,11421,1,471,951,37161,0,20282,6}, {942703,0,7026,0,181,0,30959,0,19131,0}, {998807,0,0,0,0,1193,0,0,0,0}, {938492,0,8066,0,255,0,36145,0,17042,0}, {944711,0,2723,0,356,1071,31657,1,19481,0}, {949299,0,5682,0,381,0,27476,0,17162,0}, {934209,0,11514,0,272,660,40587,0,12757,1}}, {{10000000,0,0,0,0,0,0,0,0,0}, {9491909,1,69420,7,3829,5341,274919,7,154539,28}, {9561834,0,52424,0,4088,0,249074,0,132580,0}, {9538181,0,65849,1,4599,3570,278572,0,109221,7}, {9618057,0,43660,0,8380,0,215859,0,114044,0}, {9996471,0,0,0,0,3529,0,0,0,0}, {9600907,0,53390,0,9030,0,243916,0,92757,0}, {9660218,0,20538,0,7203,3997,199990,1,108053,0}, {9666134,0,41076,0,15568,0,183288,0,93934,0}, {9594062,0,71365,0,7483,2219,259728,0,65142,1}}, {{100000000,0,0,0,0,0,0,0,0,0}, {96727773,1,417722,8,60180,18656,1905346,8,870270,36}, {97183454,0,365524,0,102076,0,1628882,0,720064,0}, {97126097,0,443468,1,92100,11516,1765044,0,561766,8}, {97570603,0,350312,0,153721,0,1354532,0,570832,0}, {99990575,0,0,0,0,9425,0,0,0,0}, {97548654,0,400655,0,136444,0,1460419,0,453828,0}, {97878586,0,253627,0,103832,12272,1241804,1,509878,0}, {97929955,0,346480,0,197436,0,1108366,0,417763,0}, {97622405,0,447454,0,93256,6160,1497504,0,333220,1}}, {{1000000000,0,0,0,0,0,0,0,0,0}, {979578102,1,3025242,9,939045,58029,11961897,9,4437621,45}, {982663764,0,2861164,0,1237482,0,9826356,0,3411234,0}, {982918871,0,3050403,1,974745,31869,10347712,0,2676390,9}, {985518393,0,2716767,0,1431757,0,7878618,0,2454465,0}, {999977349,0,0,0,0,22651,0,0,0,0}, {985857171,0,2737101,0,1135440,0,8275969,0,1994319,0}, {986865866,0,2468514,0,872481,32121,7594662,1,2166355,0}, {988296759,0,2465967,0,1451817,0,6168711,0,1616746,0}, {986706155,0,2547882,0,689718,14760,8430852,0,1610632,1}}, {{10000000000,0,0,0,0,0,0,0,0,0}, {9878382430,1,21873040,10,8732485,159430,70484777,10,20367762,55}, {9900526094,0,19875933,0,9375140,0,55772770,0,14450063,0}, {9904869365,0,18549872,1,6746485,77665,57999579,0,11757023,10}, {9921215165,0,17225847,0,8984341,0,42958482,0,9616165,0}, {9999950419,0,0,0,0,49581,0,0,0,0}, {9925270623,0,15470020,0,6592905,0,44579845,0,8086607,0}, {9925210327,0,17504924,0,5177200,74305,43064918,1,8968325,0}, {9939663569,0,13905250,0,7668415,0,32619365,0,6143401,0}, {9930928773,0,12496527,0,3684560,31620,45658394,0,7200125,1}}, {{100000000000,0,0,0,0,0,0,0,0,0}, {99326016765,1,136901413,11,56961531,392601,393138130,11,86589471,66}, {99474404786,0,114029719,0,52283957,0,300029554,0,59251984,0}, {99508935359,0,95437529,1,35198031,170951,309861453,0,50396665,11}, {99599615145,0,88964480,0,43316516,0,226544220,0,41559639,0}, {99999899712,0,0,0,0,100288,0,0,0,0}, {99629431515,0,72658872,0,29983250,0,231848266,0,36078097,0}, {99605068461,0,97084560,0,24155681,156101,225852154,1,47683042,0}, {99695226958,0,64420389,0,32267631,0,174572310,0,33512712,0}, {99660525302,0,52704410,0,15720617,62095,237397424,0,33590151,1}}, {{1000000000000,0,0,0,0,0,0,0,0,0}, {996499124003,1,722201372,12,289887214,882036,2099243511,12,388661761,78}, {997325950061,0,548127065,0,234585078,0,1585621052,0,305716744,0}, {997544339519,0,419808061,1,149913534,346710,1621936570,0,263655593,12}, {997934645314,0,388888545,0,172724905,0,1222418124,0,281323112,0}, {999999810115,0,0,0,0,189885,0,0,0,0}, {998128620262,0,292607074,0,114337410,0,1226533916,0,237901338,0}, {997878260436,0,446614093,0,94543912,303744,1191689622,1,388588192,0}, {998338308785,0,258797528,0,115887102,0,985390717,0,301615868,0}, {998299654938,0,194685645,0,57220132,113784,1249370002,0,198955498,1}}, {{10000000000000,0,0,0,0,0,0,0,0,0}, {9981948713433,1,3271729383,13,1229099287,1836159,11182203514,13,2366418106,91}, {9985836512869,0,2285533238,0,903400550,0,8637913830,0,2336639513,0}, {9987211394494,0,1619971288,1,559349921,657761,8723126763,0,1885499759,13}, {9988456300026,0,1508398229,0,629428255,0,6892012101,0,2513861389,0}, {9999999659867,0,0,0,0,340133,0,0,0,0}, {9989816998846,0,1047530068,0,417721980,0,6761320944,0,1956428162,0}, {9987751222276,0,1773930652,0,339754688,555373,6750044184,1,3384492826,0}, {9990122610763,0,962243490,0,459303364,0,5680583376,0,2775259007,0}, {9990887874782,0,644837349,0,218548824,197080,6864707499,0,1383834465,1}}, {{100000000000000,0,0,0,0,0,0,0,0,0}, {99902031287356,1,13114173697,14,4756606869,3586506,61491912211,14,18602433227,105}, {99919641710032,0,8606104340,0,3668907088,0,48528107058,0,19555171482,0}, {99929264352695,0,5647574611,1,2424698563,1180739,48266305206,0,14395888171,14}, {99931699651720,0,5483870016,0,3371107195,0,38898245701,0,20547125368,0}, {99999999418663,0,0,0,0,581337,0,0,0,0}, {99942017318716,0,3467777861,0,2569780759,0,37225384302,0,14719738362,0}, {99927873948748,0,6254904215,0,1614558232,964523,39307821385,1,24947802896,0}, {99939809553494,0,3566556644,0,4129671651,0,31435810812,0,21058407399,0}, {99949448192672,0,1963761996,0,1683101448,325780,37753002938,0,9151615165,1}}, {{1000000000000000,0,0,0,0,0,0,0,0,0}, {999441785434096,1,48104723380,15,24218431805,6638885,342906589613,15,142978182070,120}, {999530394990365,0,30615528854,0,27720348105,0,267931309640,0,143337823036,0}, {999601642329051,0,18366321393,1,21015375585,2023260,261504612384,0,97469338311,15}, {999593910499764,0,19811642068,0,38273670076,0,208454487722,0,139549700370,0}, {999999999045449,0,0,0,0,954551,0,0,0,0}, {999671553418406,0,11087644490,0,30658069785,0,193542768631,0,93158098688,0}, {999596377529707,0,19974463570,0,14620363805,1604205,217262336300,1,151763702412,0}, {999636863478955,0,13916789960,0,56183937930,0,161986434194,0,131049358961,0}, {999724777284070,0,5649374913,0,21235704485,517755,195567420696,0,52769698080,1}}, {{10000000000000000,0,0,0,0,0,0,0,0,0}, {9996797304009863,1,167526488628,16,233925901576,11738656,1849155959180,16,952075901928,136}, {9997280671340441,0,107723197271,0,331483705352,0,1393872382200,0,886249374736,0}, {9997801672282131,0,57668744012,1,250479263736,3332376,1325951950092,0,564224427636,16}, {9997619051982521,0,74116160124,0,468171031201,0,1042289009976,0,796371816178,0}, {9999999998485887,0,0,0,0,1514113,0,0,0,0}, {9998179884076364,0,35679377951,0,355983047880,0,927930426481,0,500523071324,0}, {9997909326894869,0,58643574930,0,156560419056,2571616,1094162376972,1,781304162556,0}, {9997832483391271,0,57128708096,0,630784474456,0,789834040308,0,689769385869,0}, {9998560580374487,0,15803521564,0,234139390192,795680,925632437780,0,263843480296,1}}, {{100000000000000000,0,0,0,0,0,0,0,0,0}, {99981980972837834,1,574289772576,17,2661527233449,19952441,9348828582989,17,5434361620523,153}, {99984541917142935,0,387158434419,0,3589960401658,0,6781742947852,0,4699221073136,0}, {99988218706190613,0,180552032329,1,2569422345249,5304425,6202558665292,0,2828755462074,17}, {99986225932168174,0,287637011553,0,4590583290265,0,4970554559287,0,3925292970721,0}, {99999999997669469,0,0,0,0,2330531,0,0,0,0}, {99990104052509256,0,118324717262,0,3289671369520,0,4145913647648,0,2342037756314,0}, {99989902464958499,0,160145819015,0,1426962514565,3993521,5009166641964,1,3501256072435,0}, {99987242858821151,0,236438712690,0,5518031810925,0,3833552629569,0,3169118025665,0}, {99992750965596212,0,44175064060,0,2039166442570,1187824,4001253338345,0,1164438370988,1} }}; long long DEG16[100][10] = {{10000000000000000,0,0,0,0,0,0,0,0,0}, {9996797304009863,1,167526488628,16,233925901576,11738656,1849155959180,16,952075901928,136}, {9997280671340441,0,107723197271,0,331483705352,0,1393872382200,0,886249374736,0}, {9997801672282131,0,57668744012,1,250479263736,3332376,1325951950092,0,564224427636,16}, {9997619051982521,0,74116160124,0,468171031201,0,1042289009976,0,796371816178,0}, {9999999998485887,0,0,0,0,1514113,0,0,0,0}, {9998179884076364,0,35679377951,0,355983047880,0,927930426481,0,500523071324,0}, {9997909326894869,0,58643574930,0,156560419056,2571616,1094162376972,1,781304162556,0}, {9997832483391271,0,57128708096,0,630784474456,0,789834040308,0,689769385869,0}, {9998560580374487,0,15803521564,0,234139390192,795680,925632437780,0,263843480296,1}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9994261945610933,1,892963347572,0,59454354254,2446200,4699681168004,0,85953073020,16}, {9998435783967383,0,23986901781,0,479845606496,0,631279381712,0,429104142628,0}, {9996583865270339,0,1028674347432,1,531029478832,458376,1493582512064,136,362847931124,1696}, {9998396352410331,0,30163814464,0,211174140057,0,762828092068,0,599481543080,0}, {9999999999634207,0,0,0,0,365793,0,0,0,0}, {9997950366458293,0,49090268244,0,796984668480,0,628495112015,0,575063492968,0}, {9995801501839084,0,1608162692296,0,1124163919000,152,716002643700,1,750168905751,16}, {9998847323516331,0,9270006488,0,315533727736,0,605214503092,0,222658246353,0}, {9998852192413575,0,210297156632,0,73528852376,146116,572826001676,136,291155429472,17}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9998695148143421,0,16743673425,0,151142490056,657120,735823586056,0,401141449922,0}, {9994782649202603,0,759465152960,0,31790429305,0,4373458159452,0,52637055680,0}, {9998214730940383,0,239769279280,0,41768228600,58096,1483463428913,0,20268064728,0}, {9998587445266527,0,18281639152,0,606793867696,0,432142761172,0,355336465453,0}, {9999999999936448,0,0,0,0,63552,0,0,0,0}, {9997320155691684,0,699272406113,0,747039349296,0,1031550780304,0,201981772603,0}, {9999110868929762,0,3118167956,0,175504951457,153456,618583618907,0,91924178462,0}, {9998753924702511,0,14399662504,0,270034311040,0,524925949893,0,436715374052,0}, {9998269089265517,0,6779542176,0,0,101360,1675482339946,0,48648751001,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9996400686404393,0,86812248974,1,27281734512,64208,3425054591448,0,60164956464,0}, {9998012127541779,0,44731235124,0,938956789680,0,543556341401,0,460628092016,0}, {9994855594034827,0,772333727412,0,77197848312,677040,4264811786712,0,30061925696,1}, {9996624260093327,0,1139208316649,0,1140647606080,0,566963417720,0,528920566224,0}, {9999999999687679,0,0,0,0,312321,0,0,0,0}, {9999034748857889,0,5902436528,0,399012541216,0,378031962810,0,182304201557,0}, {9996548230434575,16,1091974861661,0,270296,1681680,1240758881048,0,1119033870724,0}, {9999042457830389,0,267817063526,0,53660186192,0,433103149824,0,202961770069,0}, {9997696929574774,0,536570553152,0,663549847201,118356,853186251013,16,249763655368,120}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9997626800240683,0,795625374320,0,150976183601,0,1040591911552,0,386006289844,0}, {9999032419091851,0,8019522192,0,193510080416,0,472064344100,0,293986961441,0}, {9997932068270957,0,112812677729,0,136,1920,1735974771516,0,219144277742,0}, {9995304729745629,0,680443465164,0,13801100080,0,3969927432399,0,31098256728,0}, {9999999999925248,0,0,0,0,74752,0,0,0,0}, {9998551148539717,0,247500813852,0,17477888418,0,1169406519668,0,14466238345,0}, {9996047663535267,0,23455289960,0,10896,262200,1763430874141,0,2165450027536,0}, {9998664952974977,0,15525277114,0,717332637840,0,317915662725,0,284273447344,0}, {9998883270276594,0,22007942090,0,272,310368,573807928603,0,520913542073,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9996993118306365,0,1219524081310,0,943036067040,17,306885365948,0,537436179320,0}, {9997747431959048,0,444357307304,0,979558275712,0,727470434338,0,101182023598,0}, {9997779993539211,0,18240155212,240,7695856,10881,1881145797320,0,320612801280,0}, {9999321494757934,0,1659556056,0,221659860240,0,381334605556,0,73851220214,0}, {9999999999711712,0,0,0,0,288288,0,0,0,0}, {9998993459921822,0,6403564386,0,324590106516,0,370818492472,0,304727914804,0}, {9999365393342039,0,183064441640,0,20425768456,28057,312565128588,16,118551291204,0}, {9998638973104936,0,4026780884,0,0,0,1304110263956,0,52889850224,0}, {9998236991224361,0,75621809272,0,2732850120,11576,1502110234007,0,182543870664,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9999454858014507,0,27922900,0,784944,7280,402718196057,0,142395074312,0}, {9996614947772643,0,54113931885,0,14007313320,0,3284419242176,0,32511739976,0}, {9999238563829421,0,3764065024,0,119950967152,142096,474735871800,0,162985124507,0}, {9998058991607297,0,41013307942,0,1029842583120,0,515868990872,0,354283510769,0}, {9999999999985632,0,0,0,0,14368,0,0,0,0}, {9995425776194943,0,620224710264,0,38458603064,0,3898961056528,0,16579435201,0}, {9997195730508435,0,1324666155208,0,321116235440,0,791909638964,0,366577461953,0}, {9997326543904103,0,741453102876,0,1108586178960,0,473428460941,0,349988353120,0}, {9999103929768136,0,98717689312,0,25721055480,12320,760580339456,0,11051135296,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9999183735111719,0,31067123656,0,410213440,59484,337423647688,1,447363831412,12600}, {9999143031659185,0,4264712632,0,472746683137,0,234921228604,0,145035716442,0}, {9998250631444404,0,5468063920,0,572978003728,3636,1099507624048,0,71414860264,0}, {9996776579809739,0,1057313697800,0,41360,0,1100535590205,0,1065570860896,0}, {9999999999990559,0,0,0,0,9441,0,0,0,0}, {9999110713033987,0,358690003308,0,36686524000,0,362403627892,0,131506810813,0}, {9996441651717089,0,311268628934,0,66994543776,222784,3172771533448,0,7313353969,0}, {9998106258624880,0,334550628040,0,882984822720,0,544530291408,0,131675632952,0}, {9998205629406735,0,13769395496,0,3600,54080,1728727289848,136,51873850105,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9999494353745955,0,392597812,0,100618321440,21840,382799109796,0,21836203157,0}, {9998231299966433,0,584674065544,0,128995776256,0,703678608753,0,351351583014,0}, {9997209325449237,0,905048113016,0,9798896,1920,1737407791650,0,148208845281,0}, {9999264845017515,0,3509085236,0,233164540336,0,293398926733,0,205082430180,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9998295781781223,0,65069822100,0,16,0,1441043887061,0,198104509600,0}, {9998638138663450,0,1058746654,0,0,17880,1333771235720,0,27031336296,0}, {9995855161575143,0,629793852980,0,4597410800,0,3492802532316,0,17644628761,0}, {9999314652879393,0,111747809296,0,3315443977,240,564729337580,0,5554529514,0}, {10000000000000000,0,0,0,0,0,0,0,0,0}, {9997699875641553,0,391155125976,0,845286842672,47280,819547719108,0,244134623170,241}, {9998847325982679,0,248341322176,0,6035466768,0,888800259288,0,9496969089,0}, {9996475750146699,0,22254844112,0,8508820321,14740,3476546429752,0,16939744376,0}, {9996251460315483,0,20209090128,0,1920,0,1662977385836,0,2065353206633,0}, {9999999999989360,0,0,0,0,10640,0,0,0,0}, {9998704919873536,0,13860111124,0,792049811280,0,268883852940,0,220286351120,0}, {9998511768194779,0,12812566740,0,36063731376,0,1411526925000,0,27828582105,0}, {9999278548602061,0,10425677336,0,17,0,378395419178,0,332630301408,0}, {9995568083803435,0,619286171824,0,87293735240,152880,3713928595932,0,11407540689,0}}; long long DEG15[1000][10] = {{1000000000000000,0,0,0,0,0,0,0,0,0}, {999441785434096,1,48104723380,15,24218431805,6638885,342906589613,15,142978182070,120}, {999530394990365,0,30615528854,0,27720348105,0,267931309640,0,143337823036,0}, {999601642329051,0,18366321393,1,21015375585,2023260,261504612384,0,97469338311,15}, {999593910499764,0,19811642068,0,38273670076,0,208454487722,0,139549700370,0}, {999999999045449,0,0,0,0,954551,0,0,0,0}, {999671553418406,0,11087644490,0,30658069785,0,193542768631,0,93158098688,0}, {999596377529707,0,19974463570,0,14620363805,1604205,217262336300,1,151763702412,0}, {999636863478955,0,13916789960,0,56183937930,0,161986434194,0,131049358961,0}, {999724777284070,0,5649374913,0,21235704485,517755,195567420696,0,52769698080,1}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999168901575061,1,147996088340,0,7318548660,1531635,648495467273,0,27286789015,15}, {999722656229965,0,6907309210,0,45644639265,0,138570753455,0,86221068105,0}, {999315993277160,0,238760478290,1,32572132755,309428,330919726930,120,81754073936,1380}, {999682389518315,0,11002777976,0,20717730571,0,158929986683,0,126959986455,0}, {999999999753954,0,0,0,0,246046,0,0,0,0}, {999662497948227,0,11147593903,0,80263703520,0,127795276816,0,118295477534,0}, {999252130781474,0,296674648158,0,137619023220,135,156253029997,1,157322517000,15}, {999780405256444,0,3233910810,0,32021606100,0,136661365059,0,47677861587,0}, {999753628360293,0,22405194228,0,20438063640,104525,135656700008,120,67871577170,16}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999727411154567,0,6364922911,0,15654953280,438375,161887883932,0,88680646935,0}, {999238231448049,0,119287000440,0,4606737466,0,620110627735,0,17764186310,0}, {999630158268677,0,38288094292,0,10072167275,42435,318096155106,0,3385272215,0}, {999756282234273,0,4776600135,0,65217877740,0,96750138740,0,76973149112,0}, {999999999954715,0,0,0,0,45285,0,0,0,0}, {999486876964153,0,178310326111,0,51637050675,0,233843512466,0,49332146595,0}, {999816944621401,0,1282660150,0,19031037496,106940,141467007195,0,21274566818,0}, {999751645624105,0,5617289165,0,29260689315,0,113321122657,0,100155274758,0}, {999670183698169,0,2371375081,0,0,73710,319874562228,0,7570290812,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999533571030833,0,27249660428,1,9639484885,47103,410032778030,0,19506998720,0}, {999674935694062,0,10025850345,0,107573466000,0,105152224951,0,102312764642,0}, {999225127806973,0,138968835631,0,11396858560,453180,614209326200,0,10296719455,1}, {999377646693056,0,229874328976,0,154226351125,0,120324511525,0,117928115318,0}, {999999999785244,0,0,0,0,214756,0,0,0,0}, {999820260273170,0,1913085338,0,45753047355,0,90258571441,0,41815022696,0}, {999498760256997,15,167376326671,0,194160,780780,211740346914,0,122122094463,0}, {999814980577657,0,21987013416,0,16083318645,0,95862944180,0,51086146102,0}, {999553436310022,0,135351059605,0,47197640701,85170,206403391629,15,57611512753,105}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999542414319213,0,157823392890,0,11198311636,0,210862778486,0,77701197775,0}, {999793769285561,0,3257360905,0,22248940365,0,110256113028,0,70468300141,0}, {999667793502015,0,20475702549,0,120,1575,269276248591,0,42454545150,0}, {999297315309882,0,103667469395,0,2338051200,0,585549788053,0,11129381470,0}, {999999999946525,0,0,0,0,53475,0,0,0,0}, {999685729728739,0,39865026440,0,4702971975,0,267285109465,0,2417163381,0}, {999435656036155,0,4948941040,0,8415,173460,250614142727,0,308780698203,0}, {999774584326408,0,3823725390,0,87298020810,0,68162976262,0,66130951130,0}, {999727779823289,0,8166264255,0,240,213150,136802051205,0,127251647861,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999431059469948,0,238857698188,0,137506917240,16,72380742580,0,120195172028,0}, {999607792836898,0,123917073133,0,77356805541,0,164056188733,0,26877095695,0}, {999678209579467,0,6379527995,210,535200,8401,247362729894,0,68047618833,0}, {999860373052137,0,679741673,0,27140846460,0,93727739865,0,18078619865,0}, {999999999800710,0,0,0,0,199290,0,0,0,0}, {999802265883929,0,2665351253,0,39424029645,0,80541662695,0,75103072478,0}, {999866066667826,0,18496741720,0,6360390870,21471,77830139790,15,31246038308,0}, {999748934034860,0,1464154150,0,0,0,243804184260,0,5797626730,0}, {999639193889369,0,22362145275,0,601260660,8975,285293670100,0,52549025621,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999873893445591,0,16306255,0,518940,5460,105350111786,0,20739611968,0}, {999561448159372,0,17817052306,0,5350430085,0,404350834542,0,11033523695,0}, {999827688290152,0,1595144895,0,14633711835,101130,115161220472,0,40921531516,0}, {999679811226503,0,9515217105,0,133686382830,0,92556458175,0,84430715387,0}, {999999999989297,0,0,0,0,10703,0,0,0,0}, {999290289872521,0,110495233250,0,6572452608,0,586601927210,0,6040514411,0}, {999508099897096,0,166076869380,0,73663394805,0,168246703133,0,83913135586,0}, {999491075632295,0,163870275600,0,165688291860,0,96287238925,0,83078561320,0}, {999791660400332,0,16941942165,0,7023326415,9555,182681580503,0,1692741030,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999829923599068,0,10272761535,0,158143440,42645,62539518096,1,97105925660,9555}, {999845242598914,0,1257580005,0,61137055981,0,56888868475,0,35473896625,0}, {999717017441188,0,2116298104,0,77055731025,2850,182619418610,0,21191108223,0}, {999516931135603,0,166968563415,0,31815,0,188978429932,0,127121839235,0}, {999999999992754,0,0,0,0,7246,0,0,0,0}, {999851761828441,0,28583648410,0,11832154425,0,72038433603,0,35783935121,0}, {999395918076147,0,53080859606,0,11150940885,152895,537200414673,0,2649555794,0}, {999664413506742,0,93077423460,0,72829326570,0,136437574735,0,33242168493,0}, {999750705162429,0,2874122840,0,2940,38355,230196361740,120,16224311576,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999884889051674,0,192023780,0,13186380480,16380,95900244577,0,5832283109,0}, {999634002520411,0,127855897743,0,11691383110,0,152663522241,0,73786676495,0}, {999498484014308,0,144686071490,0,5944590,1575,312700966731,0,44123001306,0}, {999844315693641,0,1522503153,0,29990350390,0,71243522131,0,52927930685,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999709002729898,0,13220916660,0,15,0,240455702311,0,37320651116,0}, {999763636311642,0,443515445,0,0,13860,231910643988,0,4009515065,0}, {999354248509011,0,96927307680,0,908048535,0,541227822910,0,6688311864,0}, {999836867879168,0,24438336981,0,1312311786,210,136728680825,0,652791030,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999568564204856,0,106633003238,0,79997968290,34335,185119795926,0,59684993144,211}, {999738585826811,0,41446748960,0,1809563730,0,216488037938,0,1669822561,0}, {999522673945249,0,7800283640,0,3298555261,11445,460082053490,0,6145150915,0}, {999461276113724,0,4209425340,0,1575,0,233870380390,0,300644078971,0}, {999999999991810,0,0,0,0,8190,0,0,0,0}, {999781763731807,0,3422092405,0,108643209675,0,51625015818,0,54545950295,0}, {999675590367064,0,4433956935,0,10476077720,0,299846011530,0,9653586751,0}, {999811559668331,0,4137289435,0,16,0,95457824370,0,88845217848,0}, {999291913212579,0,122540553230,0,15162716340,109200,566285793950,0,4097614701,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999781892154197,0,6147781185,0,264360635,0,158846775765,0,52848928218,0}, {999537514804522,0,177911940615,0,143774532840,0,51570581808,0,89228140215,0}, {999765568439894,0,155325565055,0,274614810,0,43689016395,0,35142363846,0}, {999680739282350,0,80018118945,0,108050747805,0,117956578125,0,13235272775,0}, {999999999950635,0,0,0,0,49365,0,0,0,0}, {999716549119602,0,2441466538,0,479130,0,238785994455,0,42222940275,0}, {999693697374660,0,20483324830,0,169132005,470,257339600895,0,28310567140,0}, {999890678879205,0,364006145,0,36161405280,0,57779535390,0,15016173980,0}, {999839474405409,0,18339485635,0,85290,0,110480402040,0,31705621626,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999590548061145,1,119566740785,0,16920,225225,143269620780,0,146615335144,0}, {999835461648786,0,1186764661,0,49811541780,0,59438771413,0,54101273360,0}, {999776206593539,0,1034880,1,19320,21945,154041054115,0,69751276200,0}, {999897461509054,0,21369435250,0,4785255931,0,53979982550,0,22403817215,0}, {999999999995574,0,0,0,0,4426,0,0,0,0}, {999810647030789,0,904092191,0,0,0,182134577302,0,6314299718,0}, {999706048898861,0,72606864650,0,61387806495,18740,118845743520,1,41110667733,0}, {999736428404695,0,15012432645,0,561470910,0,215833398918,0,32164292832,0}, {999528756960364,0,216694300305,0,105180480420,0,107112127200,0,42256131710,1}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999685652293367,0,32105791,0,17798235,0,208561286417,0,105736516190,0}, {999911747353493,0,5247860,0,162646,0,73922291399,0,14324944602,0}, {999667871602161,0,122870126940,0,20927246460,0,151554776021,0,36776248418,0}, {999584007260134,0,11051788205,0,2709546840,0,396318440220,0,5912964601,0}, {999999999999335,0,0,0,0,665,0,0,0,0}, {999874945087663,0,774477916,0,19720857975,0,73639089091,0,30920487355,0}, {999309682060223,0,201224729165,0,145385340706,5670,341269505001,0,2438359235,0}, {999683298379794,0,9010286040,0,153594395955,0,87914709811,0,66182228400,0}, {999716387686055,0,19297484535,0,0,210,236825431436,0,27489397764,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999827953637497,0,80368023778,1,1926197028,10220,87816824390,0,1935307086,0}, {999354560866166,0,91067519085,0,3073853840,0,547848068886,0,3449692023,0}, {999868868921070,0,42330695533,0,4595564185,8855,35331434330,0,48873376026,1}, {999590285187333,0,177813645911,0,47428886505,0,113363507885,0,71108772366,0}, {999999999990339,0,0,0,0,9661,0,0,0,0}, {999588710689603,0,106941889735,0,169080584400,0,80594016570,0,54672819692,0}, {999637247387485,0,20641547804,0,55517889015,0,235508743676,0,51084432020,0}, {999835155158108,0,17601576090,0,3099546450,0,142851449990,0,1292269362,0}, {999778963642185,0,85396424465,0,11985205066,665,55405173645,0,68249553974,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999510027806887,0,951352220,0,1,46410,220869870857,0,268150923625,0}, {999861468195224,0,6533272740,0,95255160,0,50539847940,0,81363428936,0}, {999898227587165,0,1751106751,0,16172636565,32775,26560348460,0,57288288284,0}, {999858013502706,0,958738395,0,76113947910,0,35849678769,0,29064132220,0}, {999999999989570,0,0,0,0,10430,0,0,0,0}, {999759476150289,0,832985605,0,63614864040,0,165892453850,0,10183546216,0}, {999850797531104,0,2302451415,0,15,49140,81606584416,0,65293383910,0}, {999541847799099,0,161740074825,0,4725,0,170923006606,0,125489114745,0}, {999725261265926,0,83528001510,0,0,1365,180519300853,0,10691430346,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999778232192542,0,1354402030,0,3797495,1711,218066284650,0,2343321572,0}, {999867376472895,0,40954766000,0,8113609140,0,60422962460,0,23132189505,0}, {999594606807822,0,177337610719,0,111087737895,1,31480395095,0,85487448468,0}, {999472607338845,0,48684616755,0,5962051530,0,471092374425,0,1653618445,0}, {999999999999775,0,0,0,0,225,0,0,0,0}, {999730631649615,0,59740356936,0,103716112500,0,89028815216,0,16883065733,0}, {999766612556524,0,47734731900,0,31674881295,1,153110851965,0,866978315,0}, {999769863129035,0,2670247560,0,210,0,217966858765,0,9499764430,0}, {999696612954419,0,2685931760,15,245700,1590,236467039695,0,64233826821,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999845987143445,0,38098278198,0,10441791585,0,97604505047,0,7868281725,0}, {999917404866092,0,88466206,0,17484960675,0,60409655002,0,4612052025,0}, {999628745736988,0,194000182005,0,300525,4305,163937056405,0,13316719772,0}, {999721144620799,0,94852410135,0,10403127750,0,105279855035,0,68319986281,0}, {999999999948130,0,0,0,0,51870,0,0,0,0}, {999582021466249,0,132756300470,0,1699425,0,259067150960,0,26153382896,0}, {999761258995989,0,9734364900,0,7258680,1575,132371870940,0,96627507916,0}, {999878773984709,0,645571500,0,37924616730,0,44752844201,0,37902982860,0}, {999636915473841,0,100298945595,0,115650,0,168808283170,0,93977181744,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999932048084529,0,14169662075,0,1320495540,3075,41703404755,1,10758350025,0}, {999753630485028,0,7760106530,0,1,0,202826329396,0,35783079045,0}, {999707339499179,0,552591141,0,27134600235,120,254286174695,0,10687134630,0}, {999816105974064,0,195365510,0,0,0,180300605571,0,3398054855,0}, {999999999990324,0,0,0,0,9676,0,0,0,0}, {999415225607494,0,94676257420,0,239872845,0,486028731045,0,3829531196,0}, {999756867682259,0,7276493280,0,0,1710,211365784160,0,24490038591,0}, {999894107345986,0,15042988085,0,410089800,0,90075749944,0,363826185,0}, {999679293452935,0,147359979055,0,107655,0,152506710389,0,20839749966,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999887260973783,0,51433453190,0,1643460,0,61023751646,0,280177921,0}, {999660278157039,0,71670976315,0,105698032455,0,128807130261,0,33545703930,0}, {999945999709809,0,1973750,0,36975,0,36061911345,0,17936368121,0}, {999788362978613,0,42144176495,0,543730110,0,167884823704,0,1064291078,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999543315432279,0,4842572820,0,1749187440,0,446845537441,0,3247270020,0}, {999688606398145,0,150749675135,0,26020809585,15,83291210040,0,51331907080,0}, {999493537015414,0,3659455815,0,210,0,214619693870,0,288183834691,0}, {999897447165389,0,281240730,0,10969059466,19110,77276328785,0,14026186520,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999907118933858,0,1184352458,0,683214315,665,28878933108,0,62134565595,1}, {999783514133935,0,3187220520,0,125480024670,0,44721979219,0,43096641656,0}, {999783615463873,0,234833385,0,951827896,30,215067532325,0,130342491,0}, {999763599936502,0,2247135534,0,4412659800,0,225894717368,0,3845550796,0}, {999999999997030,0,0,0,0,2970,0,0,0,0}, {999877420977532,0,1915182405,0,0,0,64129394198,0,56534445865,0}, {999479513878829,0,48019501985,0,56035995,3500,323221433630,0,149189146061,0}, {999360170250635,0,94659748935,0,8089361281,0,534998819188,0,2081819961,0}, {999887402432431,0,119018460,0,38769298260,785,36613625025,0,37095625039,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999609150301332,0,170150742545,0,60027732765,0,120964242413,0,39706980945,0}, {999753611248940,0,5607416010,0,296639295,0,168186293570,0,72298402185,0}, {999778286254063,0,727205575,0,0,1575,209058844844,0,11927693943,0}, {999631695785307,0,121531150905,0,144530282715,0,39995593220,0,62247187853,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999785554727405,0,167657462835,0,66403155,0,27716152200,0,19005254405,0}, {999899091440084,0,5383436640,0,4075131060,1680,90571767160,0,878223376,0}, {999717470595363,0,47858172825,0,139532232840,0,89054607411,0,6084391561,0}, {999566794745953,0,141143648625,0,14200515435,0,104065873671,0,173795216316,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999812080788000,0,268347290,0,5120340,0,157949643725,0,29696100645,0}, {999745275489966,0,798681135,0,1448371,0,230132904658,0,23791475870,0}, {999917569680340,0,2338745495,0,0,12068,35328572782,0,44762987950,1365}, {999733611399311,0,18407881170,0,45466100,0,221449454912,0,26485798507,0}, {999999999999880,0,0,0,0,120,0,0,0,0}, {999909270753775,0,210110802,0,44979114180,0,33391259688,0,12148761555,0}, {999514165178416,0,9936131201,0,2433661231,3165,463589493834,0,9875532153,0}, {999866732866142,0,13644267170,0,11565,0,92849749060,0,26773106063,0}, {999755586438888,0,699804246,0,98984095665,665,132511146460,0,12218514076,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999897457377784,0,12225414505,0,2655252601,0,87186839890,0,475115220,0}, {999606389954368,0,121706698380,0,2255,0,126406157281,0,145497187716,0}, {999915953172001,0,4725900229,0,782431875,15,78005687470,0,532808410,0}, {999855344616517,0,505504394,0,58684799355,0,47619727678,0,37845352056,0}, {999999999999320,0,0,0,0,680,0,0,0,0}, {999824125302395,0,96915,0,1575,0,115661592958,0,60213006157,0}, {999661234756174,0,111858343995,0,120457447110,16395,68526176136,0,37923260190,0}, {999911524086922,0,28812672945,0,3371877915,0,41324849479,0,14966512739,0}, {999741679698516,0,90013451010,0,139335,0,128174564013,0,40132147126,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999533224837356,0,36221619610,0,14474565540,42315,415707134949,0,371800230,0}, {999856758962189,0,548687088,0,0,0,134954279213,0,7738071510,0}, {999658880773139,0,33773401280,0,14813939130,0,272823838080,0,19708048371,0}, {999771952699524,0,44679958388,0,88219040910,0,72366373357,0,22781927821,0}, {999999999967225,0,0,0,0,32775,0,0,0,0}, {999814609488153,0,9657913545,0,489338850,0,157105375875,0,18137883577,0}, {999758281192526,0,644759550,0,210,11193,235123014860,15,5951021646,0}, {999646128327009,0,148348622010,0,92133427530,0,87570796281,0,25818827170,0}, {999734451703432,0,77412374320,0,574247145,1470,179660046238,105,7901627290,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999787063285070,0,3826383590,0,11403,19110,180010290036,0,29100010791,0}, {999758505926666,0,19984810,0,8396115,0,160998456034,0,80467236375,0}, {999933860549750,0,19918470,0,6552147420,1365,58631848405,0,935534590,0}, {999933060121260,0,1766865,0,44100,0,52707598855,0,14230468920,0}, {999999999971047,0,0,0,0,28953,0,0,0,0}, {999749835839296,0,94308588675,0,19494111225,0,102281129179,0,34080331625,0}, {999540851290979,0,38949264826,0,121182626565,1575,285992904385,0,13023911670,0}, {999606549605647,0,6530634968,0,1243602360,0,382689486735,0,2986670290,0}, {999643279555329,0,83174657045,0,1184821,210,250264841572,0,23279761023,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999716604473234,0,180401288340,0,38047829820,455,61711943631,0,3234464520,0}, {999908696273292,0,341495973,0,24938283825,0,43878904920,0,22145041990,0}, {999643246252016,0,14807730,0,2734095,15,177208184264,0,179528021880,0}, {999349063396157,0,201922102540,0,142016566632,0,304384949866,0,2612984805,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999690486365117,0,8245999350,0,163058712180,0,89000492753,0,49208430600,0}, {999748954212861,0,93054418641,0,9555,0,90595371978,0,67395986965,0}, {999760193297849,0,11036791185,0,0,0,205826068580,0,22943842386,0}, {999551750004662,0,119626702995,0,19530,630630,143750424825,0,184872217358,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999824537010171,0,125147136,0,0,1785,173444642540,0,1893198368,0}, {999835062418039,0,94789042845,0,1319822910,0,67886612040,0,942104166,0}, {999469416134819,0,180335501640,0,37478613900,24585,312420807596,0,348917460,0}, {999424225852169,0,77542079870,0,1104924500,0,495203976436,0,1923167025,0}, {999999999999320,0,0,0,0,680,0,0,0,0}, {999886380156215,0,52036907882,0,3353763106,0,23670821422,0,34558351375,0}, {999899712372434,0,19806132885,0,531532365,0,79066182786,0,883779530,0}, {999645378076028,0,195201154530,0,27333726420,0,70510099951,0,61576943071,0}, {999685743409025,0,1203159090,0,149199050000,0,72077776800,0,91776605085,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999940683255121,0,35419961340,0,196441471,15,19907973458,0,3792368595,0}, {999670005323379,0,63564343605,0,162376517160,0,70674169511,0,33379646345,0}, {999708408884459,0,53955025140,0,88784130450,8400,104835127340,0,44016824196,15}, {999756244499934,0,16164753885,0,45523107645,0,149251265276,0,32816373260,0}, {999999999991810,0,0,0,0,8190,0,0,0,0}, {999871653069161,0,17995344150,0,1130629500,0,108305986464,0,914970725,0}, {999834390578542,0,73321157673,0,4951,105,83842272779,0,8445985950,0}, {999811468158072,0,102506508751,0,10608953460,0,32650278532,0,42766101185,0}, {999534955792688,0,1584125406,0,857266410,2270,461145967156,0,1456846070,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999668328594775,0,91310438445,0,0,0,172719792717,0,67641174063,0}, {999523621103305,0,732410679,0,0,0,211821864986,0,263824621030,0}, {999833478470615,0,64587874560,0,15,455,99480036525,0,2453617830,0}, {999890559203793,0,4092908225,0,52932880,0,40021018006,0,65273937096,0}, {999999999998425,0,0,0,0,1575,0,0,0,0}, {999922318811103,0,1052633505,0,7828466520,0,22192699987,0,46607388885,0}, {999742381734037,0,50299023511,0,37743385680,0,148507482467,0,21068374305,0}, {999862973394044,0,819064965,0,88235799015,0,24965732996,0,23006008980,0}, {999788503430989,0,20072851860,0,32399006640,0,73738336681,0,85286373830,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999759872655279,0,1738752885,0,6430263840,0,227516704035,0,4441623961,0}, {999794965428581,0,316695305,0,46427119830,0,154018814030,0,4271942254,0}, {999733115445922,0,56464985878,0,120,8190,208948892235,0,1470667655,0}, {999903266133066,0,1099128215,0,1,0,52268837413,0,43365901305,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999581143113407,0,151687345775,0,435,0,152722046895,0,114447493488,0}, {999376081388298,0,100838137801,0,17323115643,20475,503956739893,0,1800597890,0}, {999790870585791,0,60763384500,0,0,0,143490904339,0,4875125370,0}, {999722149117029,0,2358028261,0,9975,0,275394014895,0,98829840,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999748154000897,0,17483360615,0,0,0,231082982745,0,3279655743,0}, {999805345858920,0,506971650,0,24448125,0,190964618230,0,3158103075,0}, {999747161869591,0,2514870295,0,12883005,0,172812902500,0,77497474609,0}, {999867334196886,0,57047687103,0,5168132970,0,56770214205,0,13679768836,0}, {999999999998635,0,0,0,0,1365,0,0,0,0}, {999681482838156,0,127165765203,0,108837618450,0,19946509880,0,62567268311,0}, {999874763247869,0,89171322256,0,3060,15,32760111805,0,3305314995,0}, {999541979666780,0,50378946810,0,2588166960,0,404076275730,0,976943720,0}, {999841358070819,0,124589027615,0,353500875,0,15665283320,0,18034117371,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999636517446614,0,7871542155,1,90520329915,105,265016055655,0,74625555,0}, {999761567497435,0,35845319120,0,135934683885,0,59262764806,0,7389734754,0}, {999807928592989,0,71811567885,0,2955,8295,91230539135,0,29029288740,1}, {999844130949204,0,36097360811,0,21072426390,0,98195547570,0,503716025,0}, {999999999990429,0,0,0,0,9571,0,0,0,0}, {999785961312804,0,2701069455,0,0,0,205551782790,0,5785834951,0}, {999900595355375,0,113584486,0,10935,0,98572117204,0,718932000,0}, {999719123913461,0,929735835,0,521640,0,241731737508,0,38214091556,0}, {999888380180990,0,40127710680,0,264811,19398,61320698910,0,10171125211,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999743659839469,0,12312360300,0,57882825,0,203107882651,0,40862034755,0}, {999871822818224,0,41776399386,0,4369365000,0,76201317825,0,5830099565,0}, {999795527614418,0,48628852205,0,0,0,155261103131,0,582430246,0}, {999939613182783,0,38354905,0,21693887670,0,35019411131,0,3635163511,0}, {999999999999985,0,0,0,0,15,0,0,0,0}, {999690261943684,0,170794803861,0,4354350,0,130909193584,0,8029704521,0}, {999866890892844,0,8682872885,0,14660,0,85058336510,0,39367883101,0}, {999797714539269,0,64166208450,0,7831893825,0,69332776396,0,60954582060,0}, {999517062439089,0,5729189025,0,680,0,223944202931,0,253264168275,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999850598303749,0,3583245,0,748456035,455,145533063255,0,3116593260,1}, {999651651322633,0,129862345535,0,403585,0,204169118336,0,14316809911,0}, {999660860109294,0,83302408815,0,456,45045,102968847815,0,152868588575,0}, {999805581916088,0,5335426410,0,4684680,0,99081360556,0,89996612266,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999899645499284,0,247301600,0,44833289865,0,29115898071,0,26158011180,0}, {999824277061279,0,7754663415,0,60901200360,210,99105956025,0,7961118711,0}, {999727581056310,0,61790945415,0,38326,0,139047973896,0,71579986053,0}, {999824564239979,0,212955,0,1365,3395,120418699325,0,55016842981,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999811221773639,0,21464902176,0,120,210,64092905015,0,103220418840,0}, {999945639002319,0,17024932520,0,952074060,0,29032941925,0,7351049176,0}, {999860214147279,0,3104773220,0,0,9570,56112118895,0,80568951036,0}, {999801450713394,0,4104830150,0,0,0,159372290171,0,35072166285,0}, {999999999999125,0,0,0,0,875,0,0,0,0}, {999736151456084,0,306186485,0,36141165061,0,220562533655,0,6838658715,0}, {999808594192016,0,2374447755,0,4326572250,0,183688129941,0,1016658038,0}, {999853615786235,0,93031290,0,0,0,142466744235,0,3824438240,0}, {999719665252127,0,72390003800,0,0,0,207474243153,0,470500920,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999800470131086,0,41314545853,0,65481105690,3076,66006460410,0,26727753885,0}, {999483272449588,0,93204254535,0,31663740,0,421421797397,0,2069834740,0}, {999638014022600,0,125408036145,0,54660101925,665,100717447595,0,81200391070,0}, {999820846563922,0,5045034225,0,0,0,159680470358,0,14427931495,0}, {999999999998304,0,0,0,0,1696,0,0,0,0}, {999936007566325,0,8462260620,0,100676955,0,55165893585,0,263602515,0}, {999669103557272,0,178544629200,0,87302158125,0,43532090558,0,21517564845,0}, {999772849524555,0,100785016425,0,36960,0,108119976995,0,18245445065,0}, {999728399858569,0,148823088050,0,120,121,121977721695,0,799331445,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999845313876418,0,1421880405,0,45047706075,5460,84991215706,0,23225315936,0}, {999900462133029,0,49452571455,0,475020,0,49887036705,0,197783791,0}, {999802246238486,0,88425,0,1429416,0,146126878490,0,51625365183,0}, {999710795837259,0,45025720575,0,132675648106,0,94750604385,0,16752189675,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999961856224299,0,459525,0,11403,0,23109517675,0,15033787098,0}, {999772845108431,0,14067246229,0,162949161375,105,22769136055,0,27369347805,0}, {999833937425440,0,41321954871,0,113975253,0,124026109246,0,600535190,0}, {999771435065497,0,83449725976,0,31686723915,0,100109591727,0,13318892885,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999761107095547,0,3764064634,15,21840,0,216571238904,0,18557579060,0}, {999572565478110,0,2832310995,0,848167320,0,422121585039,0,1632458536,0}, {999808013873907,0,164453364027,0,14745840,120,25444530270,0,2073485821,15}, {999692474691400,0,165106379250,0,28315489035,0,61145302147,0,52958138168,0}, {999999999999880,0,0,0,0,120,0,0,0,0}, {999530194989789,0,3152267756,0,15,0,195115668770,0,271537073670,0}, {999613447987634,0,37331084700,15,115186920240,210,233904741436,0,129265765,0}, {999929007134635,0,131682930,0,13853741265,0,46909135245,0,10098305925,0}, {999624787768900,0,55510228980,0,614872171,0,164886537529,0,154200592420,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999448542827796,0,177640519740,0,98271476775,420,273134873940,0,2410301329,0}, {999947563458323,0,697574283,0,683212755,0,16676628239,0,34379126400,0}, {999926044135733,0,13628319856,0,1,105,46438086745,0,13889457560,0}, {999785399980301,0,2927776644,0,134474567955,0,44525368545,0,32672306555,0}, {999999999981982,0,0,0,0,18018,0,0,0,0}, {999839109632213,0,117424860,0,670282670,0,160064763412,0,37896845,0}, {999775455855941,0,19433485505,0,0,15,190309718286,0,14800940253,0}, {999835834185526,0,1234919136,0,1558557015,0,160044046727,0,1328291596,0}, {999808225788448,0,2444384671,0,225,0,187428573266,0,1901253390,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999829592351509,0,15736508195,0,29900587096,1695,123670393705,0,1100157800,0}, {999924423340580,0,806563695,0,0,0,42214050055,0,32556045670,0}, {999894994608118,0,56051499525,0,210926625,1485,48179051336,0,563912911,0}, {999555837698412,0,35685547716,0,23063040,0,288521679787,0,119932011045,0}, {999999999998409,0,0,0,0,1591,0,0,0,0}, {999433901484539,0,72979630369,0,3516518460,0,488570971942,0,1031394690,0}, {999827033121484,0,1881928000,0,1607731126,8310,145913763220,0,23563447845,15}, {999922060930951,0,40919516,0,29947375815,0,21240224880,0,26710548838,0}, {999930735423071,0,35388370305,0,1276611315,1695,12533064178,0,20066529436,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999838182370205,0,5268623080,0,706500795,0,153051427385,0,2791078535,0}, {999673980499257,0,180364584120,0,36693346690,0,75505405978,0,33456163955,0}, {999829422189816,0,3474535275,0,0,0,159418699751,0,7684575158,0}, {999728064996837,0,5006028300,0,340136175,0,174403733343,0,92185105345,0}, {999999999998635,0,0,0,0,1365,0,0,0,0}, {999811707490379,0,459258555,0,0,0,172789705905,0,15043545161,0}, {999705744996405,0,1205834595,0,4702698015,9555,286662408610,0,1684052820,0}, {999711255140280,0,75655228035,0,138413773680,0,34152047360,0,40523810645,0}, {999605638290131,0,15632520255,0,62084112519,5460,313395334890,0,3249736745,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999742489153842,0,6406186185,0,28567924477,0,173389634231,0,49147101265,0}, {999804948195464,0,169236050950,0,8034845,0,16598198820,0,9209519921,0}, {999752676972087,0,6672550879,0,683212530,665,217575413146,0,22391850693,0}, {999925901534621,0,5349587460,0,1708106400,0,66363685036,0,677086483,0}, {999999999999880,0,0,0,0,120,0,0,0,0}, {999734350852296,0,26360056170,0,165754774185,0,70633350385,0,2900966964,0}, {999833781545616,0,107929371335,0,3343500615,120,21890055184,0,33055527130,0}, {999600652824061,0,124093849440,0,7074202800,0,96264653034,0,171914470665,0}, {999869185474154,0,23843119875,0,1000764765,0,86196029795,0,19774610746,665}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999815493836591,0,6017200595,0,45135090,0,134234640273,0,44209187451,0}, {999861261602404,0,115746960,0,767145,0,122226202266,0,16395681225,0}, {999576288063679,0,72248085,0,0,9555,212575049610,0,211064629071,0}, {999772432102789,0,218760550,0,4323930,0,215201936396,0,12142876335,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999935340436412,0,1216714815,0,0,0,27533744178,0,35909104595,0}, {999918302185427,0,1379560,0,890,455,59215257195,0,22481176473,0}, {999761957795759,0,19959950718,0,9549660,0,193473490997,0,24599212866,0}, {999927705825208,0,430521435,0,17797557276,8190,16516192206,0,37549895685,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999938602141886,0,4591144041,0,14190540,60060,35126486243,0,21665977230,0}, {999919058406492,0,139357195,0,52253777940,0,18949013045,0,9599445328,0}, {999548423903234,0,14881293015,0,412206795,0,257398085520,0,178884511436,0}, {999545391755466,0,6362053575,0,1159052895,0,441533148574,0,5553989490,0}, {999999999998095,0,0,0,0,1905,0,0,0,0}, {999881101766073,0,12354946215,0,891,0,86886619201,0,19656667620,0}, {999958846995172,0,17398215,15,14572950,0,21981592225,0,19139441423,0}, {999802838089372,0,222622500,0,76028727840,0,115587279798,0,5323280490,0}, {999603061053002,0,23146530,0,80430371595,4530,223204079303,0,93281345040,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999927808684366,0,476289450,0,0,9555,45217068051,0,26497948578,0}, {999927885749709,0,7323261690,0,2732850120,0,61717428778,0,340709703,0}, {999781558980594,0,3149333397,0,120,0,214337091274,0,954594615,0}, {999632591967833,0,121244880960,0,330,0,111654074066,0,134509076811,0}, {999999999999985,0,0,0,0,15,0,0,0,0}, {999940988552287,0,3172209288,0,226951740,0,55308685905,0,303600780,0}, {999848183315749,0,47684809006,0,0,105,94046136560,0,10085738580,0}, {999867298900751,0,211536083,0,64365161445,0,42229268806,0,25895132915,0}, {999930917137779,0,11987272150,0,0,210,55397508661,0,1698081200,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999793452069055,0,19561935890,0,17658515,0,186050342715,0,917993825,0}, {999853326843460,0,4200,0,15,0,98637994110,0,48035158215,0}, {999808256596347,0,442545620,0,53603550,225,186025292585,0,5221961673,0}, {999714279104009,0,83050965525,0,107633360835,0,65809207071,0,29227362560,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999913208434467,0,39127551155,0,2218737885,0,36206084928,0,9239191565,0}, {999840404058847,0,31466723195,0,101684520,0,124932784265,0,3094749173,0}, {999822676394392,0,56184757475,0,9828,0,90230754335,0,30908083970,0}, {999736399903058,0,122520058445,0,71583046095,0,13827405447,0,55669586955,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999782267272463,0,88896381,0,15,0,201139118180,0,16504712961,0}, {999610874876853,0,30496740125,0,7210985175,0,351181594076,0,235803771,0}, {999880575428628,0,57426070362,0,17746,105,30892101411,0,31106381748,0}, {999890794221530,0,328862370,0,0,0,99645983100,0,9230933000,0}, {999999999999985,0,0,0,0,15,0,0,0,0}, {999706213749437,0,27919681170,0,13009170438,0,237137667925,0,15719731030,0}, {999834399605219,0,228165,0,8235045,0,123812459871,0,41779471700,0}, {999804083407832,0,25592489600,0,116537270850,0,42727525277,0,11059306441,0}, {999783904545530,0,72435021339,0,20070014965,0,116088271791,0,7502146375,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999857468770454,0,30639243945,0,13290412815,0,98408242886,0,193329900,0}, {999875931215710,0,5903773365,0,397567170,0,108457863040,0,9309580715,0}, {999809257696206,0,15296059173,0,1575134330,0,167290096066,0,6581014210,15}, {999772546849104,0,587288661,0,15,0,224043365575,0,2822496645,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999741004411534,0,92409766400,0,80094463215,0,72139489276,0,14351869575,0}, {999690683284640,0,1021986765,0,120045,210,254892215810,0,53402392530,0}, {999781431895475,0,49387427940,0,892536375,0,163224281700,0,5063858510,0}, {999958910116336,0,522776003,0,943002060,120,16558687771,0,23065417710,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999914448568464,0,58599994680,0,2154602115,16380,12961450981,0,11835367380,0}, {999844791006360,0,2128571460,0,3045,0,134644539033,0,18435880102,0}, {999925889227447,0,16647113598,0,6430263855,0,46425469605,0,4607925495,0}, {999809775690436,0,11810835,0,3643005,0,131958554089,0,58250301635,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999956088482815,0,7836200,0,8092126770,0,35148856190,0,662698025,0}, {999948805497856,0,465683610,0,225,4095,44465613694,0,6263200520,0}, {999939503181495,0,570410,0,9990,0,39750100595,0,20746137510,0}, {999664118490676,0,177751208370,0,7282290,420,153384751366,0,4738266878,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999873476095326,0,243356040,0,937345500,0,103848548835,0,21494654299,0}, {999822679978624,0,66392345985,0,15651034351,0,64720151920,0,30556489120,0}, {999938030342446,0,25957870830,0,504203700,0,27172163375,0,8335418984,665}, {999612367512924,0,31245283645,0,82364393475,0,267734635506,0,6288174450,0}, {999999999989080,0,0,0,0,10920,0,0,0,0}, {999633084632695,0,3751631151,0,512311800,0,361209131145,0,1442293209,0}, {999868129689735,0,3610962755,0,76915020,0,70187284520,0,57995146395,1575}, {999698878739304,0,86174069475,0,330330,0,201945815316,0,13001045575,0}, {999897585891409,0,54008811675,0,13114920,0,35220653700,0,13171528296,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999845243253042,0,4967890020,0,0,210,94915174228,0,54873682500,0}, {999763295728097,0,162428000490,0,31822851060,0,41216618150,0,1236802203,0}, {999756286780562,0,73860360,0,5085039960,0,201533981008,0,37020338110,0}, {999930246047266,0,134971200,0,29546667696,0,24906269553,0,15166044285,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999683675303919,0,2423540,0,2282280,0,148146431796,0,168173558465,0}, {999745977171755,0,70278477570,0,0,0,130726924755,0,53017425920,0}, {999418413461765,0,189461493470,0,129198147015,0,258813916490,0,4112981260,0}, {999900411444525,0,4039035,0,23195055,0,97352023675,0,2209297710,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999801383884911,0,931214130,0,72538476465,1,117397539623,0,7748884870,0}, {999704159491632,0,7185777965,0,159916537365,0,93651730830,0,35086462208,0}, {999968710135426,0,8675075670,0,140324940,241,19954660983,0,2519802740,0}, {999788324354295,0,83597177575,0,0,0,76856224495,0,51222243635,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999806507220530,0,5576566415,0,0,0,167086189480,0,20830023575,0}, {999910766546242,0,4096079187,0,2300705,1,81493836015,0,3641237850,0}, {999581433405395,0,106728273060,0,1785,0,129785808475,0,182052511285,0}, {999827894089921,0,97332960,0,17535696360,15,150028254318,0,4444626426,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999671249132364,0,10262841606,0,65874528720,1365,135673562600,0,116939933345,0}, {999850409604890,0,33329730,0,0,0,148014184370,0,1542881010,0}, {999893314998110,0,205731435,0,225,0,104094774575,0,2384495655,0}, {999841361109955,0,105286728540,0,831426275,0,52100228035,0,420507195,0}, {999999999998620,0,0,0,0,1380,0,0,0,0}, {999554400470249,0,163855428030,0,35598162600,0,245988187728,0,157751393,0}, {999683290728005,0,509052210,0,0,0,249058551260,0,67141668525,0}, {999501685924435,0,67340281765,0,271476780,0,429661973925,0,1040343095,0}, {999873160091006,0,13863438345,0,18219175,0,57653342591,0,55304908883,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999840437008166,0,3691466058,0,0,226,146798258410,0,9073267140,0}, {999891134816879,0,68174987875,0,2292907855,0,15707769690,0,22689517701,0}, {999685566261934,0,21026458245,0,210,8190,289957198021,0,3450073400,0}, {999939231030560,0,12588114365,0,160137705,0,47240324175,0,780393195,0}, {999999999999894,0,0,0,0,106,0,0,0,0}, {999680230009071,0,211982407410,0,13945932000,0,40337844949,0,53503806570,0}, {999723314750136,0,120090884025,0,210,0,141209992079,0,15384373550,0}, {999715632026176,0,810281346,0,158611282830,0,54622970403,0,70323439245,0}, {999620855027335,0,18075706194,0,8378125281,1,351991931894,0,699209295,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999792119735039,0,78960397638,0,564684120,0,128277921690,0,77261513,0}, {999949427707805,0,27544521715,0,77837775,0,21580624765,0,1369307940,0}, {999932495224239,0,33215419658,0,125580,0,34151417168,0,137813355,0}, {999736511480575,0,34258480380,0,145569824400,0,64907630710,0,18752583935,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999761863978579,0,33123009705,0,115328863650,0,66262477776,0,23421670290,0}, {999741228121725,0,26052414515,0,0,0,225067526255,0,7651937505,0}, {999846584944807,0,11860236018,0,34799531130,0,88133299875,0,18621988170,0}, {999970495794498,0,218675,0,0,0,12601407207,0,16902579620,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999753954614095,0,84624160635,0,1179285345,210,111270010560,0,48971929155,0}, {999902237667387,0,17751045978,0,322972650,0,79109495215,0,578818770,0}, {999786794434363,0,1266318900,0,225,1,206065551450,0,5873695061,0}, {999846165497444,0,63902604515,0,450,0,81144108426,0,8787789165,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999822599266377,0,122169521805,0,8766027270,0,18829420273,0,27635764275,0}, {999806861537877,0,3312336380,0,11220540,13651,183433786558,0,6381104994,0}, {999568585448940,0,925887865,0,435014580,0,429351078480,0,702570135,0}, {999852667361495,0,4968501720,0,97192080,0,114255613080,0,28011331625,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999764495536027,0,122720245095,0,17016613020,0,40428432195,0,55339173663,0}, {999699730262935,0,64726438885,0,0,0,159142258080,0,76401040100,0}, {999834985185675,0,84946051725,0,502341840,0,72951144385,0,6615276375,0}, {999545397387100,0,602002765,0,0,0,199553323295,0,254447286840,0}, {999999999998425,0,0,0,0,1575,0,0,0,0}, {999851857397655,0,65797180035,0,0,0,81381789758,0,963632552,0}, {999942725156229,0,28761930,0,6288645090,2730,47747855683,0,3209578338,0}, {999917792743564,0,2503835895,0,26966940,0,30239222496,0,49437231105,0}, {999892673806625,0,31914023505,0,37703505840,0,36669797110,0,1038866920,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999946847372270,0,32155614940,0,0,121,20085425969,0,911586700,0}, {999929938453767,0,884914695,0,3084378795,0,23427510048,0,42664742695,0}, {999944551304782,0,130818870,0,120,120,19374732590,0,35943143518,0}, {999809127168024,0,36906877498,0,32248796580,0,101872877913,0,19844279985,0}, {999999999999879,0,0,0,0,121,0,0,0,0}, {999865023129264,0,729494235,0,95266800720,0,21268982733,0,17711593048,0}, {999798820852615,0,4442963645,0,64600106445,785,96216082860,0,35919993650,0}, {999840734220219,0,25270167518,0,25913607720,0,44149819113,0,63932185430,0}, {999866269332028,0,36202785,0,314837005,1,133347365666,0,32262515,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999698951934070,0,144969556425,0,0,0,146287911420,0,9790598085,0}, {999828301549402,0,604297275,0,2563781220,0,166901324115,0,1629047988,0}, {999799851522845,0,148445365355,0,1785,0,46313273595,0,5389836420,0}, {999824180556542,0,120170610,0,29679838188,0,144464326945,0,1555107715,0}, {999999999999320,0,0,0,0,680,0,0,0,0}, {999763906112697,0,65091873798,0,15,0,170315894875,0,686118615,0}, {999861105024504,0,8137007718,0,0,0,130500501910,0,257465868,0}, {999941672610730,0,475074225,0,0,0,31559773845,0,26292541200,0}, {999791849366977,0,26844899655,0,403132710,8190,155868806893,0,25033785575,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999621644743674,0,44022189393,0,14774760,785,229341768083,0,104976523305,0}, {999634981417440,0,137480098995,0,15,0,132500050225,0,95038433325,0}, {999773018620813,0,47038618575,0,2865604770,121,170559170121,0,6517985600,0}, {999450067067625,0,75643476865,0,8619030420,0,464893724865,0,776700225,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999838653339944,0,40686520695,0,0,0,118719970721,0,1940168640,0}, {999943749144013,0,31309425,0,21404135745,121,17702632521,0,17112778175,0}, {999765393425147,0,3542647983,0,1785,0,231042133010,0,21792075,0}, {999699834200935,0,78308555535,0,91050828975,120,115062625686,0,15743788749,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999762036692785,0,15830396715,0,13952301090,0,207064561160,0,1116048250,0}, {999794697358547,0,11280341520,0,0,0,192685766460,0,1336533473,0}, {999704701992788,0,150641729973,0,41953201290,0,86893562864,0,15809513085,0}, {999821196291692,0,175987905,0,98484360,0,173632301055,0,4896934988,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999721306366947,0,1594443515,0,15,0,178375967010,0,98723222513,0}, {999768214910317,0,63067301430,0,0,105,148082498388,0,20635289760,0}, {999858675997070,0,73905986715,0,3045050190,0,57046247700,0,7326718325,0}, {999796862221152,0,63767385,0,0,210,195874755280,0,7199255973,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999442084894282,0,139435760380,0,691892580,300300,215998601798,0,201788550660,0}, {999756285441130,0,83221968216,0,102832441530,0,14678275369,0,42981873755,0}, {999910294325730,0,59412944970,0,1384503135,120,28326260265,0,581965780,0}, {999878425036876,0,101301424618,0,680,0,17252168795,0,3021369031,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999603038886768,0,54308007998,0,862140825,0,341250667390,0,540297019,0}, {999838881578130,0,18704458073,0,0,0,86467697061,0,55946266736,0}, {999853067005439,0,127931629376,0,79493505,0,9593882545,0,9327989135,0}, {999977902256595,0,1418392010,0,951599040,120,19014690620,0,713061615,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999952341271871,0,1047643231,0,1931079150,210,44270905483,0,409100055,0}, {999704988148354,0,2996980890,0,79750671000,0,212238279705,0,25920051,0}, {999910750416299,0,5828012425,0,611148735,15,82461747405,0,348675121,0}, {999772086123299,0,20094743035,0,163774550940,0,41332978016,0,2711604710,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999867518860024,0,50523170880,0,211,0,64232873930,0,17725094955,0}, {999663929337729,0,82704504575,0,7565543520,0,62460797666,0,183339816510,0}, {999896466462700,0,26821939630,0,12729491775,0,63485263415,0,496842480,0}, {999882000403273,0,23595220705,0,14303590665,0,67233904757,0,12866880600,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999954436819179,0,2926333050,0,0,2850,22709641570,0,19927203351,0}, {999804539175514,0,2953105410,0,0,0,188878733525,0,3628985551,0}, {999867494876860,0,45744860,0,1150710,0,101379265795,0,31078961775,0}, {999909794678749,0,72206435,0,1366,0,89943721590,0,189391860,0}, {999999999999565,0,0,0,0,435,0,0,0,0}, {999742753267330,0,274231545,0,1430900,0,236277318055,0,20693752170,0}, {999755611526292,0,28634893486,0,76328737485,2955,110329182600,0,29095657167,15}, {999915702330139,0,30931970475,0,720825,0,39966135951,0,13398842610,0}, {999962951565279,0,497922196,0,0,3075,21034439670,0,15516069675,105}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999888724253329,0,2771314455,0,1014136515,0,3424740180,0,104065555521,0}, {999760703342055,0,18456614610,0,15091440,0,179162476825,0,41662475070,0}, {999905720453399,0,29059675415,0,17492236546,0,45022383150,0,2705251490,0}, {999893040265080,0,43622716020,0,1508827320,0,57916063955,0,3912127625,0}, {999999999999985,0,0,0,0,15,0,0,0,0}, {999844663403844,0,25836369240,0,0,0,129220571446,0,279655470,0}, {999835604557543,0,78440086860,0,470,0,83784191267,0,2171163860,0}, {999953203826724,0,15395835,0,25213519695,0,18701423345,0,2865834401,0}, {999499153844209,0,114317016626,0,63190747620,0,271478496915,0,51859894630,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999519469892465,0,2534040970,0,795314520,680,474452479545,0,2748271820,0}, {999750776918205,0,139977889445,0,32162130,0,104536814630,0,4676215590,0}, {999862922113617,0,22730,0,6233942925,0,126727087613,0,4116833115,0}, {999879780843155,0,5994574440,0,1905,0,83689176755,0,30535403745,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999859704171463,0,39358493125,0,4905851615,0,44135580792,0,51895903005,0}, {999795183454633,0,228273420,0,108649150675,120,87016644732,0,8922476420,0}, {999537739019600,0,5174831025,0,120,0,228323854090,0,228762295165,0}, {999929339322284,0,3044870340,0,62614364685,120,4277923431,0,723519140,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999859392942149,0,88986613325,0,56035980,0,44648827005,0,6915581541,0}, {999863545742378,0,114660,0,748456021,0,134279049643,0,1426637298,0}, {999928154640712,0,5205150615,0,379321800,0,66260518860,0,368013,0}, {999705263101885,0,135564806061,0,75075,0,152025328849,0,7146688130,0}, {999999999999335,0,0,0,0,665,0,0,0,0}, {999681261016594,0,89757762390,0,0,0,87566016725,0,141415204291,0}, {999943954724870,0,5965925420,0,33286678425,15,14381283360,0,2411387910,0}, {999847227630151,0,2694625275,0,2657655,0,71791595724,0,78283491195,0}, {999934327090164,0,1743543795,0,970494540,0,62584682685,0,374188816,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999933411663405,0,10268004453,0,180180,0,52678954811,0,3641197151,0}, {999911197065466,0,85954050,0,49503113205,0,21633806529,0,17580060750,0}, {999674869351596,0,915493691,3003,837992625,1365,317977666875,0,5399490845,0}, {999842697669997,0,9993953585,0,47865416235,0,93105414958,0,6337545225,0}, {999999999999985,0,0,0,0,15,0,0,0,0}, {999804635575721,0,34372500411,0,11508,0,107876746340,0,53115166020,0}, {999942029620575,0,3746663115,0,31036111,0,39972708559,0,14219971640,0}, {999844122851767,0,19320,0,105,0,110829056550,0,45048072258,0}, {999916359298141,0,969341835,0,6841674840,0,71090705779,0,4738979405,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999780449072553,0,55285198365,0,70922676825,1365,72498660267,0,20844390625,0}, {999856494807697,0,10826152155,0,15,0,64817023463,0,67862016670,0}, {999955446409584,0,2669690805,0,1575,0,10608394301,0,31275503735,0}, {999949697200427,0,22082703105,0,644053620,0,22887065827,0,4688977021,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999909453955418,0,1466395206,0,0,0,37648680236,0,51430969140,0}, {999850832012275,0,60667747210,0,40950,0,72421534305,0,16078665260,0}, {999849193529857,0,1954684215,0,0,0,115377131298,0,33474654630,0}, {999839312798454,0,58992570,0,0,0,27919692600,0,132708516376,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999724535350571,0,23389158,0,59692263540,2835,215735455595,0,13538301,0}, {999768479776351,0,198789801,0,44960525610,0,182312600580,0,4048307658,0}, {999663153025023,0,20022131836,0,16367567580,9555,300271140311,0,186125695,0}, {999836968116864,0,1647713096,0,9512242740,0,151460393435,0,411533865,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999881000623308,0,49156293,0,0,0,114439770435,0,4510449964,0}, {999769500996041,0,30034499498,0,1531635,5460,140334209631,0,60128757735,0}, {999750467493079,0,83755580133,0,0,0,165615478077,0,161448711,0}, {999772818590299,0,14221641750,0,22819106310,0,163314645770,0,26826015871,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999800419386909,0,55125,0,196396200,0,198807716176,0,576445590,0}, {999839659761854,0,22397327796,0,86644973415,0,37111782225,0,14186154710,0}, {999788958396832,0,25164610590,0,91455330,15,161702469900,0,24083067333,0}, {999558012740960,0,89894933730,0,15,0,351046338680,0,1045986615,0}, {999999999991810,0,0,0,0,8190,0,0,0,0}, {999732988814835,0,96948466680,0,38110493850,0,77708529485,0,54243695150,0}, {999649354439359,0,8025471090,0,92591787,0,209246734916,0,133280762848,0}, {999874094836210,0,3396286215,0,0,0,114684188205,0,7824689370,0}, {999943544528957,0,5143713213,0,1935404835,8190,49356523170,0,19821635,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999776938152551,0,72483120,0,0,2940,220901621143,1,2087740245,0}, {999964155069911,0,4248077595,0,17343691,0,31387346335,0,192162468,0}, {999757637188811,0,5304837331,0,172758915,0,30834916045,0,206050298898,0}, {999763119133058,0,118628984985,0,72322645395,0,33322430452,0,12606806110,0}, {999999999997164,0,0,0,0,2836,0,0,0,0}, {999839533762032,0,62929538975,0,11403,0,78475165309,0,19061522281,0}, {999779273968031,0,45069326865,0,137291700,105,171862877233,0,3656536066,0}, {999792450030374,0,120202084485,0,15,0,86638254386,0,709630740,0}, {999815270353051,0,21469184100,0,0,0,139699849070,0,23560613779,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999827385824579,0,147770529975,0,99908446,0,10205016425,0,14538720575,0}, {999893394877524,0,574545420,0,34163584695,0,60710195056,0,11156797305,0}, {999900714592779,0,1217222370,0,0,2730,81598237590,0,16469944531,0}, {999913226062627,0,44386656405,0,114660,0,42228716763,0,158449545,0}, {999999999999335,0,0,0,0,665,0,0,0,0}, {999839114443173,0,15765,0,655748,0,123890635434,0,36994249880,0}, {999932003932949,0,40695170336,0,8420641776,0,11344904991,0,7535349948,0}, {999733538916456,0,26394504466,0,156794858220,0,75844157770,0,7427563088,0}, {999966568631253,0,1840486,0,2106653640,0,31239815463,0,83059158,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999925365103042,0,6951914376,0,0,225,19048452224,0,48634530133,0}, {999964018519206,0,131715,0,3045,0,17399265150,0,18582080884,0}, {999825514058368,0,1389823830,0,31975331115,15,134049969341,0,7070817331,0}, {999817496907189,0,20635842390,0,135183513465,0,11297813866,0,15385923090,0}, {999999999994435,0,0,0,0,5565,0,0,0,0}, {999873907305891,0,38787156409,0,12345375,0,87005646465,0,287545860,0}, {999837609347019,0,13373548420,0,31300880535,0,50619693206,0,67096530820,0}, {999837091128547,0,60833243933,0,26769577800,0,63392715277,0,11913334443,0}, {999813919362979,0,33243736500,0,686455771,682110,138250035425,0,13899727215,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999669903431784,0,18894924405,0,94191217575,210,207035853226,0,9974572800,0}, {999775816422232,0,1280683005,0,2940,0,214312262838,0,8590628985,0}, {999962722498356,0,1303185,0,1776232200,0,34247233369,0,1252732890,0}, {999610269756109,0,1540109056,0,373753380,0,387047783790,0,768597665,0}, {999999999999790,0,0,0,0,210,0,0,0,0}, {999823173601058,0,155849532790,0,9014580,0,20188446379,0,779405193,0}, {999730795315579,0,47860306515,0,161070,15,210946658466,0,10397558355,0}, {999699527961473,0,168015109893,0,29651054370,0,44175808229,0,58630066035,0}, {999773628555730,0,11612720100,0,20962305,0,197243992360,0,17493769505,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999863414042476,0,18365089743,0,0,1,116735968390,0,1484899390,0}, {999571049975175,0,2654531880,0,0,0,175575142270,0,250720350675,0}, {999776008573530,0,130633634250,0,56128772700,0,35134828330,0,2094191190,0}, {999617189961955,0,37923167100,0,123274112535,0,221557967397,0,54791013,0}, {999999999999999,0,0,0,0,1,0,0,0,0}, {999950297843127,0,56213535,0,16428218625,0,26307907483,0,6909817230,0}, {999928255794832,0,61116998040,0,61786650,210,9451547463,0,1113872805,0}, {999636979607300,0,57497668950,0,522080940,0,152201125610,0,152799517200,0}, {999703182135879,0,4702845,0,105,1,154373275524,0,142439885646,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999839133329886,0,92401426683,0,0,1365,66306986805,0,2158255261,0}, {999502763753329,0,170412842955,0,91516961070,0,232097163971,0,3209278675,0}, {999805645173951,0,11166261016,0,0,0,116269349430,0,66919215603,0}, {999972975885884,0,446141585,0,644413785,0,8824501081,0,17109057665,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999930284566013,0,15305235095,0,0,0,30093672567,0,24316526325,0}, {999891052489664,0,44223387000,0,3798584791,105,45696567795,0,15228970645,0}, {999791278636875,0,2582281585,0,133715102430,0,48268494645,0,24155484465,0}, {999854363135409,0,5242999050,0,24114720630,210,114046305811,0,2232838890,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999803816654941,0,106202103840,0,1365,0,41823902363,0,48157337491,0}, {999885052406199,0,62786025,0,487638936,0,114385487485,0,11681355,0}, {999872878477334,0,9747967740,0,0,0,112219459801,0,5154095125,0}, {999821106446120,0,10135585425,0,0,0,157414409365,0,11343559090,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999891876334319,0,730270390,0,458558101,0,106540585470,0,394251720,0}, {999611610596125,0,70995860565,0,2045,165165,131748015204,0,185645360896,0}, {999834966388810,0,1776187140,0,15,0,162481792640,0,775631395,0}, {999813492178134,0,161651858100,0,680,0,8540603171,0,16315359915,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999748402328819,0,25090026330,0,15,210,195483064211,0,31024580415,0}, {999859142530887,0,8651763121,0,18015917010,0,113596157502,0,593631480,0}, {999851971133893,0,55433865,0,0,120,147319889301,0,653542821,0}, {999954779020038,0,309451415,0,0,0,28098258962,0,16813269585,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999902343521216,0,62395370499,0,136906770,0,34865737400,0,258464115,0}, {999823618951727,0,112644575905,0,124488,0,46796470385,0,16939877495,0}, {999634185658494,0,24185707455,0,7567560,0,244792586561,0,96828479930,0}, {999583121545745,0,171771618000,0,15473626350,1365,229589968650,0,43239890,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999918934932382,0,156290,0,3060,1575,80819387130,0,245519563,0}, {999515451604718,0,55900729982,0,1179283560,0,426961224533,0,507157207,0}, {999759999448811,0,164716947213,0,330331,0,73433110805,0,1850162840,0}, {999858174116995,0,583444800,0,999893895,0,129073215590,0,11169328720,0}, {999999999999879,0,0,0,0,121,0,0,0,0}, {999948239141457,0,13335688,0,21528356230,0,12403946970,0,17815219655,0}, {999889866193345,0,3873828273,0,42525,1380,91561753587,0,14698180890,0}, {999933898446178,0,44440592208,0,895182060,0,7221510424,0,13544269130,0}, {999957509797400,0,100690920,0,4153809660,1680,14775128220,0,23460572120,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999933821198725,0,21333886340,0,172202940,0,42603412525,0,2069299470,0}, {999867182752522,0,6284363730,0,401531130,0,124394068880,0,1737283738,0}, {999896148475578,0,14727525,0,3706316315,0,97028723655,0,3101756927,0}, {999714888169385,0,193016944050,0,20127547440,0,43013443825,0,28953895300,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999867652210235,0,3342775815,0,0,0,125957990555,0,3047023395,0}, {999777334653269,0,568533840,0,147623035560,0,27216709715,0,47257067616,0}, {999716423775560,0,4323338565,0,369134220,0,171864423870,0,107019327785,0}, {999650332024305,0,21884118720,0,438964320,0,317189961695,0,10154930960,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999964368276204,0,1027640685,0,15,0,31458564375,0,3145518721,0}, {999836570710132,0,269919783,0,0,0,144527067780,0,18632302305,0}, {999948085178835,0,32431983450,0,125411730,0,17543589960,0,1813836025,0}, {999747892396414,0,902256110,0,1809457650,0,248591675491,0,804214335,0}, {999999999999670,0,0,0,0,330,0,0,0,0}, {999776154443869,0,42644725341,0,125121511515,0,31650159942,0,24429159333,0}, {999901631614572,0,52751874175,0,15,6306435,43164453685,0,2445751118,0}, {999676632640056,0,12535511625,0,66058402410,0,243187053105,0,1586392804,0}, {999800814136613,0,25717993051,0,89678604016,1590,53599243050,0,30190021680,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999869695524904,0,5719841855,0,16516980480,0,39008349376,0,69059303385,0}, {999840004833375,0,4802076105,0,22536204600,0,102989181880,0,29667704040,0}, {999776887439993,0,81951892740,0,0,0,64427568011,0,76733099256,0}, {999827984495279,0,158723787213,0,0,0,9345788628,0,3945928880,0}, {999999999998425,0,0,0,0,1575,0,0,0,0}, {999816005815402,0,4227203610,0,582982400,0,166301422733,0,12882575855,0}, {999983994996454,0,4982306446,0,0,0,8921293805,0,2101403295,0}, {999945601444296,0,5272179293,0,593422830,0,48064096301,0,468857280,0}, {999893131124891,0,36810542630,0,0,0,9984139714,0,60074192765,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999895504342334,0,41414378175,0,345,0,59748119800,0,3333159346,0}, {999746982994439,0,13255187030,0,180570570180,0,57495007176,0,1696241175,0}, {999737871876458,0,123462587445,0,41556039736,0,87449470655,0,9660025706,0}, {999846121710945,0,116831530845,0,2842925085,0,11356755560,0,22847077565,0}, {999999999999880,0,0,0,0,120,0,0,0,0}, {999626159871294,0,101603447400,0,3515380260,0,94554126046,0,174167175000,0}, {999603914400874,0,195513360,0,151561410,330,395499944811,0,238579215,0}, {999891896419163,0,17701730865,0,1303908606,0,78609642685,0,10488298681,0}, {999910824191054,0,2920332481,0,105,120,31029418780,0,55226057460,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999882816592946,0,442056828,0,59824159395,5460,32844996776,0,24072188595,0}, {999871261536261,0,3219093633,0,50720670,0,101610259680,0,23858389756,0}, {999799047281164,0,48065925066,0,0,0,113797703210,0,39089090560,0}, {999899506705929,0,55545455,0,46410,0,92781672461,0,7656029745,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999588644711376,0,24164868,0,0,0,204097458165,0,207233665591,0}, {999868368377874,0,680,0,0,0,92142003551,0,39489617895,0}, {999803277350820,0,48949895,0,11505585,0,191073841265,0,5588352435,0}, {999865099543616,0,51091580750,0,0,0,82627372549,0,1181503085,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999724996719264,0,62693030766,0,379321800,15,180935747428,0,30995180727,0}, {999951005033651,0,630772221,0,0,0,20743967753,0,27620226375,0}, {999892408909550,0,9524890830,0,176486730,15,96649888715,0,1239824160,0}, {999940840278917,0,209055,0,120,0,43287931583,0,15871580325,0}, {999999999999790,0,0,0,0,210,0,0,0,0}, {999784019000295,0,26570446910,0,1397775,0,168112680220,0,21296474800,0}, {999877017160247,0,976584170,0,90300,0,121880781978,0,125383305,0}, {999944064901140,0,248509460,0,8134521060,0,14953205780,0,32598862560,0}, {999713396107744,0,202198875845,0,989863875,0,83401311436,0,13841100,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999802952613657,0,34605353520,0,54872197380,0,98482142863,0,9087692580,0}, {999951829555590,0,3352202805,0,2078505,0,27491966455,0,17324196645,0}, {999873432731169,0,4636545760,0,0,0,118064776761,0,3865946310,0}, {999923769801844,0,106226720,0,56731193610,0,11874472455,0,7518305371,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999654647945894,0,8329153875,0,283558275,0,189344605461,0,147394736495,0}, {999878609552345,0,29948515175,0,10908654120,0,34568664390,0,45964613970,0}, {999584891418206,0,3951997405,0,503993490,0,407652905706,0,2999685193,0}, {999866850796561,0,10586385,0,105387882810,0,27584205993,0,166528251,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999918909453855,0,2078505,0,660870,0,21482147145,0,59605659625,0}, {999886170638616,0,13070391421,0,15,0,88354390765,0,12404579183,0}, {999840333868546,0,853892750,0,3322158840,0,153692829976,0,1797249888,0}, {999975334373963,0,3667800,0,1161825,0,15218309339,0,9442487073,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999841350274666,0,62412470,0,51840514635,0,104799024525,0,1947773704,0}, {999780760077041,0,88751854780,0,17624900685,210,56130474224,0,56732693060,0}, {999624786370974,0,4064025,0,99226822905,0,213586012636,0,62396729460,0}, {999754601845465,0,90506860080,0,0,1575,154401822350,0,489470530,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999899116549866,0,753576090,0,210,0,84003079653,0,16126794181,0}, {999955972896366,0,216592740,0,0,0,27018600099,0,16791910795,0}, {999762661077714,0,2510654055,0,210,0,199997358220,0,34830909801,0}, {999950934586950,0,4182734300,0,2655252600,0,41990152673,0,237273477,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999800020868190,0,2268722705,0,15,0,197300361410,0,410047680,0}, {999712480037850,0,288596805,0,3060,0,127998454890,0,159232907395,0}, {999671784313915,0,117787536330,0,30,0,96145580320,0,114282569405,0}, {999626426395995,0,81971941545,0,53916594335,420,237360006470,0,325061235,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999477345780938,0,76701762806,0,17036141956,2730,427990181250,0,926130320,0}, {999959576724661,0,3023745530,0,32852820,0,37205065069,0,161611920,0}, {999802942521000,0,107880140139,0,38610000,0,64909789560,0,24228939301,0}, {999893875027351,0,33085739505,0,0,0,68420802814,0,4618430330,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999876085874341,0,88710315,0,65690637870,0,40793581328,0,17341196146,0}, {999788983032217,0,952638120,0,680,0,210024186478,0,40142505,0}, {999955328019838,0,8048774370,0,0,0,35727598272,0,895607520,0}, {999882756957967,0,6642153080,0,0,150150,75133800147,0,35466938656,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999940702747229,0,3762034824,0,0,90300,55407635357,0,127492290,0}, {999866216241136,0,11201434885,0,64324275,0,122161859681,0,356140023,0}, {999806769627825,0,9805097115,0,0,0,181508800295,0,1916474765,0}, {999867918333114,0,105,0,0,0,96763358971,0,35318307810,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999832851217524,0,142916910,0,187297110,0,157878358315,0,8940210141,0}, {999863016628310,0,40849757160,0,0,455,80654242215,0,15479371860,0}, {999752251310054,0,58767959970,0,88798725015,0,79168387501,0,21013617460,0}, {999733214726325,0,1887991980,0,7387380,0,171494917650,0,93394976665,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999826059519194,0,246472800,0,210,8190,173693906930,0,92675,1}, {999907952480799,0,50245231855,0,1358611800,0,35218041935,0,5225633611,0}, {999910486448455,0,8616474603,0,244679191,1575,80314900871,0,337495305,0}, {999870846397748,0,26257534656,0,60442200,0,101387635080,0,1447990316,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999879661108331,0,31490396210,0,0,0,66703695774,0,22144799685,0}, {999925437621978,0,33032448555,0,1634712170,1575,39895194370,0,21352,0}, {999802383252297,0,84422001300,0,65900586571,0,7397097024,0,39897062808,0}, {999845604856499,0,88844571615,0,127698480,0,17582359095,0,47840514311,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999899976553309,0,75469165905,0,0,0,18255200435,0,6299080351,0}, {999819725333969,0,31232880,0,0,0,166845617570,0,13397815581,0}, {999508177775170,0,10950024540,0,33229770,0,455835387935,0,25003582585,0}, {999678562669784,0,28912780865,0,2927882686,0,289458804465,0,137862200,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999915913737932,0,43048588695,0,1365,0,20948113750,0,20089558258,0}, {999906552635519,0,81044883591,0,413775180,0,4251884975,0,7736820735,0}, {999916984354220,0,206565900,0,0,0,72569521265,0,10239558615,0}, {999895801469784,0,300660481,0,37478581140,0,57427914990,0,8991373605,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999899290947051,0,58006253165,0,1786,0,18989148327,0,23713649671,0}, {999758881452155,0,21766402905,0,10166987730,0,198439711820,0,10745445390,0}, {999728317606699,0,3956486725,0,48932924040,0,218774894010,0,18088526,0}, {999827796114290,0,47985,0,3599115,0,122181314375,0,50018924235,0}, {999999999999999,0,0,0,0,1,0,0,0,0}, {999814665254434,0,13751785101,0,141683086545,0,25290859755,0,4609014165,0}, {999692835365766,0,179186579355,0,1,5460,118619054064,0,9358995354,0}, {999837150632979,0,71172575566,0,11744868135,0,75345972135,0,4585951185,0}, {999871355868819,0,35017902480,0,210,1575,83384814360,0,10241412556,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999947103208505,0,16390426965,0,2792549760,0,26157811219,0,7556003551,0}, {999909868032505,0,22769305630,0,8411157756,0,58774759589,0,176744520,0}, {999751606671526,0,106058544075,0,23929564935,0,117064466865,0,1340752599,0}, {999921488865481,0,3383751820,0,300570270,0,70538744799,0,4288067630,0}, {999999999998425,0,0,0,0,1575,0,0,0,0}, {999812377219979,0,20341150651,0,613407795,0,163310745115,0,3357476460,0}, {999809949119546,0,3330210,0,244680765,0,189418772825,0,384096654,0}, {999789900934043,0,590851425,0,0,0,208108909187,0,1399305345,0}, {999968941833980,0,10001265615,0,4911031125,0,16015586935,0,130282345,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999908834780475,0,5717075,0,0,0,90813789320,0,345713130,0}, {999812380409112,0,51765744450,0,68712949995,0,59947770670,0,7193125773,0}, {999791199523402,0,45651616740,0,646277835,1,147069317525,0,15433264497,0}, {999715865374476,0,310697625,0,275760,0,253335502521,0,30488149618,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999829412187465,0,28609761470,0,1319055675,0,135233062805,0,5425932585,0}, {999936773369614,0,16093387290,0,2583945,4201,29313003380,0,17817651570,0}, {999976078149565,0,131492340,0,645705060,0,8151464295,0,14993188740,0}, {999838141885872,0,4796279113,0,5903188215,0,81695385540,0,69463261260,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999836761210496,0,473142090,0,2479216740,0,160205479334,0,80951340,0}, {999936495429510,0,50252925480,0,814043700,0,6267525285,0,6170076025,0}, {999760460148807,0,18872755546,0,15918630,0,153653176500,0,66998000517,0}, {999889484839499,0,1159526551,0,680,0,98481414965,0,10874218305,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999942716808689,0,17358913515,0,2563781220,0,34011469955,0,3349026621,0}, {999877507803896,0,95595318,0,52240788600,0,50511700941,0,19644111245,0}, {999847528702540,0,6575251,0,1440105,0,112605831778,0,39857450326,0}, {999822256708149,0,29902040075,0,0,0,147746776380,0,94475396,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999901551291899,0,104556900,0,35505,0,90948479275,0,7395636421,0}, {999970857454906,0,3025171,0,9390381000,0,19232205623,0,516933300,0}, {999875956308399,0,52615733865,0,14583605611,0,31675835175,0,25168516950,0}, {999968392525696,0,99660890,0,15,0,28476431549,0,3031381850,0}, {999999999999999,0,0,0,0,1,0,0,0,0}, {999931789936845,0,170850,0,1785,0,34124637892,0,34085252628,0}, {999813919424038,0,66908205,0,2045949360,0,183686150887,0,281567510,0}, {999715897267242,0,152641940340,0,43723680,0,128743100940,0,2673967798,0}, {999729635056047,0,2201063250,0,164847560790,0,94420494148,0,8895825765,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999862799942886,0,3077131718,0,1786,0,93790632975,0,40332290635,0}, {999850004832794,0,131855130,0,1106837550,0,134251026431,0,14505448095,0}, {999591719988030,0,1489732726,0,1318852080,0,400854552839,0,4616874325,0}, {999882128231587,0,42674914485,0,10726252320,0,38215920993,0,26254680615,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999950291528774,0,21327254265,0,184264080,0,23120318050,0,5076634831,0}, {999570454635710,0,896539567,0,0,0,225054318913,0,203594505810,0}, {999678643308303,0,23669811480,0,50908747890,0,244157939572,0,2620192755,0}, {999847363964251,0,3280400075,0,0,0,148809980275,0,545655399,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999927973465266,0,35053320,0,0,0,62787258960,0,9204222454,0}, {999666349685834,0,2189644566,0,186696510,0,330557025205,0,716947885,0}, {999873993431116,0,1236705,0,97181760,0,125067765858,0,840384561,0}, {999894515322080,0,2130023100,0,43303260,0,57790551010,0,45520800550,0}, {1000000000000000,0,0,0,0,0,0,0,0,0}, {999743282172941,0,94595983375,0,76650,0,155360835873,0,6760931161,0}, {999718198948027,0,17761914935,0,10597036905,0,219140906198,0,34301193935,0}, {999911762595931,0,51069560115,0,4949490,0,29532230270,0,7630664194,0}, {999729016236669,0,63973940271,0,0,5005,72711517945,0,134298300110,0}}; long long small_coefficients[17*2 + 1][17 + 1]; long long coefficients[17*3 + 1][17*2 + 1][17 + 1]; long long factorials[20]; int mno(long long x){ if(x < 10){ return x; } long long y = 1; while(x > 0 && y > 0){ y *= (x % 10); x /= 10; } return mno(y); } // so, basically, we start with some factor, and we fill in // the remaining first D digits. vector<long long> generate_counter(int D, vector<long long> factors){ int original_size = factors.size(); vector<long long> RES(10, 0); for(int l = 0; l < factors.size(); l++){ if(factors[l] < 10){ for(int i = 0; i < 10; i++){ RES[i] += MAP[D][factors[l]][i]; } factors.erase(factors.begin() + l); l--; continue; } if(D == 16){ vector<long long> vec; for(int i = 0; i < 10; i++){ RES[i] += DEG16[factors[l]][i]; } factors.erase(factors.begin() + l); l--; continue; } if(D == 15){ vector<long long> vec; for(int i = 0; i < 10; i++){ RES[i] += DEG15[factors[l]][i]; } factors.erase(factors.begin() + l); l--; continue; } } if(factors.size() > 0){ int amts[3]; // if we can append any 5 whatsoever, and if the factor is not even. if(D >= 1){ amts[0] = 0; amts[1] = 1; amts[2] = 0; long long v0 = 1; long long v1 = 5; long long v2 = 1; long long v, summand; while(true){ // this is the crux of the algorithm. // first assume there is a five somewhere. // then adding any 2 will make things 0, // so we only have prime factors 3, 5, 7. // position 0 is 3, position 1 is 5, position 2 is 7. summand = factorials[D]/(factorials[amts[1]]*factorials[amts[2]]*factorials[D-amts[1]-amts[2]]) * small_coefficients[amts[0]][D - amts[1] - amts[2]]; v = v0 * v1 * v2; for(int l = 0; l < factors.size(); l++){ RES[mno(v * factors[l])] += summand; } if(amts[0] == 2*(D - amts[1] - amts[2])){ amts[0] = 0; v0 = 1; } else { amts[0]++; v0 *= 3; continue; } if(amts[1] + amts[2] == D){ amts[1] = 1; v1 = 5; } else { amts[1]++; v1 *= 5; continue; } if(amts[2] == D - 1){ amts[2] = 0; v2 = 1; } else { amts[2]++; v2 *= 7; continue; } break; } } amts[0] = 0; amts[1] = 0; amts[2] = 0; long long v0 = 1; long long v1 = 1; long long v2 = 1; long long v, summand; while(true){ // again, this is the crux of the algorithm. // we assume there is NO five anywhere. // So we only have prime factors 2, 3, 7. // position 0 is 2, position 1 is 3, position 2 is 7. summand = coefficients[amts[0]][amts[1]][D - amts[2]]; if(summand > 0){ summand *= factorials[D] / (factorials[amts[2]] * factorials[D - amts[2]]); v = v0 * v1 * v2; for(int l = 0; l < factors.size(); l++){ RES[mno(v * factors[l])] += summand; } amts[0]++; v0 *= 2; continue; } else { amts[0] = 0; v0 = 1; } if(amts[1] == 2*(D - amts[2])){ amts[1] = 0; v1 = 1; } else { amts[1]++; v1 *= 3; continue; } if(amts[2] == D){ amts[2] = 0; v2 = 1; } else { amts[2]++; v2 *= 7; continue; } break; } } // all the remaining cases will give us necessarily a 0. long long z = original_size; for(int i = 0; i < D; i++){ z *= 10ll; } for(int i = 0; i < 10; i++){ z -= RES[i]; } RES[0] += z; return RES; } void process(){ long long N; cin >> N; N++; long long x = 1; long long leading_digit = 1; long long power = 1; int degrees = 0; vector<long long> counter(10, 0); vector<long long> ans(10, 0); while(x <= N){ // we include all of them exclusive of the upper range. for(int i = 0; i < 10; i++){ ans[i] += counter[i]; } if(degrees == 18) break; counter = generate_counter(degrees, {leading_digit}); leading_digit++; x += power; if(leading_digit == 10){ leading_digit = 1; power *= 10ll; degrees++; } } if(leading_digit == 1){ leading_digit = 9; degrees--; power /= 10ll; } x -= power; // cout << N << endl; // cout << x << endl; if(N >= MAX){ for(long long l = MAX; l < N; l++){ ans[mno(l)]++; } for(int i = 0; i < 10; i++){ cout << ans[i] << ' '; } cout << '\n'; return; } else { power /= 10ll; } // cout << power << endl; // so now we have the following situation: // MAX > N >= x // and we wish to calculate for all the numbers up to, but excluding, N. // currently, ans calculates for all the numbers up to, but excluding, x. vector<long long> digits; long long N_copy = N; while(N > 0){ digits.push_back(N%10ll); N /= 10ll; } N = N_copy; long long factor = digits.back(); for(int i = digits.size() - 2; i >= 0; i--){ // cout << x << endl; vector<long long> input; if(x <= N){ // we increase x. int upper_range = digits[i]; if(i != 0 && digits[i - 1] >= 5){ upper_range = digits[i] + 1; } for(long long d = 0; d < upper_range; d++){ input.push_back(factor * d); } vector<long long> counter = generate_counter(i, input); for(int j = 0; j < 10; j++){ ans[j] += counter[j]; } x += power * upper_range; } else { // we decrease x. int lower_range = digits[i]; if(i != 0 && digits[i - 1] >= 5){ lower_range = digits[i] + 1; } for(long long d = 9; d >= lower_range; d--){ input.push_back(factor * d); } vector<long long> counter = generate_counter(i, input); for(int j = 0; j < 10; j++){ ans[j] -= counter[j]; } x -= power * (10ll - lower_range); } factor *= digits[i]; power /= 10ll; } for(int i = 0; i < 10; i++){ cout << ans[i] << ' '; } cout << '\n'; } void find_coefficients(){ // firstly find the small coefficients. for(int i = 0; i < 17*2 + 1; i++){ for(int k = 0; k < 17 + 1; k++){ small_coefficients[i][k] = 0; if(i > 2*k){ continue; } long long sum = 0; for(int s = max(0, i - k); 2*s <= i; s++){ // so we have: s nines, i - 2*s threes, and k + s - i ones sum += factorials[k]/(factorials[s] * factorials[i - 2*s] * factorials[k + s - i]); } small_coefficients[i][k] = sum; // cout << "i = " << i << " k = " << k << " sum = " << sum << endl; } } // cout << "HERE" << endl; // and now the big coefficients. for(int i = 0; i < 17*3 + 1; i++){ for(int j = 0; j < 17*2 + 1; j++){ for(int k = 0; k < 17 + 1; k++){ // here is how it looks like: // there is i factors of 2 // there is j factors of 3 // all of them are distributed over k fields. coefficients[i][j][k] = 0; if(i > 3*k || j > 2*k){ continue; } // let a be the amount of number 6, and b the amount of fields in which I place values divisible by 2. for(int a = 0; a <= min(min(i, j), k); a++){ for(int b = 0; b <= k - a; b++){ if(i - a > 3*b || i - a - b < 0 || j - a > 2*(k - a - b)){ continue; } long long val = factorials[k] / factorials[a]; val /= factorials[b]; val /= factorials[k - a - b]; // now I place the values 2, 4, 8 on b fields. val *= small_coefficients[i - a - b][b]; // and finally, I place the values 1, 3, 9 on k - a - b fields. val *= small_coefficients[j - a][k - a - b]; coefficients[i][j][k] += val; } } } } } } // the normal main function int main(){ // std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now(); cin.tie(NULL); ios_base::sync_with_stdio(0); factorials[0] = 1; for(long long i = 1; i < 20; i++){ factorials[i] = i * factorials[i - 1]; } find_coefficients(); // cout << "DONE" << endl; int T; cin >> T; for(int v = 0; v < T; v++){ process(); } // std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now(); // std::cerr << "Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[µs]" << std::endl; // std::cerr << "Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds> (end - begin).count() << "[ns]" << std::endl; } // main function used to generate initial MAP values. /* int main(){ cin.tie(NULL); ios_base::sync_with_stdio(0); factorials[0] = 1; for(long long i = 1; i < 20; i++){ factorials[i] = i * factorials[i - 1]; } find_coefficients(); int d = 15; for(long long factor = 0; factor < 1000; factor++){ // cout << "d = " << d << " " << "factor = " << factor << endl; vector<long long> vec = generate_counter(d, factor); cout << "{"; for(int j = 0; j < 10; j++){ cout << vec[j]; if(j != 9){ cout << ','; } } cout << "}"; if(factor != 99){ cout << ","; } cout << '\n'; } } */ |