今天用PHP8.0，PHP7.4，PHP7.2，PHP5.6分别测试了下面一段冒泡，选用了10000个整数，测试结果有点让我吃惊，PHP7.4竟然比5.6还耗时？

PHP8.0：9.5秒左右

PHP7.4：34.6秒左右

PHP7.2：11.8秒左右

PHP5.6：31.7秒左右

机器配置：英特尔i7 9700 3.00GHz 8G

代码：

 <?php
function bubbleSort($array){
  $start = microtime(true);
    do
    {
        $sw = false;
        for($i = 0, $size = count($array) - 1; $i < $size; $i++)
        {
            if( $array[$i] > $array[$i + 1] )
            {
                list( $array[$i + 1], $array[$i] ) =
                        array($array[$i], $array[$i + 1]);
                $sw = true;
            }
        }
    }
    while($sw);
$end = microtime(true);
return $end - $start;
}
$array = [7156743,4231232,8253083,9124151,5813422,2566102,8427162,2309087,4138572,3342799,7053307,4491497,1616565,2257408,159655,9964590,1032033,6744355,9439797,5368114,6796887,6646317,5043181,3763792,7402934,3148756,2661693,1175529,1091264,513164,1066407,8248007,4744396,9319491,7372159,557818,1885594,5799321,2866906,6024166,9142121,9920214,515664,758686,2177622,675320,723277,3209656,7419676,163074,8577770,4216563,6809391,3620952,7980356,4212325,6769708,642049,5387855,7860972,1155213,6454263,6108980,5899610,5773755,3481139,6457428,7659349,9280461,9324335,3683516,8422582,9244549,4199181,9181269,1422171,4874501,9904546,4631827,2294178,67621,3209597,6510741,6877012,6830549,4491098,1089338,3600258,5133148,6477193,1461231,6288361,2931457,7570211,2187972,8705212,1051351,8645400,6364561,331813,7969736,48078,8754396,7214285,4247259,7935666,8636457,9121761,7840212,3268284,1415939,7907833,6477882,7926681,4784846,3308432,2417779,5874185,6908690,7550927,2351379,8369922,3839289,5282836,5940133,6027261,3988048,6991485,4672662,352610,7323298,2642398,400688,6077694,9856683,4647948,4013360,8493140,3769709,1853573,1761425,5185648,9761407,8239308,3112329,4546254,1547740,5530109,420439,8456431,3081036,2771818,6826353,6920326,8054655,2766487,2947587,2042704,9757972,7620250,2395314,7081271,262648,2796003,3158966,119332,7443951,7172327,8612473,1213661,9025900,373899,6399309,8787308,8613207,9511639,3333563,160947,5041748,3754002,8617379,8122785,6525821,5443733,5043111,4580476,8210220,7990699,6623181,7968193,5610949,9018495,5049464,5873598,1814499,8208430,5992931,9258450,5380758,4605404,472111,4406658,4979303,6871421,3193967,3592510,6383061,6527530,3753458,1424809,281533,2370838,9547595,6807355,7814572,4590706,1387832,6024792,2581406,8011013,3992986,8192356,7029508,9042451,4065955,8844008,7250882,58886,8102458,2631640,4664291,8574570,7038299,9643594,5445992,232266,3236105,1829053,6759797,6989564,3253863,7041330,9360403,2801458,3848685,7174975,7392165,5236518,3199768,9973571,3247531,7192754,8165928,277040,6235205,2231883,9121048,3486087,2290769,7223506,6117728,6955060,5798077,3156027,6598655,1244070,3388293,9834761,3073124,148091,6824326,6326987,7189422,6184729,9128445,1038108,3359705,6520611,6274626,6559473,6494183,9522157,3752228,4660111,9799197,9987433,6891994,8920245,3473521,9182763,6143752,9591249,6137824,1941830,2747277,2736479,3185900,6135571,2571240,6259025,6283662,9395566,2586012,3473084,5580296,1714458,4511192,8940001,8235069,785819,5499474,4729252,307976,9251702,9389363,107174,9239136,6281358,9027419,2712658,5464121,5171172,2303908,1601945,7113002,5051185,4338425,298903,1186756,6909666,6557928,7470419,6305233,9143941,943503,1885529,858400,5454696,825531,9093469,6240515,6325006,3822722,6548492,5576708,3212086,6655666,4815845,9493444,5683086,7528504,4957566,854258,9832412,6559512,7967261,4883598,897937,8266165,6070354,7807603,4824094,3540774,4112836,3968036,4484278,5998366,4826436,9938974,6823897,3919906,6179490,3148903,7742629,2727982,8725612,954715,9383649,3541458,448160,5066735,1069962,5405726,5920994,902375,1965238,3888256,5785973,2863176,2154422,1856328,670780,6978516,5397102,4783616,946553,9881380,781983,5772989,9820355,7605881,9692895,5999845,754785,7435524,8727828,9480398,8390240,8111478,3021856,8838400,3178213,4091818,4244127,9099208,4994194,6209366,2987464,780167,9072543,5141886,2636495,9743323,2120403,8033597,4526939,3066956,7914977,5308923,8839946,7735333,2914804,8532841,3735178,3669590,5968366,2463007,3149988,4358606,574485,6171844,3197007,3752699,263663,7441135,2851908,5257857,3650502,5839372,6038024,2723045,981259,8674520,2466368,3101663,6708117,6993308,6168620,4623095,2302231,5008566,2358428,5217036,3541407,6093607,8886626,9509774,8556615,2036614,3868381,9131100,8208459,7065388,2883800,8472122,4506524,5735708,3729980,8157026,1575081,9768004,880071,2556341,8442524,3346439,5658004,5150642,339748,1826625,9773738,2641979,6835191,2132166,7859016,376599,8225774,6745642,9886373,6782389,8782256,3754754,5913489,6990716,820143,8797290,5462838,5326668,4532998,9192818,3483694,6108079,8960823,4363766,8664420,7403348,7710206,4322425,2553991,8049954,6149050,2327729,691933,2984241,4459895,8550949,3360841,2685670,5296592,3247214,9468059,4078849,7001969,5381549,1069565,7822113,4178839,6532403,3148781,8711837,5725222,6632476,4819917,4686046,996242,3484338,2089394,8706448,7806764,4643386,6756402,3955814,6971115,7448336,6940056,1431011,5999286,300897,4116681,1295878,3548112,3584740,5374727,550082,8966290,6444293,8372195,3145129,2976697,1520977,1856967,8701919,8153453,6676884,3387966,9149695,161223,5477360,7856144,7967987,120747,4612546,1923801,7091862,2060883,8863858,8522873,8060169,9164756,2639555,9356047,2712869,6224295,4730775,3262951,5190586,1175068,1635147,8335715,4151765,3156125,192682,2853685,1309578,6869567,6241651,459274,7030790,1719012,8315418,4998778,1839759,2927965,6922580,8931621,4988848,5786438,7454495,3049018,4951195,94050,2405066,7664064,6318346,7135841,927016,1508932,8310910,2562163,9844648,2462676,5718288,37331,5316361,7027867,6906898,1558013,7487141,3937689,3277025,5802560,8936467,5116785,8730526,5859048,4048407,3719374,1645486,1502902,6768393,6596681,1596953,9173459,4260746,7915300,6309300,5187762,9424232,4620211,7749926,9268881,7082887,3468215,9306212,2399248,496082,6213111,3957262,7983224,150800,7234287,3785784,9087268,2351073,2516310,4946316,6399480,6235685,6591803,7902383,3004079,3188485,9499336,2177538,7449231,7414637,8486839,2636993,6838869,3107050,386920,6107750,189937,3855135,5413963,2589186,4351217,1627074,6546448,2334441,1777874,3780736,6120226,865143,6131810,8636537,5811460,2531290,4872223,2403264,433674,7876302,5591749,9933011,53840,3040981,7347648,8540679,5677975,4186517,1647730,6064895,294268,1837668,9920030,5708231,4426854,4271247,7335305,973303,6605689,9113180,4754040,2725916,9978324,885850,1362453,5789785,3417141,6234677,8193049,3850815,4110979,3784799,3783826,4164820,6825780,1131474,2705500,2503756,5317992,4353231,8568651,5612261,6190899,8488681,1320493,617754,2759929,8655799,1591057,9365619,7768980,6345098,2091535,7747305,7230949,3453989,3537090,648091,9688667,1730140,4498906,3799647,5514939,8282733,7964467,2340720,9414208,669968,4844476,4732201,5023200,3413127,344463,1214099,1901809,1664956,1831853,4661739,320756,3422911,4027358,8089736,9768010,6118894,5837041,6998959,9572884,9374132,7647050,9261551,1104272,2145957,3061198,6619211,428690,1025666,8959932,9842899,1695635,3804408,4575101,6718835,7217536,4919564,7932934,9119346,6584521,9764788,3781085,6905277,3187699,7808444,4995014,2955709,3927339,832055,9954669,3500223,206187,7601719,2761775,1310460,9747676,5822974,7929671,176367,6848640,6889604,19267,8544276,694012,4594368,5263111,7911549,9513933,3196046,7030896,6098454,2960835,811981,3003732,6148534,8620426,7998746,9104244,2547766,8830801,9058913,6047989,9036989,6660633,8809765,347449,6408310,4632739,8277121,6584678,1481379,5166725,6603945,25656,5860738,1198314,5288767,3772288,712247,8484814,803184,6810702,1445649,1615166,9814434,7594184,235593,7813180,6698428,2783359,6643982,5757342,8831349,5680972,2417976,7641114,6028422,8826286,2273853,4305543,5410964,3755233,9472269,2014910,3780889,5333008,3213225,9069657,9105297,3925473,7554472,9908482,736175,9000121,1523648,550609,6594306,1759242,8363790,3292735,4542601,5007772,9050077,3373950,688745,1468054,1015065,6717167,294340,3288918,1022711,5705305,7044151,494981,7720215,825041,5827990,933441,9894698,4933287,4858914,7449170,4841769,5595089,6449292,6365418,6145699,3043598,8124660,4509489,6336333,2667262,9517262,5386411,6041212,206007,6854465,7056278,6923175,7148806,345196,7945886,2854111,7389348,8440867,574327,8214389,4268858,1507768,8109087,9202145,6366682,5558258,4043915,1961772,2007550,409333,8107472,5051149,8533994,2616962,1387483,1201256,2134225,6773895,7242469,2340232,3628361,4298747,9263408,777167,4643944,7209294,3631279,2033292,5650162,4205606,247681,9919020,5713375,8356769,9121166,2080058,3915027,3165081,4041831,5922578,3574415,2149303,973727,2108410,4766265,2361211,3309667,6900490,9135106,552136,9240723,2763467,4850884,8504131,3540635,9494828,5713426,7171914,1528121,1363589,1377521,1775802,1282610,7090896,132572,403776,9170955,4047599,3568858,3212786,9970178,7143274,5362090,943905,9251684,128355,3305117,2561351,7028846,2440223,3113488,6269569,5203690,7964372,4773701,8744326,7459201,487128,5916240,8987322,1850718,7293761,763125,3133328,4384658,895697,3537105,3555614,4943297,7105964,6768400,4913475,4249238,2130491,5857381,3500923,2258846,9162498,6062274,9287693,1602721,9175763,5557263,6806412,7140136,330964,5550738,4599337,818093,1466979,3586660,2668811,8760741,4349786,5802140,3145400,5245483,9339245,6701014,188780,6445209,3469415,5102256,694447,5599906,959637,4195371,7858753,122136,257645,7146446,1724858,9433409,2703709,8531270,6573545,3034674,4082009,1172883,3852768,5548989,4759543,6521580,4309730,9109330,2323720,7455130,4354813,1662965,4156145,4543594,8108175,7625560,9645851,8802623,3225467,605489,2997994,1084220,727625,3255639,8230667,2452483,2689048,934377,983754,9262594,3969051,5065764,435477,7821820,614753,5195021,4343400,4924483,4304351,6667120,2379614,8659165,8330086,6535759,3202760,6438261,4161320,2848611,5240884,7386787,3454101,8238878,8471008,4181726,1494518,6701675,6634209,4183567,7636053,7617964,3446161,1605105,2683728,3881638,9426925,3298482,9076660,3770325,8222966,3381012,437446,602580,2040177,8767532,7138340,5242938,5205793,1299661,8091550,446678,8686448,1545651,8685556,7157457,5727377,180074,3859133,2361587,4363641,1495186,9979552,7809803,3100291,2663280,1691442,2527216,5961762,768102,6297542,4184729,4149114,6734988,4787309,6189292,5502521,1925650,1432231,708315,3225311,9523781,1154993,1911760,1069432,9840549,9069218,6796810,20624,2928351,9158397,4384266,4423537,9137949,2194069,7523829,1801230,3885512,51045,7762993,4653614,6348588,1947722,8802729,3083577,6735032,4992022,8586099,8660683,6424253,9294414,1885994,5948034,449407,3797755,7017467,289957,2866973,3814277,310582,5795324,2972674,4694848,218862,2110624,6888918,7742691,3911855,774430,7793737,1674848,5428045,4142326,3622570,4230775,7225903,357603,9222798,5812002,9018286,5647051,5106417,904281,1595086,5555825,4702036,8612554,5845782,7569010,2426831,6156364,3364335,5399506,851213,3583197,7510130,7740131,1325889,1421985,8514562,9119627,3096834,3942607,3261953,6719405,8173383,487857,7077008,7396181,6299860,6095295,3043233,1406277,6999576,4638320,6962102,1701613,3250874,2807884,9270623,5677705,8964249,2634958,1077211,9815463,6218156,8587342,7555594,7544045,9328,6070157,6663673,3106163,12765,9925626,9825568,8186148,413483,6902577,5582330,6713343,2997872,8625563,8119620,9997448,3263884,5081723,1699061,6514758,7889608,969685,2192463,6853857,3604644,3269675,6669321,9822800,1857018,4224916,7366846,1866347,295073,4030519,4972510,307838,3956146,4798078,8493987,4369630,1700655,4076317,1082973,4698528,2701881,9202594,4695976,5965766,4284318,6395038,2480524,2173926,7364724,4672988,9027784,969368,7942663,5697105,792169,9799682,9922021,8159015,1666029,217094,2189535,6638540,524933,6145682,1436618,9018920,515312,3137274,3095238,1598285,7835802,5797120,800880,2531779,1762886,5085198,8926818,4243411,7259124,6291543,8916399,6286909,7260911,6859063,1984014,8053081,6658745,1906035,6212097,8324775,2123130,8401632,4963315,2648064,4547315,6399934,1666985,5062627,9537209,4762223,6660913,7373012,559344,7461793,9904791,2322231,2546992,8831610,6565642,9806117,5123153,5482041,6093026,2384065,2341105,8077040,437146,8999850,9983076,6649244,7324626,2106207,5050876,2287941,4754271,9598191,8687876,6421256,4660819,8225085,1183480,1321732,5598097,1742825,8783525,5502889,4065056,1330518,4334500,630699,1136635,9457653,6112740,7229661,1841719,8453846,5306702,2278866,7453697,5289779,8928110,4778323,7395986,3978987,7066265,2150258,3577179,5754141,8571515,8237998,3979226,9754995,9559730,9577323,1497820,8343256,5080213,5562877,9673774,9414713,6193576,810410,8872367,2306317,8040071,714086,760163,3346774,2992953,8213860,8636554,1921064,2992183,6032541,5900051,58448,8182799,9477231,5812590,6754314,7715230,9791816,6509310,7274960,9369140,8007131,5618217,4449354,3570008,5291992,3864067,9763584,6102402,2736434,2069902,4142474,3450521,2830065,7489248,6443475,1043926,6125802,8364539,4036110,2158343,4264591,4094559,341143,3741822,9907149,7095457,1457053,9698966,3604768,8732013,9068107,1611899,4350231,3517461,5181907,9642223,7381528,4945492,5744625,117963,7015394,9887099,3568485,9845460,7376348,11960,889386,3502150,8376500,4925496,5660494,2641091,9020056,6001637,6382914,8927205,3097095,7839967,8626171,6701863,6571981,7694278,8313763,922212,1211740,3495671,564436,8593269,8441163,6309061,8711232,5456558,6196161,2279717,5302019,3572509,2291678,6191406,7074660,668178,1116902,2735155,3309270,136958,8736792,9692184,9064164,1833888,7532152,7690336,8535752,4104133,5384615,6849515,5026346,6596355,345187,5590782,5189624,8786350,1899844,3900857,4242909,8096005,6180574,9544928,1668515,8472253,5736334,8743176,9140431,6853237,1478331,2449702,6990196,215124,2141886,6054361,2049012,9674039,3744697,584765,3778173,9129312,7434281,8804519,5725667,7779468,4395302,915292,6565818,6295146,4816149,808728,4391152,996724,353657,6059668,9468977,6089992,4802844,8609409,2943229,6281176,1059111,9933426,6496300,3200998,5987787,8545313,2875037,9732485,9130078,6653210,8861797,6564359,5457730,4587465,4343827,9853032,5502757,909646,6148179,318906,1718374,539332,1315630,2072032,6599000,784607,8162024,1401845,9394017,1105253,7683021,453128,1038680,4179322,3654126,7026468,2724635,6529164,6758953,1854713,3182374,5620751,8419073,8640105,208216,2762900,8493137,5710973,3672547,4641317,6029880,5390922,5180649,7345510,7462954,1779650,8130118,5624978,3181496,7524135,6730232,864517,7977264,7768913,5043840,1631391,4795381,7768475,8160555,1554335,9623189,1342930,7175086,8042262,9983035,7383303,805163,8476173,3094277,4477711,3117490,9124157,9868633,8298140,6469667,7331588,77791,4599786,2956566,3259287,2123922,9686799,4123805,101187,7455712,9167645,1732578,2251094,6936120,9893134,3805430,6559310,1236064,980517,4601572,1219100,8363820,5406736,9695273,1458097,9884447,2812764,582254,9753080,1110905,7051922,7084668,1188696,1651709,41235,4447984,3775631,9728035,8571789,3876819,7183748,7739435,5609397,9434843,4675555,5502531,3240273,1234865,6738596,4220790,5836438,7957696,2584611,1243174,7652969,4042709,1127621,465734,4624963,880702,1576639,1676886,7965371,2765336,3328596,8006607,7213320,7104228,7734642,5785110,981047,4918391,3524545,6590444,4353234,8200101,2092976,7593508,9434967,8831572,1814299,5271405,6789268,4398910,6514580,4442238,8441619,7642202,4907972,3066583,8522905,6484612,4743470,6488276,9249949,8072066,4494884,6463270,5176294,2229527,2248380,6157342,7147918,5772926,2747786,1501152,3973027,4840762,9094660,3407995,3672335,908959,8679401,461603,5307870,5193981,4903842,3749490,2836184,9811815,6816073,1359089,6296427,1559544,7847366,5546377,9631611,2342250,2009647,4807905,4571777,4258028,965247,1719695,30954,3713034,3220848,4003982,8553797,2315509,7411977,2226132,3224469,6091378,2687736,8532339,1285360,7591578,2281830,4121544,7403393,9097903,5480634,3699821,657448,3328000,9246198,289059,5670251,1255846,5096965,242029,5513874,6062213,1961725,5544828,9775247,5182573,9548810,8329045,7498083,6960788,555178,722552,3052166,3242914,9254892,4337527,834493,1536722,8459072,8237886,634626,3939706,1937708,1292074,7267707,1183907,1581133,2937958,2439753,6678099,3179987,7953628,2740312,5141712,3498456,2515560,324286,3047267,844605,7822369,8056,1399783,8544922,3060223,4642698,7799814,7397750,5477191,9336536,5856822,3715078,9971163,9796529,5652786,1263237,7064236,6836694,2844371,2195,9276447,9522470,3182183,7230075,2262783,8323896,728532,4778343,8648182,3775800,5622949,6470552,3783856,7022733,5015474,6844079,1665432,2815288,4241830,7142623,2151825,98653,857702,2122988,9895182,6510488,3386226,6959419,3347182,6230598,6961614,2623630,5753069,143797,9853706,8015852,8467693,582238,2794196,7115876,4358039,8417146,3586428,8141896,5439879,8601902,4985976,7105312,1417191,9227806,4247935,3569017,9326459,5105637,5692006,9221642,1616126,9078232,6181061,4963309,5308830,3142675,7586940,1061899,3286473,7440646,9077752,1754167,8022885,1871948,8870043,2380924,289094,2456471,522820,5728974,1058374,5508796,2834286,2475566,4736603,7082222,6044583,4063063,2187860,1736589,3284705,3803987,814822,9465766,8767296,6123652,2608442,6354237,7185552,5894916,3794883,6263304,7649083,1817768,8135253,6519126,4198693,8424348,8975598,4721513,4153323,33972,230310,6987610,2509538,4966913,4069832,8554122,9029976,6257693,290711,2314682,61680,1105533,1780448,8828977,7229186,4388891,5183214,4414739,283807,8978097,678044,7932890,795866,8813297,4452017,4994559,7237646,3427615,9716073,1390969,3461588,9946383,8378579,5971126,4913297,2448412,4525249,3943274,8706105,4815961,6257956,8767786,5921495,8038405,7596763,3150681,2427296,2779978,7565420,2711104,1758075,8243464,643994,2553942,7056762,5096012,7548502,4294408,8523627,7264575,5685378,1985215,7210959,4063957,7956342,2124257,6512370,2481591,6067531,5218476,7297552,2325487,3986262,3219047,363893,1583025,6369729,2791189,4363003,3935150,5502293,6121079,2178615,6146288,8675022,9235378,1242301,6223524,3529786,9765928,3488100,9215164,1751144,699059,3279122,9707486,2823316,9791493,2189078,8890848,5009969,9486631,1216336,8996231,2705678,1580229,579257,9075408,4371419,4942261,3010558,9873712,1063340,5189174,6020001,9738363,4424552,7262303,5961887,7954339,7028231,9449987,7169504,8779375,149047,448626,8486862,2972364,240120,675941,1863212,5250089,162572,3079549,4246320,2868251,4659778,4825578,1943659,9031197,9767839,4954218,8904910,831180,143392,4924912,569543,4567944,2187215,6531430,2522283,9215447,5981418,9691788,7994823,6130466,140414,6481685,9102830,380535,7157626,966043,5630624,7320199,4045592,9876945,188450,8705371,4702523,2132109,7736568,4470362,7086327,6641479,5301542,7229720,1566391,5871086,1797665,3753607,2402517,4319949,2969054,8383935,4011737,963877,4514401,4152152,7445563,3617232,4532687,4603190,4583275,163311,1923389,8628868,40256,2111839,7334239,4742780,4243949,5070808,9213142,1330277,1712287,4514685,8559997,3278679,385771,357662,7032286,2788289,4677611,1341,1172224,8689349,965218,5686626,2841501,8410782,9303859,7374188,3013972,3887135,7537499,4937362,2516003,7577756,7049201,9850242,2320536,1293151,4921050,1533679,2623428,6633338,6048364,1183425,9912017,6434136,1541088,6944304,9222425,6218700,6945645,394650,4908049,7910864,6081277,7749550,6321646,5385137,5123739,9335618,9272272,2661239,4272980,1788275,238995,1322182,1638518,2559532,2615333,6559569,4093211,5238761,3192907,141576,6422187,3104925,6575713,7963276,49229,5798139,4181976,6994875,6192790,9090026,4905739,2274067,6839577,1227385,7659204,1963316,563004,6931476,4624555,4835985,8719752,4863551,6158168,358270,7423083,8773501,6917840,1516295,4012263,110748,1657872,434451,3215673,8233586,8397727,3264903,4031725,2579704,259778,224515,1669730,5165518,2498583,8509308,6392903,157788,472624,6955908,7089265,5097179,1791893,5809017,9960731,7950061,6167288,7383815,6723563,3085128,8900110,735827,3195876,557983,1170278,6411550,8791569,9568006,9676454,2823295,2147710,9936232,3047811,3817441,5101751,5546394,2326750,1494654,5704182,2799374,8450563,2793447,7896554,242456,8602465,7857285,8192518,4769754,5241100,4916082,7854882,4141211,5651909,1050759,4699194,6822188,7462310,3490764,6390194,7138764,6314059,8537905,7074997,9361871,2355347,2176748,4908265,4682097,3671403,612448,7481472,2121966,3405896,5378026,2364423,2008361,3235312,556942,6778115,8476413,5473024,4632998,2617624,1124934,5683758,7316819,7947122,3146069,807584,4337317,284833,7121644,2875223,7359831,6483515,5230570,9536579,1391780,9912668,3207983,2004229,7394140,5329950,5410125,2772166,7694374,7418487,6007479,8251316,4196603,4483892,3724341,8829602,7101516,4849276,4513360,4418336,2796399,7659429,5225920,7133716,7944263,2347564,8939,5304094,8831079,5239510,4840674,222860,5152178,8048657,2227089,2546318,3378608,7637215,5318485,1072982,5055702,1325964,9324299,9252306,5809856,3048641,8081908,2911373,7897917,2595269,7329709,694316,254699,2555629,7828033,8198963,4903194,7836972,3503057,3734274,3076482,8343732,3957135,8228661,6392389,6184225,774979,9770998,3821440,6093465,843980,8877143,7419429,168279,8129450,3229285,3216920,6211358,6140659,1114838,8806628,3470368,1809154,9061328,6025998,9637188,7260291,929193,7474160,763348,4663467,550643,9107081,8620603,8779305,5499471,4804828,9554284,5270469,8626269,5647750,6114449,7503413,3067179,6282729,5632863,6296465,9499649,1844222,2437124,614488,650851,5907493,2423642,9712179,1933491,2060830,6972470,2862684,9534991,7735819,7526152,85635,6842900,6146755,8864940,2342371,951583,8419225,7612840,9577853,4066975,3727290,7081266,7134155,10019,2714130,3430620,9509669,4558353,5867745,124157,5209204,1775238,2547800,4921384,3708729,4608631,1893854,6571413,4143622,9629674,4097566,4229258,6472575,244321,3094198,8814946,1195905,1513424,6427787,773758,5580399,155078,7855025,2714554,165097,569156,6145175,9674766,5127510,2012920,9798924,336714,3788158,2346724,5258099,7496887,6955355,7151953,4068301,1098978,6781628,8165868,5328237,3254203,8410189,8422435,2069150,9606095,9935860,8496938,379854,5516260,8652016,8234880,8230814,8817113,8804036,4375990,8491880,3931546,6388910,8290804,4268261,177069,637529,9526360,7673957,7592885,6678314,1742259,8691863,3459942,9908127,4020100,6714146,8318316,2442536,8783296,7924412,2378397,7280234,8304266,7894657,5932250,6539146,6125471,4749364,5343182,501462,3241244,9274729,6890372,1532049,3542991,7067442,2169578,3069351,4741399,9762463,9747666,6483658,8454327,3207609,6391785,2474428,9921755,4710102,4916965,8705052,2634514,7295362,5985286,938780,5190019,1917537,7477927,1315491,6666901,2821109,1816953,9908146,2095839,8707326,1440195,5638830,5774768,3609774,8708182,516167,3372238,8455849,6999826,1826565,1663458,3391612,4300994,1585213,8101715,9217959,290266,736230,6513321,6275552,1675011,1703340,8193090,9152938,3018831,4859991,1974048,4835785,4768137,4069887,3543111,6208333,9708718,9317880,9818107,8416900,9834048,3190345,6872749,6833874,5016911,8536208,225487,9317905,121422,8327202,8535864,411688,9063432,5049185,6687241,738443,6752526,4880331,9891381,9771358,9740322,1865429,4607144,4508460,5935317,8150255,716793,5644035,7468136,534901,4060936,7302184,3725246,933686,4136059,8742158,9469894,4361546,8060063,9591316,2688748,6595927,3004,1752181,1645113,6690245,2490625,8397640,1570577,2382006,8168999,1310899,4247436,2776143,5819360,182754,926399,6536154,5826789,8394535,7071055,9887725,5696719,796302,821411,9832778,9538460,291306,4194324,7598524,9882622,6883073,4194451,9885627,8635254,5839565,6575873,1125879,4237206,8146450,3507886,2406205,9457350,7755323,5182348,5276711,7938077,6108747,1812865,3764867,4503282,8883921,3652593,200002,9680223,4474005,32780,9218684,4765311,4227105,6817208,4647934,1110178,1011660,4533561,9745433,6851226,1109435,871313,1088432,9255886,4379199,3494637,8713237,2134523,8676986,3989948,72601,4785734,5802813,3837468,9289016,4686734,7490061,9489018,4366958,1964066,9521799,3585642,6729378,3748904,402851,1377312,4859083,1414512,5910873,4604517,8265738,7020309,5475830,9354171,6276195,9855030,2848809,4989432,1989553,1525795,8979380,2062155,6311529,4782194,5899623,5600546,9468929,3389685,5089565,3835887,5353751,4611365,7421530,2083129,8360269,7824382,3460441,3219353,9238894,9371315,7823870,7504632,6391625,3299701,6858803,2667820,3154731,9707612,7657253,5144285,1233408,6636634,7206440,7544938,1418828,3106063,3145484,887757,6495749,8235050,4723645,1849500,2846415,2145176,3932630,1206685,9969558,7393072,4426038,9208452,6764388,2249909,6713084,3156013,5549610,3571888,5823833,8704342,3279501,3481087,3848627,4512910,117721,1055068,2057848,1536549,4161132,5203332,2424307,656881,3438383,7147953,2506381,6284798,9293129,6439012,7491483,9262687,3832084,1917522,8471139,596472,4167431,5184224,3752485,9717042,8756113,9576319,8421384,2035614,3057407,2270011,6548524,3175128,3325079,8606373,4711678,7486211,3809706,7135986,8143092,7248089,4283939,649474,3532887,3577068,7088486,1024371,2839756,920571,2941893,1310895,1517044,7109324,6495120,5269530,6826366,5251233,4845849,5247750,7286848,7903257,7517762,3835373,1078385,842842,2441746,5790063,8329054,6251453,2926050,6472146,3499542,7209989,7121621,7032430,787058,4210108,8056801,3626815,5130679,998694,4937711,6647723,8108019,1432831,1917253,4934386,6684065,6763103,182137,3970913,4666360,7699900,7806287,5744746,8542742,248034,1534810,6871796,6499487,4460860,3343943,9999029,1670850,465565,7031460,2457909,4675673,5088261,6084724,9806353,6086956,1022435,6454077,4194976,2455267,8371331,9129363,9139332,5134434,9311500,3110246,9800795,7011400,916533,5545541,5554143,1164567,7080352,2425940,7664054,1541212,5769884,7663084,3212063,6235449,4694544,5669972,911123,9782805,1754697,717477,5869762,2777132,7171554,64739,5232400,5542885,9194102,4371732,677320,8505602,7481978,478115,5517003,8398511,6023657,1071147,9563078,3104010,3497087,7227133,4645222,9266972,4890217,7857286,5502422,9584761,3527258,6413546,9367567,5281956,7131023,5237330,8059089,4302577,5302069,3291489,9845463,4496171,7663221,522783,3001774,5145200,1000899,8518777,3543712,7024557,9589925,3106791,128567,3087013,333924,4773790,2353985,5224141,2631076,7856408,4808903,6158335,4269954,4176471,1440291,1400977,9413801,9499380,5703555,4715870,2790869,5549018,9212042,454091,6071802,2213816,5599291,7072701,732594,9143003,4097259,322519,2249794,4225826,3409532,2583718,8999617,5763518,7807860,1630693,3619926,2616764,7789028,7889880,6793235,9229320,9290857,6207037,8728700,4994413,922907,1519569,543431,134950,1973661,6615233,2348766,7572952,3687935,3081360,6715956,7785194,3403880,8965750,2011021,6813412,1549469,1010638,2576931,9357330,2641332,6196857,1974094,430361,4086738,8767330,9659681,3377596,4974367,8388381,8372009,5897275,9907951,8915440,6032225,1881612,5530674,8380992,9454565,9218609,1462352,6170521,7003804,4866232,5136271,9014826,1679645,6685741,25465,4256576,6043071,2666797,453433,8017166,3097159,4540172,6784497,2756840,7917768,1758864,1145222,6289777,7656140,1053173,5205217,3688365,2934786,735892,2069358,2389351,9954502,3531710,8559872,6958306,8397943,3696144,5973133,77588,381886,5998598,4334165,6424958,8665396,4787599,4442124,1762555,9327771,1226622,4519396,7245539,2985486,5664618,3535316,641627,6717791,8740534,4329993,9652578,9476426,6399351,2041929,9430928,9931061,601801,6389235,8329005,4297946,2362369,8406593,4679832,8360967,2740758,1104790,7026364,7528357,5546915,8788919,6856129,6773537,3308316,4101668,9759024,8972934,7636984,400651,5690726,6377518,4730644,5343304,5853945,1129995,7385233,5284873,1061057,7987035,1674109,9390063,2284981,4036478,7796656,6964813,2397446,537415,8069604,9423810,8065773,3616519,8212730,4921902,390056,1521046,9023570,149080,493980,6660555,549732,6184706,3038074,5280376,1528011,8892019,6410372,8913244,4176893,7471430,6900279,5851002,6861493,9185261,9887481,4658150,6150075,2284927,5195566,4219679,1708737,3261340,7836198,9921468,8183242,8226255,1442514,7206813,8375335,1936495,3867369,8925067,8121202,6905443,4205444,9649213,5797462,615817,8562458,9974355,8087247,5462738,5825357,4948741,4647999,5712839,9606891,798075,7997766,4802458,5017754,9706504,8063798,2853953,9627972,6247041,1080208,1070487,3453854,9455544,3006983,7321224,8380612,1128186,4226667,2586057,777400,24129,3201874,9339858,9998484,1289122,4802597,5823842,6237864,9450597,1536681,5844755,248672,9534448,647214,5266427,9240953,8711012,8120380,8868926,4958053,9200589,9939413,8411908,8656134,2946397,5733132,7036746,4074583,9959799,9622803,4851983,9983929,2824678,4191842,9982414,4113801,8994439,5806256,351665,8445036,7342938,6196421,8693709,6877387,6843635,3960136,6118340,5554647,2080517,4987266,512701,1281106,4926680,8924610,9937240,7873077,4657742,6973987,1947661,4617542,6596791,6799645,4601471,9421470,991487,4583885,3535271,9985927,390142,3886936,8430964,7733081,83357,7124673,4610468,6926992,1084810,728809,2481640,3165327,5716075,2994342,4446434,642756,1918952,4383675,8515833,6576694,1357662,463495,1194236,7954454,7263140,5795708,7375924,8254628,379593,911196,8240555,769736,4798132,6671519,8502817,4881489,3796193,3113285,1808482,4881003,3842094,4290123,8046331,9558170,7284465,2492765,200926,9203417,6876440,8716760,5780112,8234103,9180255,6974349,6188558,6443396,2770057,3564483,4698024,3149651,4475679,2938579,3919387,9273811,9610099,2422204,4155301,3406292,5535490,5963784,8287296,9377585,253908,6333627,8935756,7538373,8826393,9136682,6741791,5702834,7853443,2521904,3936938,7033698,9496253,125496,3477094,2266311,3689980,8175119,5415962,8165659,1113698,9335350,7439471,723798,1757554,1594773,4130090,7293045,7558557,2417387,6670631,7812466,8751014,5606387,5350839,7577407,4743069,2092631,3280242,2596512,4614535,7217180,9630211,4110789,7342677,3107306,6377100,1032657,1282425,1793063,9198316,2396124,1128413,6637788,3119922,2885968,8232561,7250013,179013,5791119,9667400,6849644,3603585,8418415,2456032,8954425,5995823,7199101,1047056,9276065,9795614,5661592,6493245,9425826,9772381,3835922,2533133,6149481,4868579,3815558,7942544,4066896,6211683,9070957,704684,9331605,1956926,8937246,6581619,2135939,4728365,6249020,8985584,8331950,4667435,1441616,7286376,663258,8640718,8333432,9939324,8436333,3995025,6432570,7862160,3767406,268493,395293,9916887,5137073,4210852,7859432,9203969,422536,6930390,9908654,9754142,8887316,8845900,6335761,1023256,3574266,2584781,8841,1906217,7252216,1450458,9192593,7915475,91176,7526026,7854800,8527510,1521051,4287370,6389671,5288457,4555864,6784964,5205345,9692937,995817,3064777,8896907,1418353,9995168,8805561,1172495,8882484,7651462,7508257,9905740,1225728,93038,9914581,3131945,7345255,1365039,2324539,5260731,1456216,9850565,3115531,9983727,1371616,7402902,6373398,6660074,1958766,3158363,1865420,1651703,4154181,4930197,548611,5572534,4925366,9354173,6745030,3807850,7005635,4253287,3713591,8231364,4346326,3628173,1363310,1691581,4993213,3687849,6952312,6449429,3538414,67844,6433157,4910031,7470746,2806556,1570106,9429513,5964919,3435526,1081217,119101,8365724,1629828,5691635,3291090,984001,2436666,7098940,7989637,6689954,812531,6221002,1036280,4440705,7584312,2727861,9433918,1272161,9680174,5883347,4810576,9748019,2316505,9720607,7218766,5123061,1290713,6648279,1087981,4726240,7729497,1207082,3091964,9359325,6898718,6383054,343327,9335384,3481994,8332965,6025338,4294526,4553967,7061619,8735231,2138279,9789480,8169149,3410440,9469655,4052497,8221017,9217674,6369003,7941625,6436441,1492064,9232339,3084720,2580045,3958579,814217,3787128,7050543,173543,685846,3433597,516871,21231,6915592,8849836,6046570,1210119,3403803,3108189,9945350,5542082,2897670,8114500,8952523,2367326,2166998,7173540,1585001,8536001,5115166,8021442,28066,4347505,1106162,2608112,8306084,1920380,6395240,5356627,2093924,7081087,8790225,2610795,7102319,5705817,1460631,3148889,6915936,4864434,6257079,6861287,406517,9154750,4975788,9359041,1522076,7142787,6532581,3107078,5678788,1647748,1128520,5706854,5995253,2234683,8314967,4301337,4155063,4710207,9657965,6248987,1791295,8448190,8859783,8893614,4154008,320414,2042504,1069945,5184849,8299583,7931233,5591366,7454334,2907021,4950407,8976411,49809,1482989,2083489,5728597,3130737,3212009,1435452,9125990,5446692,9750419,3427328,9601756,4460627,3085294,5850743,6251922,1533484,4710526,5145536,5687493,5030941,7188040,6757438,215790,5487624,4688671,5807157,2941959,7595693,757565,1918370,7645502,2240554,4001859,3374100,5371292,7213868,4809553,4497283,2660561,4559973,7924612,2262317,9020601,1009906,8113061,5272523,2543390,2823588,418060,8230884,7854529,7606101,4988322,8070320,3093725,9676994,3877477,6035684,7272687,4635043,7954055,4918190,6875597,1955914,8292291,2246890,9169783,3101844,6744173,1830344,7661818,4668785,4092662,6682419,5678691,2205723,1954943,8222082,5029312,2373003,6452966,2883842,9979104,1441289,954162,3072830,1118283,4831640,9108515,8390971,9466683,7062570,3309162,6342281,9018485,1601453,8589171,8188269,4703298,5333345,18614,2365116,2131,4111276,9047536,5680823,6317000,1002479,3902906,1346312,3375482,355873,4230154,3354587,1797162,5184317,6427417,2915446,15957,5535933,1306418,9482641,2598503,4615580,5824922,1616989,6217033,4414094,9805258,920332,9747439,9823872,3285448,9749571,3935149,2332985,5430394,252149,3335464,9333300,1598462,6710946,9689173,5828616,65533,1486336,1012934,6492951,4401782,1028892,2028884,5708200,511533,4627388,323781,6336456,6244378,6540815,750551,6049636,7461147,497991,5873509,746596,247562,9808658,3079581,5677956,60808,6415045,5011257,1659270,3125991,4700430,7487887,3191525,6186767,8500821,9684477,588549,9529713,1713362,6296750,41246,6340750,6620531,6377703,2585129,3161346,7128254,8634765,622494,7626245,4508275,1369090,7873807,4316934,4448671,3551764,4377742,863716,8563021,6037012,3989708,3263452,3524899,7181234,9450219,2025721,6865711,38769,1555434,8579073,6335519,1596681,4919824,2956051,7974384,7504953,6117398,5102638,6139719,6739892,2728884,647995,8108983,602692,4964929,2557654,4154456,9342671,3421370,2717477,5379684,7411079,5980930,8904584,4592313,5431149,930305,1458025,5469918,2485739,37099,1805438,4082420,4956923,4761490,2056805,2461877,878888,7159444,8601597,7618781,9888328,9249592,5727764,491020,4214521,8285419,4645476,3557193,1706789,7362954,8936877,9117869,3343884,7841461,3710183,8775034,8771766,5168208,4244953,1257506,5205307,6050391,5339926,162231,811881,7396732,2624108,1690770,4556176,1225706,9309552,4444505,475298,5037317,4935525,4689820,3322736,9581002,8247013,5029526,6943957,7183891,4147395,287842,5025352,7857578,9062877,3797119,3025786,3307830,5054625,8231094,9358221,394552,8393325,170103,7791284,1017434,1860874,2347461,2243140,1170427,6791966,2718439,6207744,1727492,7408259,9530480,1308494,5655273,4560006,8252452,2839164,8707402,8540295,7864517,6564980,7603172,1661636,9590767,911002,6716261,7821862,269224,7110814,6215188,439327,4902098,7232622,2300202,7249559,9475763,3470629,4041525,2194203,9678373,5769017,9602463,9208854,7077512,5257736,3768861,5329965,8096900,2476263,3870260,5961417,9041243,1473432,7623054,8632011,2384434,4339315,6453873,2653658,1450129,2669061,3092986,6352228,9901684,5393189,3601788,9377448,8863818,7643314,1571651,8542192,3412332,1174115,7751046,489845,6431851,1519907,5819810,4528752,3996171,9690070,490170,3037415,1163503,8113224,1669426,3547938,2452540,8123300,6201597,3902670,792362,9294584,254898,694046,4687773,3856686,71495,3551591,1500001,1643147,2093784,4912333,2817262,9844831,5402178,9249113,1364739,1221988,3777866,5360910,912059,4268036,8398325,2075563,2381260,67752,5623501,4833801,8191052,1825098,8736471,8983414,1119682,8991370,9677461,5807455,2848057,9748957,9359047,4348058,1392104,1452832,9260391,4209366,1297663,4662569,3458480,2662402,5884558,7236346,8023312,6796617,1504382,6421638,8872180,3885643,6489390,4495682,8719444,4680443,6320781,7455915,3663858,7440464,6447285,3341319,3247920,9295342,3090276,2606967,3643401,4482381,4059799,2903792,8691747,5357462,7566362,2150227,8019865,3450920,9386573,6043178,247538,890956,2464816,9119719,4776599,8954207,3615401,3496044,3634650,9936183,951959,7298508,7376647,7399245,639828,624567,6694588,3730105,3231534,337989,8212486,7291334,3241782,6904234,2648797,808144,9054461,668662,4259065,8441035,6711841,4506603,9331992,9176657,3626322,4108592,8130865,7241724,7604636,1765515,7177907,8556596,9064024,4554554,5955841,9703853,5179121,2650430,3433958,8410656,2988420,1646445,5701991,6230203,8550679,8350788,7038347,7605141,9019451,1297412,6046177,5731292,5804016,5378169,4907950,9430339,9486761,3038815,6672063,7091398,4804331,3849971,5647994,3868355,8404526,1603836,3572209,3583647,4254266,7006168,1994304,7242687,8652613,7696295,3472890,7203293,6047084,511238,4808434,5066536,1808651,854612,797829,7612667,6232781,5705780,7043006,5719543,8744595,3715070,2810941,3548927,7565041,8458935,7417283,5969567,62772,989492,9553215,4317038,7995660,1547520,1559726,6648273,9243816,5032616,3851566,5290900,5543855,8660001,357437,7352506,9514613,1155266,4965173,5747395,6861046,2008180,1466938,5605642,5723251,4277880,9154569,3288292,2736815,6571852,9257860,2799587,7561345,8811076,7116626,5557005,358596,8676353,2205279,9602412,3708970,6056845,4893313,9252825,4716847,5250751,6605331,4231461,6406017,1570505,9978856,3267064,3578686,1445794,8872707,9301937,5723675,8027277,2590230,8460490,4599130,1848090,1260078,2160475,659167,8376705,7717480,1017763,7053059,9922759,620176,762029,5979605,5513490,14854,696453,764241,6620186,4927914,7170258,8190692,4906770,437323,1769378,6352565,9310031,1071316,2076240,7337308,3661546,536731,1936438,5509637,1796810,4096914,6168804,173516,1814394,7186568,7226575,1737154,7806744,7988604,7716759,3320234,8003459,8413212,4084475,4623645,3341126,1254734,2814338,8247897,1692058,4583716,4600462,1002090,5655033,6676703,8339399,9316579,7213435,275837,4826216,9010245,4372752,995021,9183761,6187146,8181590,6410336,7924301,5988334,4398940,5641061,9308569,2402399,4054273,3393045,7026045,7395400,4647780,9840383,5643298,6339839,4424100,243761,7341929,79133,6920464,5681328,9395713,4133899,5957166,4221930,3144144,329918,5216952,2327906,6517065,3398542,8738242,4441367,9386876,3137183,82428,8695446,5539583,4136701,2088492,2565629,1532102,6736273,2406012,7175400,3076112,6830113,7419161,418042,6909247,4339626,6099370,6304960,8473525,2056537,526891,1617670,2386456,5743843,3945577,8903522,9142385,2683819,3344889,8529262,5821003,3427317,7224708,1360586,7564019,9313201,3926215,9096122,6049474,6332228,6271522,9125586,3162342,3690684,9543629,71589,8030310,5643000,6376550,6503836,7699537,6903442,8121507,85994,2647285,2067085,8989516,1789671,4750904,2334406,318933,571908,5761723,7543642,1932495,3325743,6856843,5858710,2421865,2906318,2190939,8693388,2031904,5353281,2384072,1575534,5424871,414383,7218534,1801422,6918220,4918071,8704864,5039728,5004066,1352150,7106813,3993582,3141821,1857718,6327988,3460754,2429626,2089712,1004396,4362121,5415455,7861240,220832,7837321,767558,2411772,6530709,2799463,7765054,8914781,4374997,3189926,9329165,1593531,4991348,6247386,6511603,3696213,1287114,1515669,5048363,8393928,5509252,8190184,251646,1837241,1650939,2681273,3926954,2655336,7043395,9342410,516577,7264228,7179731,1284135,9676000,3710440,4083599,7441055,2625222,8458597,630981,1954388,52129,5622330,8201774,6563732,9318543,9488889,8079402,4366907,7882817,3588655,2557092,8134463,5425897,4208032,815737,9352851,6863368,7859132,8695261,7379945,5123360,5874993,8664081,4799361,9585433,2747680,2240416,2210656,1206277,2871398,4165044,1258407,8493728,2366819,7822139,7812272,1855708,5901542,2179180,9738526,9490198,4736273,7872990,4916095,8944305,8688727,4268947,5807673,6547859,2964208,3187619,1671219,8839202,1851700,6470581,8424636,4599381,8710997,635292,5805659,1582395,4800337,7064066,76124,7167157,4886206,7888397,9022866,787749,67577,8761392,277947,4803850,6634382,5194043,3748156,5323109,9462990,9555830,1870969,2427199,2743449,3542188,1266401,4595150,12769,9691038,9194532,8723767,326330,5000191,306163,5126668,2064258,382288,2293826,6950465,8270685,1316692,7738215,8338263,78085,8016163,3142113,6712467,3210206,6890270,2035577,2673197,6446100,3906546,5100396,9189549,7448735,6366798,3784700,7461505,6057836,2979232,6185272,6384167,7979424,6491436,1510836,43683,6873724,3804662,6994148,5144409,5121355,4732363,3482672,5199440,2748526,6624786,1911907,5958733,3515056,3947485,8631930,9961157,7854031,3732327,9150706,5302766,99126,2935407,2764272,6156962,5914639,8949544,2541130,3894064,5440981,4051966,3937747,2314705,7856629,931896,7459114,2977984,5664260,941787,8177424,8412786,7566574,89332,4371520,1081631,4036818,3003451,1042788,1890849,6735778,193495,7193616,6834904,3128902,9957888,2991867,9043542,8907433,5532998,2937606,4348414,9584964,6875353,6663120,7441594,7807250,4122235,419578,3471510,5064022,8597003,1884297,2630597,8686335,6255817,3712229,2723154,9259268,4755017,4614003,5995047,4948513,1807620,2829952,8077416,1765509,5821820,7120958,672943,1354818,58564,5021358,939783,6933918,1684478,8381377,4741168,5806713,8800956,8212678,870736,7397959,96975,3501333,6084295,6352793,7213563,8807449,5612062,1968580,3421453,1607110,6917094,5229073,4437062,4994510,6994583,258883,2115468,7667526,1613701,2174033,2688884,2553485,9107952,4373362,934862,3849121,180076,9735818,2061800,1050812,7133778,2158776,4552146,3218073,8511569,1765709,2025522,4123631,3734290,5446976,5730741,651384,676050,167804,5645894,7670633,426687,7761362,5338159,2040389,9935396,8027044,4593874,9043348,2400406,5528736,2892469,2580482,5264555,4954270,3631295,2398333,7113046,8183441,5616407,5624615,9949151,7641930,9748247,3683441,3088906,5478989,4334825,3764956,5646794,9980719,1435589,6073481,7742082,6773749,8113871,7677479,4800793,2707745,6720828,7201200,8236482,9613298,9781683,3501038,4567568,3412979,5899371,1680614,1596420,1515778,7305230,1545572,9157709,7053477,5229013,2246615,2532467,9563839,6011572,8179261,9544559,7447162,4252743,7286641,4220911,2366614,4964121,9021705,5074360,1684949,6222906,3310842,1298247,6004590,6811880,5865815,9417569,2711252,7546429,1013990,4227031,4851659,2559562,3384740,1905137,7788575,5631356,4437604,7352414,1642928,2616866,6896973,9090090,6869609,4183615,3311002,9236224,9147736,2332708,4310584,832685,8555614,7621427,2130933,4560204,4433308,7996748,3977773,7144560,5543178,4991763,1371591,394838,7551325,4756332,2299976,5339901,387688,6737581,2692315,2030617,9354447,9589289,1120708,6224057,3772904,4431711,5460281,2920641,6764419,9770866,3753327,5320033,7392293,5884260,9880238,1825601,3881008,3858012,8970162,9424187,8849775,341754,9819025,6401101,5098086,2119002,1741002,5485775,8856583,4433318,7516393,8211030,4022607,8637101,4435088,7795512,3068812,9895369,716153,9833232,9666236,4469480,5153265,7058530,353740,5033504,8884132,4234749,8891516,7854294,3658937,7741292,8196049,3477963,4142393,3294135,5596965,5883396,8779911,4453548,316715,6296304,2664579,4339323,4933406,7099667,2134835,8002219,6995037,2850989,7835451,6661274,7320469,2988717,3719804,7674210,8022221,2603936,1908960,6913737,458231,5567897,4655029,8654280,9045860,8797423,1948416,4642826,4680820,728328,9096374,4997535,7024632,1760954,9336858,1958039,8860621,1471694,9960259,5855659,4322683,7795710,2516933,1643152,784427,6236737,9317363,8806649,8840674,1226323,5720387,9298906,6794221,375416,7953187,5840082,9172840,9901603,482908,3853660,629931,9579283,8851196,7654564,1340237,8188055,9612604,200859,9659749,9572863,6056518,3982432,7368574,8573452,5625585,8153001,4810190,4942948,6959651,3650864,6169272,2680038,2949771,2963493,3055455,902958,8803576,2228295,804562,9286484,6081956,1434494,8865768,4933153,9089058,206006,3121208,8701663,406865,2780957,8274526,6463384,6763390,5643100,5036836,2388975,3796102,9847026,7331924,755754,3497891,3501197,3435792,6447662,6464691,6491247,7350621,5268267,8719543,8155183,4554752,4801500,9589677,3420520,9734653,8678736,3626526,2855861,7380399,4033392,5636819,5654926,496777,2400209,1298027,5533614,4789185,5094129,5380640,2121110,5849883,8878532,5622308,9285676,5326195,2086999,5776923,2676816,7355267,4496467,832000,1910019,9297967,421677,5330539,9032620,9100414,8957066,1888482,6480813,2990458,7525301,2135739,3487236,9925510,3433766,9020850,4714696,8527896,4401491,6835807,4377780,3280023,2458115,3663456,8606219,4545114,9440380,1283036,1900382,3936847,2115036,3810401,3234815,2536714,9140941,2267435,1637128,8098008,4155917,8117942,1088467,1681218,253682,4575703,1606729,3687449,3596553,6321426,2215345,7998044,3157233,6593126,1278068,5615348,256583,9884287,160463,9696963,1167323,2060845,3633811,3282359,5871246,6868626,5819073,5012188,9136061,7456202,3110196,3291979,5574144,4198663,4973198,5827826,8774366,6579928,9515276,2370919,2901354,1730622,368964,6058587,8323748,1647032,1673936,8580331,1531319,1834399,8277294,2698642,3895244,1911106,5981002,9766491,8779732,1800076,4778680,7915794,9256278,7888876,1207773,4830423,2087540,6180972,658250,861906,2760900,173526,3232826,5662254,1904148,3601790,1720842,227897,5248823,3394779,8808228,6780142,5229178,7085523,9478785,9124423,8996629,5459787,8890915,7776361,7259864,3669595,5692156,6516143,1558472,6899929,1346567,3646012,3080901,2004817,4507918,5841802,2178344,7740745,1504057,4082492,1342536,3224899,4310390,6591359,6619679,3118618,3371502,1848857,204141,2850287,973281,9200771,8310075,9864196,6977133,5569940,3533792,2669289,2086083,5092264,9569219,3432650,8738276,2650120,5437468,3246195,8491923,7615812,986941,9995980,1698305,2329477,3220880,6008695,8920837,9840559,9127314,2292339,1689417,9331456,5142627,2662698,8532227,3452703,2526895,5509361,9022643,6060687,8178650,1108727,1152951,7747869,4541378,9891228,397990,9978846,3137424,8889913,7594659,4124365,8885894,9292965,6453842,2106774,5301661,5374680,1947334,4428975,7667019,3636751,3760431,2809647,6299449,2292659,6262350,8826345,7802020,5284994,4887032,5980671,6393722,6039984,3728540,935100,5931213,4126531,913947,9068637,3016445,8508606,3193002,1902339,7801572,9646845,4009113,3103233,5021525,5956447,7532209,2688545,9593199,1292641,5498193,5892648,3585301,1760544,4718994,1387322,7045538,9606026,7367993,3439260,5646011,1096534,4374361,1577225,5223065,5288308,645862,8239510,3796915,3838865,141850,1598487,3485711,4150963,4701721,8507236,107411,2233930,1195782,9700610,3526572,6693976,5593259,7111873,8454520,312253,8499195,5500059,9918280,5867188,8939320,5564292,6963722,3313681,7141517,2186788,8601989,7787380,426299,2398904,1626245,568149,3997392,5111956,4719113,8699113,3619193,4826525,933044,4814976,4527136,4459616,1508952,120395,1571489,9963473,432649,70685,5463532,350930,5937873,4402852,5915223,2901596,7716534,3056740,5088385,6318523,844121,5514685,8717428,2470367,6082835,2714821,7582323,801948,1413935,1201517,5628473,2346980,6016494,155609,6806596,7525447,276005,8378086,7488920,708655,8448772,2952453,1059585,4386645,7355305,6974808,7288242,5071840,31549,2376628,1390363,875670,7891313,107792,3346038,3974148,2822614,928362,4776097,4236549,2129879,404571,6583529,8146374,560181,3390126,5671821,836186,1768213,3160742,1544842,216985,6113195,2604427,4603631,3468501,9579236,1891874,8540341,9610786,4268502,9930705,486457,2159816,38498,3832495,6133964,2861112,4760857,910061,7097662,6890737,1314632,3681191,5037111,1874813,7071318,708933,2711000,8839532,3869675,4255842,9056518,9982870,6860270,3660149,3451372,6439506,5552024,1991713,6050293,9820526,1922418,6536750,1980342,1960917,369245,8114307,4822029,5130102,9024368,1919691,2020839,339001,5600883,7057951,2213815,2672202,7766884,4924815,1511734,1636559,9180658,568252,1619430,6040928,4228402,5070802,2480435,9780426,7062515,8530728,9600952,8984934,5067479,1581295,945851,5436724,9695602,5767881,566827,8719971,7687572,2587667,9058973,3288456,9645618,1272788,5960658,7412502,6197604,7472393,9049062,5378262,8040645,668492,1419191,2269047,5739294,3899627,2049474,2801810,2430356,1650427,1786745,7497835,3231722,2732597,2934560,2927325,8500478,3501388,1647296,6188051,6089055,706269,9476507,5734674,1979058,5437166,3147177,8176662,2909559,2196240,3554925,950204,2864732,4974117,3219252,8604027,8873744,5268727,1405838,1304100,6919154,3192583,8801936,150876,5925180,1736497,3078201,4425659,5237885,4725498,613710,1326941,5431768,90218,7061616,7410826,5527384,208793,5587489,8436944,2405034,9142414,9387149,5269766,4116531,2606402,3873794,2990276,7875129,5279632,4294377,4794283,8472216,3096313,4945160,4397397,4832810,8023362,8823056,70696,2748860,9436767,1397637,8180628,9526985,8459254,5591455,5054370,8668047,1178944,3491315,1073081,321359,2878464,6342848,4437891,5484866,216643,7428168,3359995,5496276,1722545,8154278,3968492,4818859,3099438,8365890,9651670,1122800,7188946,9722366,3871661,6625714,1120004,2052290,6152700,9579258,7643746,1207071,8247306,8822690,4698386,9320388,9144050,7576850,5663237,3581942,3061716,5879880,1010110,6421712,1376156,2732656,4575990,5344649,7551515,7675429,3710539,7203185,8798230,899486,6925552,2669892,7525201,8045557,4722182,3677901,7624815,2365928,4884973,5872122,1188619,9583359,5192510,332670,7160209,855748,3914613,221926,6735628,4924723,6643638,8111785,7657379,1219629,3456435,5208895,8895059,7166975,2412081,7693290,8066462,9337633,363182,5591664,7383190,5085365,9269565,5008006,7451294,4154538,880128,8639914,3737898,6072639,8972584,898107,6928387,2887197,1120034,3664016,7811921,7763673,1775802,5469301,8983302,5232238,678196,7878362,2399214,3090277,5571652,465676,2427911,5934835,6057340,9811102,1020200,5326906,4819108,8471494,9481445,5699237,7111408,3219343,1771876,6083993,4117451,8700264,8971191,5237485,2364281,6783112,3001158,4140083,2252414,1984461,9372322,2930610,9862823,1771536,6020888,5434476,2237213,8448799,1369311,8294553,8259901,2389512,3621460,3079010,861006,3102906,8778247,7972415,6322249,550124,4056409,439701,9250388,3027600,5677187,1614669,9810713,8678346,5754753,2063127,662808,5127075,4993738,525631,6898611,1014626,5960108,9135824,9463426,7329419,7430378,7723328,9718931,1051839,802339,579938,4154745,9580586,8552354,476995,130710,2608763,916696,9381099,5636364,6593884,995769,5447078,5272230,6750522,7510206,5935038,1877597,2503944,6460670,8776209,3518571,2420778,7912034,2981998,9750198,5342413,705327,9469129,6394252,1507666,49068,548998,1088253,8601423,1025993,1218964,1210187,1942690,600063,6846551,8536574,1595832,2293630,3808805,8346355,9803836,9743844,223953,2307781,6204514,9000162,5826353,8625293,6912197,8808352,8375491,2254611,9513679,7844621,8648864,1021346,7893690,9197862,2109599,6495113,223856,3328563,7705300,2166547,3928627,4551852,703122,5524460,6845482,4511927,3870815,6649319,4255771,4094768,8957101,460286,3094931,4783454,9085579,7128,3591807,7461070,2261739,3105486,5305692,910603,4126832,3199382,108466,6236432,9694495,332322,9564996,7399795,2498869,3493623,1951647,3201991,9018083,8797130,7713919,2888898,5446449,1969691,6983667,4403550,2429977,78598,9187005,1515556,85726,2778812,8976627,2347466,5884299,4282320,3258070,11132,7481702,3366536,6247565,7176198,3698859,5812561,4575993,6197729,9306185,6527641,9399721,8324269,5324771,7113640,1213168,771221,9083332,8196835,5174772,1513309,8275433,4361778,3028866,8361160,7140590,2005494,708626,3024890,6287814,3966697,3036022,3769517,7333234,9283587,945715,1032093,5096149,5521709,7229822,4402334,2049350,6629544,2726604,7374122,3743185,3939772,8145343,2826517,2136607,3320116,4339827,412041,7681894,7368693,8773201,4822485,9374188,9481828,7847375,5662003,3448525,883398,9431520,781759,166986,377235,1813853,5263136,5898945,9043676,9665471,7948295,5673220,2392075,5322417,9416406,6331847,3467761,2242923,8468455,6787877,6582750,8880496,4469771,3951444,7653698,9292257,3325633,7135527,7139632,8987636,584053,8023031,8419156,1365813,8190018,8796392,3179666,3453154,4695337,2223343,3118625,2643633,7896564,5510700,7966051,7312970,1842548,1433812,9555894,311003,8221690,6138645,9191500,2691462,90089,6845199,1983719,3415722,3980726,9123352,2403358,4564779,7146383,822515,5930593,5336401,9618907,9110259,8789555,4314245,1333603,1908181,6957878,9230167,7418881,4923929,6543137,9261429,6357742,6099032,9572433,4579432,2237677,8763933,7270894,2327766,5609132,9254613,5743489,9589859,8377965,8146848,4154639,5524349,8969363,85232,860751,8588271,9195492,9650307,2902516,529095,1558488,9860395,9759262,8977370,4784324,6302400,8238799,1142067,2401432,7811233,5721499,4639109,6575166,2992393,6966876,2184299,2247007,2710366,1774159,624973,857214,5928798,6149323,9826578,6014030,7010074,8414849,5209522,6660381,1317366,5738617,8218870,1177761,5497880,7196240,5962086,1800281,5435040,7104153,4201714,3246273,2825653,8840824,9821440,5818047,5807700,2005740,8065055,8518067,3779899,8690028,9375281,9708697,4839352,9201859,5722728,1849426,7616709,932250,8509808,8934076,6670868,6728679,111838,2168749,3924919,6073924,3969030,9359960,3178078,8170744,2606233,6003732,7011568,2427674,1821779,2819269,4433414,9886834,1337336,8213314,8576863,712618,7922012,3416215,9914478,3644740,5265642,7531188,4576991,3775451,6465264,1247860,504130,6577102,3416609,4429049,2651027,7385640,3789009,5829105,5556385,6395243,1832838,2567953,8822917,3654617,5387223,3256332,3541452,6724560,1469646,2118316,7437179,9391658,5534532,7351657,3036399,800174,4882845,7613390,4575625,1348110,8861250,5079756,7925212,2277860,9508805,576239,9663500,3297815,6405345,5219885,9693059,8238184,7787839,8515976,1892801,3175063,1772309,5434254,9899623,3241955,7552570,7336802,2633614,3087102,4688460,5670013,3887277,9571306,3283403,8462902,919416,2144654,3542658,8844629,4422514,3051464,9420869,4086015,6349280,5826215,9305900,6042339,4064399,7093739,4558316,5957201,268803,6330626,1391455,168426,9572581,8944026,7505229,2206195,2031128,2193690,7876209,5918405,1764997,1159613,4381308,2684413,3304267,7923967,1529043,7726782,975432,949913,1812797,7324712,6776128,1118698,3367052,840527,8212438,7925369,6797729,8481241,4255995,8189184,8649667,3828577,7133210,6154897,6034773,9164339,8348588,3910982,5082744,113585,5070595,9464053,2797999,8374863,7388020,4327042,6101645,8363453,5276955,7914442,5688166,2053084,9033140,9055219,2893611,7245578,6980588,9691341,5726820,1236584,7880525,4376487,5065161,5013736,531385,1099934,4178075,8879973,5010917,9260820,8993558,81512,8724874,1791557,8456375,6112895,6118600,4558021,4476348,1395556,2472464,164514,3448640,1505604,9219733,6342252,8751183,6200322,6033593,4478004,7436906,3914118,8854492,2502068,8927855,9385877,3602003,3105931,8265851,8612920,2366751,7259410,8694433,1091625,9050968,7150808,7204520,5169568,1708830,1680869,6565124,4181294,1845383,13764,5686899,1065117,6356017,4438083,7265439,2389610,8916087,4702346,6303729,7770579,7204414,5231584,7156456,806417,8337515,5422308,9419338,704267,2681718,8113771,1795893,1732686,5264580,9000413,6902255,6973410,681283,3467379,1154704,2526666,3481144,6841603,3591783,9837161,1279686,857223,2226771,195774,5559569,8530501,7966353,2763983,3762085,5122810,3570401,2099601,545118,2989740,2803868,3226836,1103511,4599762,4959523,6368092,3600176,1861778,3341502,4281459,5329158,4496207,6808125,8810302,1337811,399909,8647464,2617498,1257133,874236,2813272,6816702,9404737,779625,9580686,3166823,5902435,3151088,5266424,6447554,6140828,8070293,9674390,7244339,2670055,4633913,3612432,6270231,6495692,6953934,551690,1824850,1450142,7359816,635152,2787953,7759726,9282617,5405452,9016859,156853,8218724,5833562,9561590,8998350,5414248,2728414,4900786,8565336,7994838,1348340,4706164,6065132,1022731,1950504,8735188,5656645,5562936,5005419,2152337,2516871,5557110,3977188,3967014,2916927,4612340,6754968,676653,3894958,2160420,9693513,4051811,379145,5527075,3613402,9377496,941324,6341816,4278282,9506660,4336655,5626623,4212825,401788,6649355,6163330,9136976,2306000,1726267,4142396,4458338,4243138,9699506,8435526,8210152,2616434,3047867,4965121,3293088,6942825,7125541,2986601,994637,7504686,8513677,4608040,6882182,9455001,949856,1160465,8961662,5286512,6787089,3174488,5688300,3436444,9337818,4825277,5742445,1064085,8967673,200783,5307224,8667180,8636310,3517377,1283614,1684178,8482498,4576702,8627004,5608040,7563304,9621641,3112726,6076981,4229681,9994909,5531983,5179538,1155375,4493645,466051,7942464,7668133,6154351,1378908,7005951,979628,7121354,8070037,9947302,7322138,3377262,8614482,5958448,6894640,9898096,7642627,5377138,4474799,6269631,985179,2038103,5891273,4097906,8115085,120954,4092815,3647068,5300493,5248191,8140714,5766544,3190655,5808847,1920896,4569564,2814799,2900525,1690918,884837,2847827,9013056,4262099,1462309,4971505,1156740,1360406,2614133,6533879,5835206,8883764,7519058,7873310,4775037,1616964,5988396,4895992,5709780,9635464,196486,957971,7776179,5963031,4148627,3585026,7883927,8718191,6399826,784453,409110,7284663,3632280,9422167,1546763,5094590,4393673,2703503,6454997,7007806,9237383,2290203,5891570,6756441,163514,666608,8373405,6151910,5562601,4083186,5787375,5759087,5041157,3563554,1722118,9189784,7148580,9606046,7907976,3548407,390499,8317086,833070,4022780,7739253,2379834,9117371,2132927,5083338,5572369,9140733,4320721,7862573,5032303,1077162,8026087,5698912,9450568,4177998,1261513,3533754,9965373,7020601,8574912,3528927,8742719,7764696,677508,8348766,5672672,4225915,8739266,3989759,5058986,2762047,1729013,7438821,1879418,3861940,2522159,7451788,3002673,6842881,5314361,8034977,7920044,3340449,3733889,7370613,7518447,4995403,904367,7483820,2016004,9479280,1012747,758724,7243976,1690256,9107490,2916649,5916171,7846756,6906408,975158,608803,8635421,8413979,2488222,2497361,936139,9940010,5500035,7779020,5254371,3535012,5699065,8594820,7268902,3069678,6113267,2264305,3974046,3597088,4280309,3453326,4609835,5039033,697303,6300092,4146524,3613952,2216263,1993281,520361,3191422,2602085,9155783,1605401,5090307,1653145,2541541,5030318,7153180,320561,284690,688193,6019627,8879511,7957095,9089305,4992779,221400,3063351,8589867,4501710,6516678,3199703,9540744,7213981,9499795,3687269,827934,1716059,5680550,1348296,4907481,8282635,504079,6512882,3372943,2157225,9054423,8403261,9310406,9374985,8687951,9998599,5394612,7567462,7955694,4483918,2560242,8177095,7547269,1150109,2678805,4063948,4349812,2219550,1277930,3849608,5906819,2105864,5565667,1587369,3454161,473148,9870005,3958241,6986031,3242948,6115466,6040455,1646210,5425872,5415440,334162,5424471,810053,7901625,3380166,5293971,461867,1557261,2841241,1611976,4236067,6905190,5961789,6455618,8183120,9811398,2362437,288985,5377065,3949807,3743146,5850214,3819812,7701387,2836245,7062761,3816854,8876700,8708971,9242726,4292141,9043133,4667198,5102195,6944758,8047365,396166,7406625,9604627,3237408,9018602,3840695,142598,4980392,296313,8325718,4791790,2658750,8614704,168855,6608558,2357850,6019069,428370,59238,8855315,7491132,3876092,7732015,6200103,3118819,2024157,5243237,7786018,7126352,2187995,5833383,7522519,9594621,5438011,759928,8613224,9278706,902526,3593616,9575019,9228245,8385406,2233770,7842949,8554262,8842328,200800,4573332,9270699,260038,3428647,6761831,4136131,1160663,2961935,7254951,3184821,8205172,5040969,311174,393168,874353,7833693,9987790,6312364,8593622,8601014,5591071,9496148,2194631,5166091,8724394,580038,7399861,6567344,9134301,6242190,6768145,3707633,5512890,7028184,7136281,2274722,1164315,8296945,5236657,8419266,1481766,3441830,3460236,1792940,3834999,4334589,9626634,3822790,646954,8220256,2423805,6238025,7716405,4618436,1404116,6440800,5198475,8803978,3008145,4332776,5046169,9776290,8040410,559059,6804474,5176691,2833781,7968790,3473637,8070439,6388056,4955403,1512269,9848292,6748344,5347269,4182882,6374979,9170059,4829836,4595236,1593864,1067862,2311642,6212301,2471979,8752442,1410776,1275957,1760587,5743552,6322126,1536878,3783962,6881185,8341352,8960654,9714967,6310142,2434291,7785406,2698199,7389695,9297676,2546492,4138039,4644945,6729374,513019,3815005,1559211,5108255,5408869,2627073,7419898,1621171,5099052,6172340,3031947,6375009,7932928,8775499,2697136,9469806,2559462,9578322,7811159,1520116,9293289,4121302,3954408,7078696,6819501,1344103,6376372,9365993,5482143,1021318,6095367,5995162,4836323,7654578,1103418,245193,281652,8523316,1866364,5380704,4695657,4898312,1755714,2628585,3673812,4452851,2098392,6233274,4031173,9909551,7753391,3324463,4030854,1707799,403159,850355,3051902,6779532,216348,8534045,7800850,6311716,4529208,2637174,3966295,5632626,2882368,4247947,4155943,4748733,9628652,8851601,9647045,1384367,1480186,3320857,5837219,3578579,9554132,9868392,3488131,7307523,3192856,7518985,9015322,3596015,8369341,2067224,375547,8585689,601270,8176398,4897406,5130478,813572,8863702,763105,3695941,3111650,4919049,8444674,2740303,3770650,8091719,4124670,5250837,1412577,9961890,8829416,966709,9830283,2317548,8274232,3023139,9836533,7289555,6619154,8205874,9356780,6994702,6791564,9958050,5171100,1688971,5088529,5984673,552673,5851635,9680614,3664323,770684,8125288,6404626,4541334,6217008,529297,9792172,7629585,491187,8621588,8596295,321470,939137,6870527,3344609,775671,4160082,9963764,8981546,3516863,6958467,5773110,3474913,2129568,7462082,8563443,8114241,8014755,4415078,7794856,1679079,5185762,5920144,8083705,9727097,2137153,8613003,9519269,9766739,9104191,8140858,8363034,9425661,9079995,5233561,2770271,9855666,9393644,2734036,8837212,2910507,9692503,4610323,6385421,1822071,2072405,4948864,9936313,87161,9363942,7731169,1766240,4549705,3651314,9849946,4276802,5788467,8462950,3796072,5555206,7567141,1936930,3918241,6992803,1016926,9151803,9763074,872593,8545448,2497111,9709806,1455956,2189614,4320130,7841377,4011686,6392536,2790242,3947999,6479697,2154184,1679169,8245938,6703889,5330483,8095885,980692,1118951,6558835,4776764,6674158,4125976,6713694,592399,1118780,7730621,9744203,881854,8603214,8289651,3378966,8313020,9745607,5568580,2633150,7586984,9580267,9025686,377226,3528267,5505384,2531411,5207436,3751322,9235301,537920,1847208,215993,1656872,8406043,4992758,8331030,2532020,1706453,8923430,3650800,9437074,8667633,4532655,8040289,6957285,7911621,6353310,6702892,3480202,8986460,4289876,3060469,8012147,4667103,6588737,3517532,7198515,1796174,7268855,6433816,2334095,9116063,6649810,3990967,7522107,1642568,2321998,54127,3349022,1245429,3704928,2786096,9913063,8237583,826385,6870348,6149205,7179695,3573240,9629407,6166156,7863117,2689877,4178304,2530221,9278615,7695837,9728736,1074789,4964692,6162553,3408884,4080756,2812363,7399851,1602863,4454932,9721850,1656990,7803955,967279,5361919,590051,880342,3599503,1416437,7750690,9748708,8596133,1323930,9378116,4762290,9187047,2067993,8940595,1717269,1346608,6636432,1446005,2421398,1601125,7608558,5830282,5681881,420922,3230134,7284744,4875855,2951984,8941735,2679811,3919264,4303655,3269863,4799606,7903158,4686300,2550296,7651866,3282434,3874227,7029982,8044725,3061275,9097976,6985321,4778544,444585,3621754,6224550,2865983,5222880,3833108,8696265,904761,4254031,1926400,8189506,9129887,4878385,7131242,1809698,8797649,1434897,5079561,3597255,9338055,9765862,6147552,6989922,3048297,21779,4019905,1093023,3083054,3117881,8078344,7861599,3562466,1700099,4086149,6428449,6922979,7919258,5124715,7827741,2173290,7051116,6017247,1303178,1929501,3148490,3112876,727150,4583388,8192438,4324405,3921444,7958301,471957,911366,1006598,493737,4931272,2099622,3576792,8049153,177967,1438391,1611620,1878066,5524541,8040070,8801046,3443799,3164785,6628787,5617090,215901,2646035,6920268,2145403,5794525,33145,2872553,377914,8225583,7196959,4299358,6183884,7668917,5210725,7190483,8162654,141997,9290105,1739447,8191150,9468072,3177838,9802770,1346139,8702380,7842840,147185,2146180,1007626,6775973,7763270,1223528,9422008,4683539,3368931,5216534,4716684,6241485,5594448,2942267,3438444,9893806,9126152,1107361,5104531,6316636,9270016,5246529,5606741,1009463,3437679,5074814,4187302,3240450,6420954,2889682,1083291,6568140,5035863,2090918,3344113,2799133,3314446,2766121,7482672,6683378,7982656,2199357,2924864,3577104,5141624,6363308,3470911,4267777,7470670,8575443,584413,6740687,3821972,6191155,7750150,7259652,1265970,1937453,500103,7686925,4827136,1583394,4255065,9862999,3674312,7599178,2662133,6988759,365300,144805,3672138,8347957,2344162,6597002,1925061,7485787,2960311,5395973,1753565,430981,3971417,2337978,7171669,7793389,8529134,4921819,5053042,9795105,6859273,5553145,7482030,1686409,7136540,1737095,1549408,810853,9336274,4211541,7799613,9701575,4356347,1471751,8049532,6700510,8068753,9974594,4186298,1029064,5370567,5939863,1460046,9341984,8277842,8631715,7135374,6806976,3553535,2188417,6602082,412808,7741562,4084112,2099218,4878103,5821207,3648626,5688956,5157482,7860168,3488569,4859057,2216515,4960321,2908589,8917025,3029075,2883184,3103324,4058140,8253751,9043187,5518187,7595736,7321029,4149902,4731111,4128006,7703438,6919528,730088,8116247,4661091,4814200,215465,9539194,635408,3864092,5228150,5792891,1724260,8716720,651948,3940776,3677042,3560538,2857802,6706117,6443723,5961126,764257,4697475,5004313,6282444,2293211,2325343,432347,7024323,6453350,8135786,3943851,7183438,6252033,8604942,1997639,6467499,8144136,2633048,331592,3372287,8425940,2055852,2089008,9077888,5996629,5766050,2638427,8854431,2472167,9082151,4815557,3236425,3779626,9819871,9518869,6072837,2145215,9951217,3097160,8598565,8087003,7041012,5782004,4339037,5645954,7779643,806536,3790091,412692,1138129,7162378,8838632,3193981,9251387,7916521,9190611,5017438,554949,8045042,7489605,9637100,2860600,726031,3416726,2680472,244901,9489564,4825687,196118,2586725,3424252,8283122,9627737,9206257,2622159,5273692,6985901,3428696,9063783,7398593,4566825,6226162,6237226,7760807,5477550,4153748,6951418,494988,4708697,4996461,7984594,4345798,7857062,8710625,7762525,537534,8955526,7252090,5363222,9151645,9838815,8787475,7434767,9466553,7993732,56927,4740245,4979633,3485623,3804029,2378227,8052449,30192,8615453,5813256,5507742,2769202,2764675,6002730,7477900,7761137,3987324,1823698,5618199,2697950,9586224,6155734,1653477,6838314,1518956,805122,6677129,306432,8239890,6143683,8300164,8296818,883928,3279798,1782442,4687958,5658025,9834891,4718150,4273479,5648148,225892,7042681,8412824,6228623,4520582,6173961,215947,6344281,1792161,2913897,5930505,7947895,4567375,2768819,9466852,5372497,9445949,9773284,3612388,5589632,8073449,1909207,6473561,1353248,3691649,1161519,7011273,3526540,5879669,1284753,9174689,6105562,8327435,7587513,2334185,2848017,3761475,2550133,9192298,5553636,5464031,5122804,3501532,31406,7891624,2968385,5403904,7337573,2741670,9016293,2927206,815120,925500,9400768,2168368,4617149,562288,9179641,8143690,6441958,464395,7318380,2547520,8791830,4905893,4881706,1639847,8667369,7431839,832146,4221006,2895871,5954950,7722538,2927277,3846574,690924,8331182,1184148,3432594,7347475,4111354,4247714,8272976,3512123,6416082,2890125,4074411,5595724,1033816,516369,6060119,8352196,3063889,4851949,3258090,7945596,6491797,1925459,5377435,7323943,6146465,8273306,3278893,3869004,1200584,7125468,4559928,9531766,8309616,7992522,6879242,2420970,2240237,5152218,5933094,8656319,8042344,7505,4252043,9076160,523874,312163,7428356,3587764,5164112,686446,1533360,1655909,2611906,6910795,8979853,8758371,5184102,2258746,2627376,6384687,9384214,7187304,5916453,7693831,5179827,2795696,114802,7420065,7947914,6047896,6076384,5990258,6055401,328428,5066419,6579275,640591,2494775,167039,5804704,3181222,1700400,7460614,5793128,8611195,6440467,4551500,3795298,8699214,7178876,179985,8083429,4366181,6096439,5777260,9546009,8892135,5892062,6966075,6840050,1939958,3042460,2830309,7995360,3370889,7896728,4574636,4011481,391504,4741675,9816185,3572726,6442075,7276799,9365855,5053271,3717267,3917355,8848570,2416482,1096232,9028555,499911,5462414,5124995,6277172,5008424,4017131,2169234,1974499,857182,4109193,5016959,3687491,2104554,8387848,1584219,6679190,2399329,1975724,1420866,2215515,5548450,7862942,9492315,4914305,2916213,3209582,8831661,1764784,5626065,9927893,793340,6125976,5390308,5918335,2403148,398732,9935467,4572383,2373232,792649,8681577,7390191,4480140,786131,5778040,6064360,7465322,8177370,8040084,8886188,392885,3588535,6749130,9885201,8502840,9665344,3094783,7334501,1430128,8720848,7262395,2223468,4846825,2652703,8141804,7249974,3051436,8077271,1822358,5424668,8869921,503936,2814859,3350062,1290068,8592900,9414422,8755390,6770270,7454507,7641578,7163156,1043043,4390709,7048357,9545884,4056053,143141,6880386,5486182,8863990,4142781,7709651,3710815,6795485,5851455,960790,9846921,3928727,2783148,5271589,2798648,3287084,8086449,6148710,4577152,6679349,5563133,3332543,3449620,3017641,974122,612776,4060684,5364831,7661133,3606569,9420885,7804274,486955,4907067,6668264,4629736,2616718,379080,1425222,8468174,1339870,1272143,2396902,4123019,6543733,5195551,7410103,4630182,1344262,1987256,1309532,6907396,5319800,4759152,9925037,6293922,5371929,3985722,1658753,3033062,7592291,1079639,837337,8079246,5986706,7505602,2708983,8603425,7884682,4134206,7071600,9224553,5406350,9468502,3347572,1950083,4664054,757676,6580266,6008316,2744933,7889798,2915712,8064733,2648951,2840750,4358655,8020880,6826473,6017409,1053943,4418764,7097048,1891280,2498011,3083755,9396882,5206995,1687181,7281564,9341201,8758781,6506118,4747551,8227284,9853690,6697635,2891339,611366,3277901,8899655,3356299,1167700,1815368,1421033,3816651,4656118,5779689,1837532,1482591,1797098,2891475,5901356,8894147,4782756,8399368,1977903,4179638,3606363,3665084,1461203,2947565,2423866,7967321,7695117,651150,7821011,4392752,3542489,8432378,7670654,2442145,1788678,8838354,4257513,3209711,2655006,8913632,8989400,4492539,396224,786499,7384014,6297581,9680647,2166771,4696949,1658550,6346409,8303313,5323634,7807613,1250878,7747501,5774934,8945996,8398652,3595946,3338749,1941142,2028325,1009403,4383287,3817003,9847758,8640801,7026715,2502765,7554434,6016116,6995304,7950658,6802616,4379319,4248239,6483263,6546090,8945189,8141813,2892500,7248502,3465448,700113,8499381,1212949,6475047,7445377,9611601,70994,784126,1552743,2099319,1793530,5936031,5916323,1641289,4576832,2943039,4144054,2131267,8959155,1139359,81925,5761771,5518678,4330165,2245035,2064769,3275355,386848,4957269,523857,3852297,5657383,9023239,5065246,2132431,6468617,4676848,2203425,7252744,6229591,4302745,9046274,2165623,219069,687563,6742456,3162108,4831618,8873723,2121263,5970977,8955649,7883035,1489656,3285815,128070,3554426,6561170,514919,8511696,7085028,4367216,4169079,6108267,9432462,6301510,2576885,4109311,8504936,9829629,338902,2807682,8875904,2504526,3026751,9563467,9246982,6188859,4395086,8120705,8310123,366064,7076354,6193158,1855720,362170,6321229,5410147,6923340,6836148,3921843,4008368,1203364,8090923,116636,635827,4392434,2693521,4745138,2897370,2523150,5084041,5705053,1399054,7588567,8731804,962522,6835550,4920663,5357608,4956255,3230786,5723673,2032610,9423945,7579393,2394780,5745175,2989540,9318121,2581323,6911384,3326489,3784688,5002307,3443126,4420516,9394741,6136647,9165654,2292112,8659798,4249696,7997165,58853,1838264,6728969,1021375,8673814,1649633,6378984,3630070,4880420,2102657,5662681,4304365,9682051,8057461,49541,2671592,7375583,2630864,9582976,702073,6415553,4585284,4145199,836069,3980025,281847,1724,6272137,8941645,4251420,4269303,9000499,6089684,998272,21875,4763499,2647905,6400860,8393569,7528326,8503518,4056250,1832692,8185569,2113712,1882233,857162,9489295,4513097,440138,191369,928650,5025422,4336568,1764720,9005448,4618415,1766444,5277586,3560061,6017864,9546889,2560560,2107549,545162,2582436,6871049,3193068,8983296,5264619,721394,7486814,9320870,2554086,5672384,1434582,4436319,6529546,923878,8949417,6969685,1115247,9878068,1995108,5451816,1642788,1000556,70232,3409232,6278143,3630293,9427097,5825032,6190854,1534647,6370194,8773290,8405696,9563263,7756587,3670315,284657,5243401,2991185,2838743,915786,4425768,7275063,7445332,5349647,6224480,4415017,6464895,6102548,6410126,1916712,7745336,7410683,1986944,1154569,3688826,5617238,581666,9513859,1808093,2116314,5884054,581384,522011,5447317,8337971,4192327,5731974,3581373,7183513,8570718,4497159,1609282,5845781,1942492,6958929,2070261,6357509,3423825,8172809,2767636,5340538,5918146,178319,7327482,7072716,3867146,2944721,7654383,3381005,4752814,9770697,9265059,5334198,292708,4712376,3672170,4485035,444351,7253544,1668548,9015069,1750703,3277830,4860850,3693195,236760,6931111,50705,3660586,5103921,2818341,9001124,1022068,2996661,6328607,8094784,6863807,9273328,5749167,244812,4026143,5519864,9509872,9360342,5812573,4222248,3032513,297609,4666599,286057,1966158,3681669,2036760,5243988,8542519,5729955,5480749,5473631,5780661,9141336,577553,8599003,8142461,1599621,1595664,4471068,9694406,8459472,3744397,5443573,8704285,7770541,963438,8214157,7130883,6776012,2436406,163396,7073621,7103005,449453,9039779,784675,2486214,4283768,9327194,8216170,9764518,4800825,3996831,8905854,5378379,2595834,7048315,6978000,4191499,1519384,6672407,2650971,5263781,2115980,1355256,3034322,3079419,9569414,165206,9855431,2005820,328602,6929053,9108826,778056,5968833,9893501,3264270,252601,9220695,1480440,17120,4021521,5477272,8922974,9399901,8073107,5971289,6377902,2264606,7490673,3050309,4915578,2754455,5166290,6270835,5788777,8245709,5840249,5953983,8101141,7846070,6282586,5030195,6954896,7060642,999028,6848398,324913,1251630,6069094,1805354,1268750,90615,7282626,191725,9490517,5355734,6163014,5868419,7620341,3653688,8918728,2535919,6408143,4085018,8806755,2196921,2330728,4647005,8150905,431870,2493076,4433492,5462066,9447972,1494135,6461095,6296370,1819048,7712725,2365464,3624403,8981476,2456080,907030,9173201,1946598,6262764,5336216,7815017,3883105,8989905,6733746,6419025,5398049,818765,5225781,7594971,3149493,9872786,5745876,3581364,2365862,179369,9043430,1813835,1673504,5504526,8110206,3492553,3217252,475671,7116956,2198728,2931752,8023986,1371930,4878350,4286750,6708147,2693367,8169856,5698052,9427114,4588881,1096102,245879,9814663,8691073,3395372,9687450,4436950,6976737,2053312,4616319,6020168,3867148,6289824,1524694,1977355,9782377,4741946,2453026,6899334,6940675,5384779,4923320,8312605,263129,9210071,5020753,2956497,7379928,718805,2383611,1968810,1814907,2629490,1783473,505980,6024863,1470923,4942931,3001601,3524236,9559250,9021769,7391385,5849074,546464,9368740,5631452,5288410,1821767,2530786,2229086,7206546,7454107,541692,7469676,6664179,5562445,426173,4044107,6281250,2809785,6012917,8096158,5439276,7796391,8602139,1464140,9267314,3545070,4465741,2791551,3104321,3487511,182936,8953396,4033975,9551677,4584848,9322386,1373444,7115635,1551472,8579990,4569742,2093165,6049666,1233921,7655610,6475840,5278029,3936861,9285626,1290947,2033019,4724902,9087338,635159,6189043,8354653,4180230,654784,1146204,7284552,4142295,1329141,6237948,8176271,880818,822797,7498657,2254263,7938432,9050130,834253,2508175,1143295,6883920,3742097,8798905,3359761,9020126,2735767,2645388,311073,4768787,7370291,9398412,5403946,3559334,7753065,9584177,4214118,8899270,6868729,8356414,228412,3106677,6532685,1109230,3929475,4031343,3363493,1867907,3081473,4197747,4376082,4224769,1081668,8118179,3023675,4441430,7138306,5759442,7086818,7449379,528229,4457109,6847792,5932176,8016444,4600857,5516353,2230562,3500128,2385083,586976,3728540,5491761,7119662,4837770,9421236,1151005,8201264,1289143,4232479,2399012,5665226,8457248,3480681,3783406,1480923,7922112,921712,7240365,5008931,8371092,7768595,9466041,5218884,3700771,7482485,9819742,9217125,9713047,3319870,1602208,300024,7048410,7093969,7419687,1886181,6515206,8570692,87446,7804349,2803171,2486458,3469576,1260420,5967140,7252982,2741343,3889252,8174694,9981709,8898184,6545787,7750305,8364225,1764671,1451077,5846710,1584413,668202,5559758,4904283,2270411,5859783,1952694,9364381,3279470,3838875,5879587,1850163,3926321,3683937,4653334,6412780,7153513,5913754,2379921,4406496,8655098,6269173,2581191,8636807,5167357,9126978,6387112,3531583,891650,7838189,9378293,2476063,8506392,4938051,7380347,776804,797835,9333041,141185,4077305,3171917,6020773,5927468,7098238,9704711,580803,3511019,6858224,6494558,5890940,1264720,5149656,2160114,3845911,3786464,7327472,2972890,173576,859055,3864540,8011766,237349,6340604,6518159,5175401,3720952,7294963,5973236,3053993,7436149,50541,6225911,3456923,5978010,3324150,3161634,6558814,6835169,19859,3053372,2726109,1284579,8203028,4886224,5130491,1989492,2213696,8103382,2163069,3072752,1967922,174836,3310101,8308526,6692995,8485502,2029478,3987958,4458738,5083472,1424108,4509280,1309383,4881031,487291,4633534,8042665,7046105,1468703,8062524,99477,4194813,9347104,8302506,9081037,4477596,291998,1294734,2580978,2455068,4367487,4548901,2629904,7677588,2857427,9322899,6163090,4886906,3310858,621829,9970379,4734966,5131110,1279763,9615997,5618401,5913297,7658663,2664506,7382001,5721188,2763984,1576814,5068292,1066491,657852,9545889,1358489,1952587,2126867,3813558,6320074,6675768,6443462,3997662,9533196,5766362,160753,4420103,9077220,782583,4390482,3812187,5913693,5670246,3428185,1532094,1583543,1086848,4196601,8965544,6808037,6960586,542359,1876329,8027077,1200212,1422219,9385567,3152799,3549086,3199125,9472874,224855,9642588,3470537,9758052,5408950,3631290,4178155,4486171,4413874,8568638,8298358,327567,4238884,1726543,1859661,5822428,2813392,6056263,4787973,9621429,3016850,5330332,1497759,1043927,6530545,2919978,429494,9683345,6469065,3628620,9156219,6693921,3271208,2626756,6451973,8680159,6258047,630129,3166330,671921,9198767,1464689,999489,3437652,3191233,2859151,9260080,6004625,8915414,4048054,5626055,1932264,9378386,7123815,2976192,5908932,43794,3405687,5592277,6512860,7034307,4748496,3206781,305516,7375253,9658754,8985676,3633301,288884,2152006,4305223,9487651,3616696,5304712,2925304,6807929,8163863,2185385,2812555,7079278,6233439,8438611,9011543,5611826,5562426,1987735,1520758,5606221,5393423,7113035,2119081,2427730,1861532,5325862,2733247,9236785,4984617,1718924,2870087,5273501,3870931,7175310,4761153,7487627,2480022,7686457,4295556,643886,9871842,7108112,7723164,6105281,5546723,6734707,1717108,1109150,8722443,3237866,6715371,4115866,350902,8834452,6543597,2212434,4160315,9276845,1449220,9144932,995769,4319307,4418434,4866700,1494618,9179587,2354327,3974640,6866045,6649884,4618527,6737888,3757996,2341691,2843170,9304719,9076399,4560278,413869,7798842,7798144,7129240,1914709,8149047,5963693,8458306,361481,124008,7735152,1810702,9268941,8730921,6130010,3687375,3597621,7624628,2866963,5951949,1599269,9733008,2601834,6217796,6470897,6359830,8559488,9314067,5664550,7635887,3874345,6078419,5434730,1672490,3207660,7349440,9821537,9171354,5807746,183019,9295362,3542898,1993722,8564304,2273820,8123732,2251679,5871442,5748361,5118643,1823392,7347631,4851651,4425226,3565428,1322549,785056,2124916,636616,6449606,9760804,4510962,2528026,5195535,6183453,5735686,2544975,6004991,4907040,8352722,6188010,4202403,1895621,8181733,2766707,4169441,6305465,5018387,40884,2053827,137030,1864276,9401458,4988682,6289502,2966887,6311231,7074558,5091803,6947847,3524165,4852608,1458810,6052191,48143,7642263,1787877,2593119,3647254,6694918,945841,9835265,897322,2841462,8016998,3664029,7010904,4322464,8682417,7051788,6376291,8819447,8916064,5777750,3808129,5205566,8744637,119361,2280125,3836441,7067208,5804290,8689050,8526019,1856481,8737194,6168282,3644359,1330313,9815536,339278,2276155,9650801,1236600,5117618,7667799,4900630,2128522,1990263,3583047,9180311,8366555,2402495,8096376,4144305,6210624,3301942,2888943,6329986,5582068,6725385,3397195,1386358,5414435,1923214,3242840,4151629,8091496,6887200,5481942,7907032,7226478,7758097,7557834,8463079,2875715,5225633,3363709,5004238,7215897,6946756,4184549,5582452,9349251,2280925,9726758,5559876,5582868,2615702,1889862,1164936,9341087,5287057,2551295,4755522,7210272,5794136,8907151,5301768,2681336,4389093,3208801,9907815,2147191,766635,8370894,5022906,5992269,1734604,27145,3208166,8681360,4211694,8790619,8030612,6492620,8517377,3590489,2075488,1133079,5480352,3240425,474166,767410,5791721,5229689,7977682,1585857,4136840,3279450,4267194,8525934,6488251,4175010,673125,7254887,2545904,5696032,3247156,4280508,5723177,6455322,2961869,9934872,5245942,992482,6427492,3763320,4582972,8502981,4896399,63324,1743406,5370566,830735,7535127,600255,8808417,9120985,4737096,2087868,3388180,3263030,8576120,7563190,3936155,5831007,109095,9632188,9078164,4389604,5355366,5533487,7351474,5290238,779429,8343956,1717730,4542749,2926928,220712,7156743,4231232,8253083,9124151,5813422,2566102,8427162,2309087,4138572,3342799,7053307,4491497,1616565,2257408,159655,9964590,1032033,6744355,9439797,5368114,6796887,6646317,5043181,3763792,7402934,3148756,2661693,1175529,1091264,513164,1066407,8248007,4744396,9319491,7372159,557818,1885594,5799321,2866906,6024166,9142121,9920214,515664,758686,2177622,675320,723277,3209656,7419676,163074,8577770,4216563,6809391,3620952,7980356,4212325,6769708,642049,5387855,7860972,1155213,6454263,6108980,5899610,5773755,3481139,6457428,7659349,9280461,9324335,3683516,8422582,9244549,4199181,9181269,1422171,4874501,9904546,4631827,2294178,67621,3209597,6510741,6877012,6830549,4491098,1089338,3600258,5133148,6477193,1461231,6288361,2931457,7570211,2187972,8705212,1051351,8645400,6364561,331813,7969736,48078,8754396,7214285,4247259,7935666,8636457,9121761,7840212,3268284,1415939,7907833,6477882,7926681,4784846,3308432,2417779,5874185,6908690,7550927,2351379,8369922,3839289,5282836,5940133,6027261,3988048,6991485,4672662,352610,7323298,2642398,400688,6077694,9856683,4647948,4013360,8493140,3769709,1853573,1761425,5185648,9761407,8239308,3112329,4546254,1547740,5530109,420439,8456431,3081036,2771818,6826353,6920326,8054655,2766487,2947587,2042704,9757972,7620250,2395314,7081271,262648,2796003,3158966,119332,7443951,7172327,8612473,1213661,9025900,373899,6399309,8787308,8613207,9511639,3333563,160947,5041748,3754002,8617379,8122785,6525821,5443733,5043111,4580476,8210220,7990699,6623181,7968193,5610949,9018495,5049464,5873598,1814499,8208430,5992931,9258450,5380758,4605404,472111,4406658,4979303,6871421,3193967,3592510,6383061,6527530,3753458,1424809,281533,2370838,9547595,6807355,7814572,4590706,1387832,6024792,2581406,8011013,3992986,8192356,7029508,9042451,4065955,8844008,7250882,58886,8102458,2631640,4664291,8574570,7038299,9643594,5445992,232266,3236105,1829053,6759797,6989564,3253863,7041330,9360403,2801458,3848685,7174975,7392165,5236518,3199768,9973571,3247531,7192754,8165928,277040,6235205,2231883,9121048,3486087,2290769,7223506,6117728,6955060,5798077,3156027,6598655,1244070,3388293,9834761,3073124,148091,6824326,6326987,7189422,6184729,9128445,1038108,3359705,6520611,6274626,6559473,6494183,9522157,3752228,4660111,9799197,9987433,6891994,8920245,3473521,9182763,6143752,9591249,6137824,1941830,2747277,2736479,3185900,6135571,2571240,6259025,6283662,9395566,2586012,3473084,5580296,1714458,4511192,8940001,8235069,785819,5499474,4729252,307976,9251702,9389363,107174,9239136,6281358,9027419,2712658,5464121,5171172,2303908,1601945,7113002,5051185,4338425,298903,1186756,6909666,6557928,7470419,6305233,9143941,943503,1885529,858400,5454696,825531,9093469,6240515,6325006,3822722,6548492,5576708,3212086,6655666,4815845,9493444,5683086,7528504,4957566,854258,9832412,6559512,7967261,4883598,897937,8266165,6070354,7807603,4824094,3540774,4112836,3968036,4484278,5998366,4826436,9938974,6823897,3919906,6179490,3148903,7742629,2727982,8725612,954715,9383649,3541458,448160,5066735,1069962,5405726,5920994,902375,1965238,3888256,5785973,2863176,2154422,1856328,670780,6978516,5397102,4783616,946553,9881380,781983,5772989,9820355,7605881,9692895,5999845,754785,7435524,8727828,9480398,8390240,8111478,3021856,8838400,3178213,4091818,4244127,9099208,4994194,6209366,2987464,780167,9072543,5141886,2636495,9743323,2120403,8033597,4526939,3066956,7914977,5308923,8839946,7735333,2914804,8532841,3735178,3669590,5968366,2463007,3149988,4358606,574485,6171844,3197007,3752699,263663,7441135,2851908,5257857,3650502,5839372,6038024,2723045,981259,8674520,2466368,3101663,6708117,6993308,6168620,4623095,2302231,5008566,2358428,5217036,3541407,6093607,8886626,9509774,8556615,2036614,3868381,9131100,8208459,7065388,2883800,8472122,4506524,5735708,3729980,8157026,1575081,9768004,880071,2556341,8442524,3346439,5658004,5150642,339748,1826625,9773738,2641979,6835191,2132166,7859016,376599,8225774,6745642,9886373,6782389,8782256,3754754,5913489,6990716,820143,8797290,5462838,5326668,4532998,9192818,3483694,6108079,8960823,4363766,8664420,7403348,7710206,4322425,2553991,8049954,6149050,2327729,691933,2984241,4459895,8550949,3360841,2685670,5296592,3247214,9468059,4078849,7001969,5381549,1069565,7822113,4178839,6532403,3148781,8711837,5725222,6632476,4819917,4686046,996242,3484338,2089394,8706448,7806764,4643386,6756402,3955814,6971115,7448336,6940056,1431011,5999286,300897,4116681,1295878,3548112,3584740,5374727,550082,8966290,6444293,8372195,3145129,2976697,1520977,1856967,8701919,8153453,6676884,3387966,9149695,161223,5477360,7856144,7967987,120747,4612546,1923801,7091862,2060883,8863858,8522873,8060169,9164756,2639555,9356047,2712869,6224295,4730775,3262951,5190586,1175068,1635147,8335715,4151765,3156125,192682,2853685,1309578,6869567,6241651,459274,7030790,1719012,8315418,4998778,1839759,2927965,6922580,8931621,4988848,5786438,7454495,3049018,4951195,94050,2405066,7664064,6318346,7135841,927016,1508932,8310910,2562163,9844648,2462676,5718288,37331,5316361,7027867,6906898,1558013,7487141,3937689,3277025,5802560,8936467,5116785,8730526,5859048,4048407,3719374,1645486,1502902,6768393,6596681,1596953,9173459,4260746,7915300,6309300,5187762,9424232,4620211,7749926,9268881,7082887,3468215,9306212,2399248,496082,6213111,3957262,7983224,150800,7234287,3785784,9087268,2351073,2516310,4946316,6399480,6235685,6591803,7902383,3004079,3188485,9499336,2177538,7449231,7414637,8486839,2636993,6838869,3107050,386920,6107750,189937,3855135,5413963,2589186,4351217,1627074,6546448,2334441,1777874,3780736,6120226,865143,6131810,8636537,5811460,2531290,4872223,2403264,433674,7876302,5591749,9933011,53840,3040981,7347648,8540679,5677975,4186517,1647730,6064895,294268,1837668,9920030,5708231,4426854,4271247,7335305,973303,6605689,9113180,4754040,2725916,9978324,885850,1362453,5789785,3417141,6234677,8193049,3850815,4110979,3784799,3783826,4164820,6825780,1131474,2705500,2503756,5317992,4353231,8568651,5612261,6190899,8488681,1320493,617754,2759929,8655799,1591057,9365619,7768980,6345098,2091535,7747305,7230949,3453989,3537090,648091,9688667,1730140,4498906,3799647,5514939,8282733,7964467,2340720,9414208,669968,4844476,4732201,5023200,3413127,344463,1214099,1901809,1664956,1831853,4661739,320756,3422911,4027358,8089736,9768010,6118894,5837041,6998959,9572884,9374132,7647050,9261551,1104272,2145957,3061198,6619211,428690,1025666,8959932,9842899,1695635,3804408,4575101,6718835,7217536,4919564,7932934,9119346,6584521,9764788,3781085,6905277,3187699,7808444,4995014,2955709,3927339,832055,9954669,3500223,206187,7601719,2761775,1310460,9747676,5822974,7929671,176367,6848640,6889604,19267,8544276,694012,4594368,5263111,7911549,9513933,3196046,7030896,6098454,2960835,811981,3003732,6148534,8620426,7998746,9104244,2547766,8830801,9058913,6047989,9036989,6660633,8809765,347449,6408310,4632739,8277121,6584678,1481379,5166725,6603945,25656,5860738,1198314,5288767,3772288,712247,8484814,803184,6810702,1445649,1615166,9814434,7594184,235593,7813180,6698428,2783359,6643982,5757342,8831349,5680972,2417976,7641114,6028422,8826286,2273853,4305543,5410964,3755233,9472269,2014910,3780889,5333008,3213225,9069657,9105297,3925473,7554472,9908482,736175,9000121,1523648,550609,6594306,1759242,8363790,3292735,4542601,5007772,9050077,3373950,688745,1468054,1015065,6717167,294340,3288918,1022711,5705305,7044151,494981,7720215,825041,5827990,933441,9894698,4933287,4858914,7449170,4841769,5595089,6449292,6365418,6145699,3043598,8124660,4509489,6336333,2667262,9517262,5386411,6041212,206007,6854465,7056278,6923175,7148806,345196,7945886,2854111,7389348,8440867,574327,8214389,4268858,1507768,8109087,9202145,6366682,5558258,4043915,1961772,2007550,409333,8107472,5051149,8533994,2616962,1387483,1201256,2134225,6773895,7242469,2340232,3628361,4298747,9263408,777167,4643944,7209294,3631279,2033292,5650162,4205606,247681,9919020,5713375,8356769,9121166,2080058,3915027,3165081,4041831,5922578,3574415,2149303,973727,2108410,4766265,2361211,3309667,6900490,9135106,552136,9240723,2763467,4850884,8504131,3540635,9494828,5713426,7171914,1528121,1363589,1377521,1775802,1282610,7090896,132572,403776,9170955,4047599,3568858,3212786,9970178,7143274,5362090,943905,9251684,128355,3305117,2561351,7028846,2440223,3113488,6269569,5203690,7964372,4773701,8744326,7459201,487128,5916240,8987322,1850718,7293761,763125,3133328,4384658,895697,3537105,3555614,4943297,7105964,6768400,4913475,4249238,2130491,5857381,3500923,2258846,9162498,6062274,9287693,1602721,9175763,5557263,6806412,7140136,330964,5550738,4599337,818093,1466979,3586660,2668811,8760741,4349786,5802140,3145400,5245483,9339245,6701014,188780,6445209,3469415,5102256,694447,5599906,959637,4195371,7858753,122136,257645,7146446,1724858,9433409,2703709,8531270,6573545,3034674,4082009,1172883,3852768,5548989,4759543,6521580,4309730,9109330,2323720,7455130,4354813,1662965,4156145,4543594,8108175,7625560,9645851,8802623,3225467,605489,2997994,1084220,727625,3255639,8230667,2452483,2689048,934377,983754,9262594,3969051,5065764,435477,7821820,614753,5195021,4343400,4924483,4304351,6667120,2379614,8659165,8330086,6535759,3202760,6438261,4161320,2848611,5240884,7386787,3454101,8238878,8471008,4181726,1494518,6701675,6634209,4183567,7636053,7617964,3446161,1605105,2683728,3881638,9426925,3298482,9076660,3770325,8222966,3381012,437446,602580,2040177,8767532,7138340,5242938,5205793,1299661,8091550,446678,8686448,1545651,8685556,7157457,5727377,180074,3859133,2361587,4363641,1495186,9979552,7809803,3100291,2663280,1691442,2527216,5961762,768102,6297542,4184729,4149114,6734988,4787309,6189292,5502521,1925650,1432231,708315,3225311,9523781,1154993,1911760,1069432,9840549,9069218,6796810,20624,2928351,9158397,4384266,4423537,9137949,2194069,7523829,1801230,3885512,51045,7762993,4653614,6348588,1947722,8802729,3083577,6735032,4992022,8586099,8660683,6424253,9294414,1885994,5948034,449407,3797755,7017467,289957,2866973,3814277,310582,5795324,2972674,4694848,218862,2110624,6888918,7742691,3911855,774430,7793737,1674848,5428045,4142326,3622570,4230775,7225903,357603,9222798,5812002,9018286,5647051,5106417,904281,1595086,5555825,4702036,8612554,5845782,7569010,2426831,6156364,3364335,5399506,851213,3583197,7510130,7740131,1325889,1421985,8514562,9119627,3096834,3942607,3261953,6719405,8173383,487857,7077008,7396181,6299860,6095295,3043233,1406277,6999576,4638320,6962102,1701613,3250874,2807884,9270623,5677705,8964249,2634958,1077211,9815463,6218156,8587342,7555594,7544045,9328,6070157,6663673,3106163,12765,9925626,9825568,8186148,413483,6902577,5582330,6713343,2997872,8625563,8119620,9997448,3263884,5081723,1699061,6514758,7889608,969685,2192463,6853857,3604644,3269675,6669321,9822800,1857018,4224916,7366846,1866347,295073,4030519,4972510,307838,3956146,4798078,8493987,4369630,1700655,4076317,1082973,4698528,2701881,9202594,4695976,5965766,4284318,6395038,2480524,2173926,7364724,4672988,9027784,969368,7942663,5697105,792169,9799682,9922021,8159015,1666029,217094,2189535,6638540,524933,6145682,1436618,9018920,515312,3137274,3095238,1598285,7835802,5797120,800880,2531779,1762886,5085198,8926818,4243411,7259124,6291543,8916399,6286909,7260911,6859063,1984014,8053081,6658745,1906035,6212097,8324775,2123130,8401632,4963315,2648064,4547315,6399934,1666985,5062627,9537209,4762223,6660913,7373012,559344,7461793,9904791,2322231,2546992,8831610,6565642,9806117,5123153,5482041,6093026,2384065,2341105,8077040,437146,8999850,9983076,6649244,7324626,2106207,5050876,2287941,4754271,9598191,8687876,6421256,4660819,8225085,1183480,1321732,5598097,1742825,8783525,5502889,4065056,1330518,4334500,630699,1136635,9457653,6112740,7229661,1841719,8453846,5306702,2278866,7453697,5289779,8928110,4778323,7395986,3978987,7066265,2150258,3577179,5754141,8571515,8237998,3979226,9754995,9559730,9577323,1497820,8343256,5080213,5562877,9673774,9414713,6193576,810410,8872367,2306317,8040071,714086,760163,3346774,2992953,8213860,8636554,1921064,2992183,6032541,5900051,58448,8182799,9477231,5812590,6754314,7715230,9791816,6509310,7274960,9369140,8007131,5618217,4449354,3570008,5291992,3864067,9763584,6102402,2736434,2069902,4142474,3450521,2830065,7489248,6443475,1043926,6125802,8364539,4036110,2158343,4264591,4094559,341143,3741822,9907149,7095457,1457053,9698966,3604768,8732013,9068107,1611899,4350231,3517461,5181907,9642223,7381528,4945492,5744625,117963,7015394,9887099,3568485,9845460,7376348,11960,889386,3502150,8376500,4925496,5660494,2641091,9020056,6001637,6382914,8927205,3097095,7839967,8626171,6701863,6571981,7694278,8313763,922212,1211740,3495671,564436,8593269,8441163,6309061,8711232,5456558,6196161,2279717,5302019,3572509,2291678,6191406,7074660,668178,1116902,2735155,3309270,136958,8736792,9692184,9064164,1833888,7532152,7690336,8535752,4104133,5384615,6849515,5026346,6596355,345187,5590782,5189624,8786350,1899844,3900857,4242909,8096005,6180574,9544928,1668515,8472253,5736334,8743176,9140431,6853237,1478331,2449702,6990196,215124,2141886,6054361,2049012,9674039,3744697,584765,3778173,9129312,7434281,8804519,5725667,7779468,4395302,915292,6565818,6295146,4816149,808728,4391152,996724,353657,6059668,9468977,6089992,4802844,8609409,2943229,6281176,1059111,9933426,6496300,3200998,5987787,8545313,2875037,9732485,9130078,6653210,8861797,6564359,5457730,4587465,4343827,9853032,5502757,909646,6148179,318906,1718374,539332,1315630,2072032,6599000,784607,8162024,1401845,9394017,1105253,7683021,453128,1038680,4179322,3654126,7026468,2724635,6529164,6758953,1854713,3182374,5620751,8419073,8640105,208216,2762900,8493137,5710973,3672547,4641317,6029880,5390922,5180649,7345510,7462954,1779650,8130118,5624978,3181496,7524135,6730232,864517,7977264,7768913,5043840,1631391,4795381,7768475,8160555,1554335,9623189,1342930,7175086,8042262,9983035,7383303,805163,8476173,3094277,4477711,3117490,9124157,9868633,8298140,6469667,7331588,77791,4599786,2956566,3259287,2123922,9686799,4123805,101187,7455712,9167645,1732578,2251094,6936120,9893134,3805430,6559310,1236064,980517,4601572,1219100,8363820,5406736,9695273,1458097,9884447,2812764,582254,9753080,1110905,7051922,7084668,1188696,1651709,41235,4447984,3775631,9728035,8571789,3876819,7183748,7739435,5609397,9434843,4675555,5502531,3240273,1234865,6738596,4220790,5836438,7957696,2584611,1243174,7652969,4042709,1127621,465734,4624963,880702,1576639,1676886,7965371,2765336,3328596,8006607,7213320,7104228,7734642,5785110,981047,4918391,3524545,6590444,4353234,8200101,2092976,7593508,9434967,8831572,1814299,5271405,6789268,4398910,6514580,4442238,8441619,7642202,4907972,3066583,8522905,6484612,4743470,6488276,9249949,8072066,4494884,6463270,5176294,2229527,2248380,6157342,7147918,5772926,2747786,1501152,3973027,4840762,9094660,3407995,3672335,908959,8679401,461603,5307870,5193981,4903842,3749490,2836184,9811815,6816073,1359089,6296427,1559544,7847366,5546377,9631611,2342250,2009647,4807905,4571777,4258028,965247,1719695,30954,3713034,3220848,4003982,8553797,2315509,7411977,2226132,3224469,6091378,2687736,8532339,1285360,7591578,2281830,4121544,7403393,9097903,5480634,3699821,657448,3328000,9246198,289059,5670251,1255846,5096965,242029,5513874,6062213,1961725,5544828,9775247,5182573,9548810,8329045,7498083,6960788,555178,722552,3052166,3242914,9254892,4337527,834493,1536722,8459072,8237886,634626,3939706,1937708,1292074,7267707,1183907,1581133,2937958,2439753,6678099,3179987,7953628,2740312,5141712,3498456,2515560,324286,3047267,844605,7822369,8056,1399783,8544922,3060223,4642698,7799814,7397750,5477191,9336536,5856822,3715078,9971163,9796529,5652786,1263237,7064236,6836694,2844371,2195,9276447,9522470,3182183,7230075,2262783,8323896,728532,4778343,8648182,3775800,5622949,6470552,3783856,7022733,5015474,6844079,1665432,2815288,4241830,7142623,2151825,98653,857702,2122988,9895182,6510488,3386226,6959419,3347182,6230598,6961614,2623630,5753069,143797,9853706,8015852,8467693,582238,2794196,7115876,4358039,8417146,3586428,8141896,5439879,8601902,4985976,7105312,1417191,9227806,4247935,3569017,9326459,5105637,5692006,9221642,1616126,9078232,6181061,4963309,5308830,3142675,7586940,1061899,3286473,7440646,9077752,1754167,8022885,1871948,8870043,2380924,289094,2456471,522820,5728974,1058374,5508796,2834286,2475566,4736603,7082222,6044583,4063063,2187860,1736589,3284705,3803987,814822,9465766,8767296,6123652,2608442,6354237,7185552,5894916,3794883,6263304,7649083,1817768,8135253,6519126,4198693,8424348,8975598,4721513,4153323,33972,230310,6987610,2509538,4966913,4069832,8554122,9029976,6257693,290711,2314682,61680,1105533,1780448,8828977,7229186,4388891,5183214,4414739,283807,8978097,678044,7932890,795866,8813297,4452017,4994559,7237646,3427615,9716073,1390969,3461588,9946383,8378579,5971126,4913297,2448412,4525249,3943274,8706105,4815961,6257956,8767786,5921495,8038405,7596763,3150681,2427296,2779978,7565420,2711104,1758075,8243464,643994,2553942,7056762,5096012,7548502,4294408,8523627,7264575,5685378,1985215,7210959,4063957,7956342,2124257,6512370,2481591,6067531,5218476,7297552,2325487,3986262,3219047,363893,1583025,6369729,2791189,4363003,3935150,5502293,6121079,2178615,6146288,8675022,9235378,1242301,6223524,3529786,9765928,3488100,9215164,1751144,699059,3279122,9707486,2823316,9791493,2189078,8890848,5009969,9486631,1216336,8996231,2705678,1580229,579257,9075408,4371419,4942261,3010558,9873712,1063340,5189174,6020001,9738363,4424552,7262303,5961887,7954339,7028231,9449987,7169504,8779375,149047,448626,8486862,2972364,240120,675941,1863212,5250089,162572,3079549,4246320,2868251,4659778,4825578,1943659,9031197,9767839,4954218,8904910,831180,143392,4924912,569543,4567944,2187215,6531430,2522283,9215447,5981418,9691788,7994823,6130466,140414,6481685,9102830,380535,7157626,966043,5630624,7320199,4045592,9876945,188450,8705371,4702523,2132109,7736568,4470362,7086327,6641479,5301542,7229720,1566391,5871086,1797665,3753607,2402517,4319949,2969054,8383935,4011737,963877,4514401,4152152,7445563,3617232,4532687,4603190,4583275,163311,1923389,8628868,40256,2111839,7334239,4742780,4243949,5070808,9213142,1330277,1712287,4514685,8559997,3278679,385771,357662,7032286,2788289,4677611,1341,1172224,8689349,965218,5686626,2841501,8410782,9303859,7374188,3013972,3887135,7537499,4937362,2516003,7577756,7049201,9850242,2320536,1293151,4921050,1533679,2623428,6633338,6048364,1183425,9912017,6434136,1541088,6944304,9222425,6218700,6945645,394650,4908049,7910864,6081277,7749550,6321646,5385137,5123739,9335618,9272272,2661239,4272980,1788275,238995,1322182,1638518,2559532,2615333,6559569,4093211,5238761,3192907,141576,6422187,3104925,6575713,7963276,49229,5798139,4181976,6994875,6192790,9090026,4905739,2274067,6839577,1227385,7659204,1963316,563004,6931476,4624555,4835985,8719752,4863551,6158168,358270,7423083,8773501,6917840,1516295,4012263,110748,1657872,434451,3215673,8233586,8397727,3264903,4031725,2579704,259778,224515,1669730,5165518,2498583,8509308,6392903,157788,472624,6955908,7089265,5097179,1791893,5809017,9960731,7950061,6167288,7383815,6723563,3085128,8900110,735827,3195876,557983,1170278,6411550,8791569,9568006,9676454,2823295,2147710,9936232,3047811,3817441,5101751,5546394,2326750,1494654,5704182,2799374,8450563,2793447,7896554,242456,8602465,7857285,8192518,4769754,5241100,4916082,7854882,4141211,5651909,1050759,4699194,6822188,7462310,3490764,6390194,7138764,6314059,8537905,7074997,9361871,2355347,2176748,4908265,4682097,3671403,612448,7481472,2121966,3405896,5378026,2364423,2008361,3235312,556942,6778115,8476413,5473024,4632998,2617624,1124934,5683758,7316819,7947122,3146069,807584,4337317,284833,7121644,2875223,7359831,6483515,5230570,9536579,1391780,9912668,3207983,2004229,7394140,5329950,5410125,2772166,7694374,7418487,6007479,8251316,4196603,4483892,3724341,8829602,7101516,4849276,4513360,4418336,2796399,7659429,5225920,7133716,7944263,2347564,8939,5304094,8831079,5239510,4840674,222860,5152178,8048657,2227089,2546318,3378608,7637215,5318485,1072982,5055702,1325964,9324299,9252306,5809856,3048641,8081908,2911373,7897917,2595269,7329709,694316,254699,2555629,7828033,8198963,4903194,7836972,3503057,3734274,3076482,8343732,3957135,8228661,6392389,6184225,774979,9770998,3821440,6093465,843980,8877143,7419429,168279,8129450,3229285,3216920,6211358,6140659,1114838,8806628,3470368,1809154,9061328,6025998,9637188,7260291,929193,7474160,763348,4663467,550643,9107081,8620603,8779305,5499471,4804828,9554284,5270469,8626269,5647750,6114449,7503413,3067179,6282729,5632863,6296465,9499649,1844222,2437124,614488,650851,5907493,2423642,9712179,1933491,2060830,6972470,2862684,9534991,7735819,7526152,85635,6842900,6146755,8864940,2342371,951583,8419225,7612840,9577853,4066975,3727290,7081266,7134155,10019,2714130,3430620,9509669,4558353,5867745,124157,5209204,1775238,2547800,4921384,3708729,4608631,1893854,6571413,4143622,9629674,4097566,4229258,6472575,244321,3094198,8814946,1195905,1513424,6427787,773758,5580399,155078,7855025,2714554,165097,569156,6145175,9674766,5127510,2012920,9798924,336714,3788158,2346724,5258099,7496887,6955355,7151953,4068301,1098978,6781628,8165868,5328237,3254203,8410189,8422435,2069150,9606095,9935860,8496938,379854,5516260,8652016,8234880,8230814,8817113,8804036,4375990,8491880,3931546,6388910,8290804,4268261,177069,637529,9526360,7673957,7592885,6678314,1742259,8691863,3459942,9908127,4020100,6714146,8318316,2442536,8783296,7924412,2378397,7280234,8304266,7894657,5932250,6539146,6125471,4749364,5343182,501462,3241244,9274729,6890372,1532049,3542991,7067442,2169578,3069351,4741399,9762463,9747666,6483658,8454327,3207609,6391785,2474428,9921755,4710102,4916965,8705052,2634514,7295362,5985286,938780,5190019,1917537,7477927,1315491,6666901,2821109,1816953,9908146,2095839,8707326,1440195,5638830,5774768,3609774,8708182,516167,3372238,8455849,6999826,1826565,1663458,3391612,4300994,1585213,8101715,9217959,290266,736230,6513321,6275552,1675011,1703340,8193090,9152938,3018831,4859991,1974048,4835785,4768137,4069887,3543111,6208333,9708718,9317880,9818107,8416900,9834048,3190345,6872749,6833874,5016911,8536208,225487,9317905,121422,8327202,8535864,411688,9063432,5049185,6687241,738443,6752526,4880331,9891381,9771358,9740322,1865429,4607144,4508460,5935317,8150255,716793,5644035,7468136,534901,4060936,7302184,3725246,933686,4136059,8742158,9469894,4361546,8060063,9591316,2688748,6595927,3004,1752181,1645113,6690245,2490625,8397640,1570577,2382006,8168999,1310899,4247436,2776143,5819360,182754,926399,6536154,5826789,8394535,7071055,9887725,5696719,796302,821411,9832778,9538460,291306,4194324,7598524,9882622,6883073,4194451,9885627,8635254,5839565,6575873,1125879,4237206,8146450,3507886,2406205,9457350,7755323,5182348,5276711,7938077,6108747,1812865,3764867,4503282,8883921,3652593,200002,9680223,4474005,32780,9218684,4765311,4227105,6817208,4647934,1110178,1011660,4533561,9745433,6851226,1109435,871313,1088432,9255886,4379199,3494637,8713237,2134523,8676986,3989948,72601,4785734,5802813,3837468,9289016,4686734,7490061,9489018,4366958,1964066,9521799,3585642,6729378,3748904,402851,1377312,4859083,1414512,5910873,4604517,8265738,7020309,5475830,9354171,6276195,9855030,2848809,4989432,1989553,1525795,8979380,2062155,6311529,4782194,5899623,5600546,9468929,3389685,5089565,3835887,5353751,4611365,7421530,2083129,8360269,7824382,3460441,3219353,9238894,9371315,7823870,7504632,6391625,3299701,6858803,2667820,3154731,9707612,7657253,5144285,1233408,6636634,7206440,7544938,1418828,3106063,3145484,887757,6495749,8235050,4723645,1849500,2846415,2145176,3932630,1206685,9969558,7393072,4426038,9208452,6764388,2249909,6713084,3156013,5549610,3571888,5823833,8704342,3279501,3481087,3848627,4512910,117721,1055068,2057848,1536549,4161132,5203332,2424307,656881,3438383,7147953,2506381,6284798,9293129,6439012,7491483,9262687,3832084,1917522,8471139,596472,4167431,5184224,3752485,9717042,8756113,9576319,8421384,2035614,3057407,2270011,6548524,3175128,3325079,8606373,4711678,7486211,3809706,7135986,8143092,7248089,4283939,649474,3532887,3577068,7088486,1024371,2839756,920571,2941893,1310895,1517044,7109324,6495120,5269530,6826366,5251233,4845849,5247750,7286848,7903257,7517762,3835373,1078385,842842,2441746,5790063,8329054,6251453,2926050,6472146,3499542,7209989,7121621,7032430,787058,4210108,8056801,3626815,5130679,998694,4937711,6647723,8108019,1432831,1917253,4934386,6684065,6763103,182137,3970913,4666360,7699900,7806287,5744746,8542742,248034,1534810,6871796,6499487,4460860,3343943,9999029,1670850,465565,7031460,2457909,4675673,5088261,6084724,9806353,6086956,1022435,6454077,4194976,2455267,8371331,9129363,9139332,5134434,9311500,3110246,9800795,7011400,916533,5545541,5554143,1164567,7080352,2425940,7664054,1541212,5769884,7663084,3212063,6235449,4694544,5669972,911123,9782805,1754697,717477,5869762,2777132,7171554,64739,5232400,5542885,9194102,4371732,677320,8505602,7481978,478115,5517003,8398511,6023657,1071147,9563078,3104010,3497087,7227133,4645222,9266972,4890217,7857286,5502422,9584761,3527258,6413546,9367567,5281956,7131023,5237330,8059089,4302577,5302069,3291489,9845463,4496171,7663221,522783,3001774,5145200,1000899,8518777,3543712,7024557,9589925,3106791,128567,3087013,333924,4773790,2353985,5224141,2631076,7856408,4808903,6158335,4269954,4176471,1440291,1400977,9413801,9499380,5703555,4715870,2790869,5549018,9212042,454091,6071802,2213816,5599291,7072701,732594,9143003,4097259,322519,2249794,4225826,3409532,2583718,8999617,5763518,7807860,1630693,3619926,2616764,7789028,7889880,6793235,9229320,9290857,6207037,8728700,4994413,922907,1519569,543431,134950,1973661,6615233,2348766,7572952,3687935,3081360,6715956,7785194,3403880,8965750,2011021,6813412,1549469,1010638,2576931,9357330,2641332,6196857,1974094,430361,4086738,8767330,9659681,3377596,4974367,8388381,8372009,5897275,9907951,8915440,6032225,1881612,5530674,8380992,9454565,9218609,1462352,6170521,7003804,4866232,5136271,9014826,1679645,6685741,25465,4256576,6043071,2666797,453433,8017166,3097159,4540172,6784497,2756840,7917768,1758864,1145222,6289777,7656140,1053173,5205217,3688365,2934786,735892,2069358,2389351,9954502,3531710,8559872,6958306,8397943,3696144,5973133,77588,381886,5998598,4334165,6424958,8665396,4787599,4442124,1762555,9327771,1226622,4519396,7245539,2985486,5664618,3535316,641627,6717791,8740534,4329993,9652578,9476426,6399351,2041929,9430928,9931061,601801,6389235,8329005,4297946,2362369,8406593,4679832,8360967,2740758,1104790,7026364,7528357,5546915,8788919,6856129,6773537,3308316,4101668,9759024,8972934,7636984,400651,5690726,6377518,4730644,5343304,5853945,1129995,7385233,5284873,1061057,7987035,1674109,9390063,2284981,4036478,7796656,6964813,2397446,537415,8069604,9423810,8065773,3616519,8212730,4921902,390056,1521046,9023570,149080,493980,6660555,549732,6184706,3038074,5280376,1528011,8892019,6410372,8913244,4176893,7471430,6900279,5851002,6861493,9185261,9887481,4658150,6150075,2284927,5195566,4219679,1708737,3261340,7836198,9921468,8183242,8226255,1442514,7206813,8375335,1936495,3867369,8925067,8121202,6905443,4205444,9649213,5797462,615817,8562458,9974355,8087247,5462738,5825357,4948741,4647999,5712839,9606891,798075,7997766,4802458,5017754,9706504,8063798,2853953,9627972,6247041,1080208,1070487,3453854,9455544,3006983,7321224,8380612,1128186,4226667,2586057,777400,24129,3201874,9339858,9998484,1289122,4802597,5823842,6237864,9450597,1536681,5844755,248672,9534448,647214,5266427,9240953,8711012,8120380,8868926,4958053,9200589,9939413,8411908,8656134,2946397,5733132,7036746,4074583,9959799,9622803,4851983,9983929,2824678,4191842,9982414,4113801,8994439,5806256,351665,8445036,7342938,6196421,8693709,6877387,6843635,3960136,6118340,5554647,2080517,4987266,512701,1281106,4926680,8924610,9937240,7873077,4657742,6973987,1947661,4617542,6596791,6799645,4601471,9421470,991487,4583885,3535271,9985927,390142,3886936,8430964,7733081,83357,7124673,4610468,6926992,1084810,728809,2481640,3165327,5716075,2994342,4446434,642756,1918952,4383675,8515833,6576694,1357662,463495,1194236,7954454,7263140,5795708,7375924,8254628,379593,911196,8240555,769736,4798132,6671519,8502817,4881489,3796193,3113285,1808482,4881003,3842094,4290123,8046331,9558170,7284465,2492765,200926,9203417,6876440,8716760,5780112,8234103,9180255,6974349,6188558,6443396,2770057,3564483,4698024,3149651,4475679,2938579,3919387,9273811,9610099,2422204,4155301,3406292,5535490,5963784,8287296,9377585,253908,6333627,8935756,7538373,8826393,9136682,6741791,5702834,7853443,2521904,3936938,7033698,9496253,125496,3477094,2266311,3689980,8175119,5415962,8165659,1113698,9335350,7439471,723798,1757554,1594773,4130090,7293045,7558557,2417387,6670631,7812466,8751014,5606387,5350839,7577407,4743069,2092631,3280242,2596512,4614535,7217180,9630211,4110789,7342677,3107306,6377100,1032657,1282425,1793063,9198316,2396124,1128413,6637788,3119922,2885968,8232561,7250013,179013,5791119,9667400,6849644,3603585,8418415,2456032,8954425,5995823,7199101,1047056,9276065,9795614,5661592,6493245,9425826,9772381,3835922,2533133,6149481,4868579,3815558,7942544,4066896,6211683,9070957,704684,9331605,1956926,8937246,6581619,2135939,4728365,6249020,8985584,8331950,4667435,1441616,7286376,663258,8640718,8333432,9939324,8436333,3995025,6432570,7862160,3767406,268493,395293,9916887,5137073,4210852,7859432,9203969,422536,6930390,9908654,9754142,8887316,8845900,6335761,1023256,3574266,2584781,8841,1906217,7252216,1450458,9192593,7915475,91176,7526026,7854800,8527510,1521051,4287370,6389671,5288457,4555864,6784964,5205345,9692937,995817,3064777,8896907,1418353,9995168,8805561,1172495,8882484,7651462,7508257,9905740,1225728,93038,9914581,3131945,7345255,1365039,2324539,5260731,1456216,9850565,3115531,9983727,1371616,7402902,6373398,6660074,1958766,3158363,1865420,1651703,4154181,4930197,548611,5572534,4925366,9354173,6745030,3807850,7005635,4253287,3713591,8231364,4346326,3628173,1363310,1691581,4993213,3687849,6952312,6449429,3538414,67844,6433157,4910031,7470746,2806556,1570106,9429513,5964919,3435526,1081217,119101,8365724,1629828,5691635,3291090,984001,2436666,7098940,7989637,6689954,812531,6221002,1036280,4440705,7584312,2727861,9433918,1272161,9680174,5883347,4810576,9748019,2316505,9720607,7218766,5123061,1290713,6648279,1087981,4726240,7729497,1207082,3091964,9359325,6898718,6383054,343327,9335384,3481994,8332965,6025338,4294526,4553967,7061619,8735231,2138279,9789480,8169149,3410440,9469655,4052497,8221017,9217674,6369003,7941625,6436441,1492064,9232339,3084720,2580045,3958579,814217,3787128,7050543,173543,685846,3433597,516871,21231,6915592,8849836,6046570,1210119,3403803,3108189,9945350,5542082,2897670,8114500,8952523,2367326,2166998,7173540,1585001,8536001,5115166,8021442,28066,4347505,1106162,2608112,8306084,1920380,6395240,5356627,2093924,7081087,8790225,2610795,7102319,5705817,1460631,3148889,6915936,4864434,6257079,6861287,406517,9154750,4975788,9359041,1522076,7142787,6532581,3107078,5678788,1647748,1128520,5706854,5995253,2234683,8314967,4301337,4155063,4710207,9657965,6248987,1791295,8448190,8859783,8893614,4154008,320414,2042504,1069945,5184849,8299583,7931233,5591366,7454334,2907021,4950407,8976411,49809,1482989,2083489,5728597,3130737,3212009,1435452,9125990,5446692,9750419,3427328,9601756,4460627,3085294,5850743,6251922,1533484,4710526,5145536,5687493,5030941,7188040,6757438,215790,5487624,4688671,5807157,2941959,7595693,757565,1918370,7645502,2240554,4001859,3374100,5371292,7213868,4809553,4497283,2660561,4559973,7924612,2262317,9020601,1009906,8113061,5272523,2543390,2823588,418060,8230884,7854529,7606101,4988322,8070320,3093725,9676994,3877477,6035684,7272687,4635043,7954055,4918190,6875597,1955914,8292291,2246890,9169783,3101844,6744173,1830344,7661818,4668785,4092662,6682419,5678691,2205723,1954943,8222082,5029312,2373003,6452966,2883842,9979104,1441289,954162,3072830,1118283,4831640,9108515,8390971,9466683,7062570,3309162,6342281,9018485,1601453,8589171,8188269,4703298,5333345,18614,2365116,2131,4111276,9047536,5680823,6317000,1002479,3902906,1346312,3375482,355873,4230154,3354587,1797162,5184317,6427417,2915446,15957,5535933,1306418,9482641,2598503,4615580,5824922,1616989,6217033,4414094,9805258,920332,9747439,9823872,3285448,9749571,3935149,2332985,5430394,252149,3335464,9333300,1598462,6710946,9689173,5828616,65533,1486336,1012934,6492951,4401782,1028892,2028884,5708200,511533,4627388,323781,6336456,6244378,6540815,750551,6049636,7461147,497991,5873509,746596,247562,9808658,3079581,5677956,60808,6415045,5011257,1659270,3125991,4700430,7487887,3191525,6186767,8500821,9684477,588549,9529713,1713362,6296750,41246,6340750,6620531,6377703,2585129,3161346,7128254,8634765,622494,7626245,4508275,1369090,7873807,4316934,4448671,3551764,4377742,863716,8563021,6037012,3989708,3263452,3524899,7181234,9450219,2025721,6865711,38769,1555434,8579073,6335519,1596681,4919824,2956051,7974384,7504953,6117398,5102638,6139719,6739892,2728884,647995,8108983,602692,4964929,2557654,4154456,9342671,3421370,2717477,5379684,7411079,5980930,8904584,4592313,5431149,930305,1458025,5469918,2485739,37099,1805438,4082420,4956923,4761490,2056805,2461877,878888,7159444,8601597,7618781,9888328,9249592,5727764,491020,4214521,8285419,4645476,3557193,1706789,7362954,8936877,9117869,3343884,7841461,3710183,8775034,8771766,5168208,4244953,1257506,5205307,6050391,5339926,162231,811881,7396732,2624108,1690770,4556176,1225706,9309552,4444505,475298,5037317,4935525,4689820,3322736,9581002,8247013,5029526,6943957,7183891,4147395,287842,5025352,7857578,9062877,3797119,3025786,3307830,5054625,8231094,9358221,394552,8393325,170103,7791284,1017434,1860874,2347461,2243140,1170427,6791966,2718439,6207744,1727492,7408259,9530480,1308494,5655273,4560006,8252452,2839164,8707402,8540295,7864517,6564980,7603172,1661636,9590767,911002,6716261,7821862,269224,7110814,6215188,439327,4902098,7232622,2300202,7249559,9475763,3470629,4041525,2194203,9678373,5769017,9602463,9208854,7077512,5257736,3768861,5329965,8096900,2476263,3870260,5961417,9041243,1473432,7623054,8632011,2384434,4339315,6453873,2653658,1450129,2669061,3092986,6352228,9901684,5393189,3601788,9377448,8863818,7643314,1571651,8542192,3412332,1174115,7751046,489845,6431851,1519907,5819810,4528752,3996171,9690070,490170,3037415,1163503,8113224,1669426,3547938,2452540,8123300,6201597,3902670,792362,9294584,254898,694046,4687773,3856686,71495,3551591,1500001,1643147,2093784,4912333,2817262,9844831,5402178,9249113,1364739,1221988,3777866,5360910,912059,4268036,8398325,2075563,2381260,67752,5623501,4833801,8191052,1825098,8736471,8983414,1119682,8991370,9677461,5807455,2848057,9748957,9359047,4348058,1392104,1452832,9260391,4209366,1297663,4662569,3458480,2662402,5884558,7236346,8023312,6796617,1504382,6421638,8872180,3885643,6489390,4495682,8719444,4680443,6320781,7455915,3663858,7440464,6447285,3341319,3247920,9295342,3090276,2606967,3643401,4482381,4059799,2903792,8691747,5357462,7566362,2150227,8019865,3450920,9386573,6043178,247538,890956,2464816,9119719,4776599,8954207,3615401,3496044,3634650,9936183,951959,7298508,7376647,7399245,639828,624567,6694588,3730105,3231534,337989,8212486,7291334,3241782,6904234,2648797,808144,9054461,668662,4259065,8441035,6711841,4506603,9331992,9176657,3626322,4108592,8130865,7241724,7604636,1765515,7177907,8556596,9064024,4554554,5955841,9703853,5179121,2650430,3433958,8410656,2988420,1646445,5701991,6230203,8550679,8350788,7038347,7605141,9019451,1297412,6046177,5731292,5804016,5378169,4907950,9430339,9486761,3038815,6672063,7091398,4804331,3849971,5647994,3868355,8404526,1603836,3572209,3583647,4254266,7006168,1994304,7242687,8652613,7696295,3472890,7203293,6047084,511238,4808434,5066536,1808651,854612,797829,7612667,6232781,5705780,7043006,5719543,8744595,3715070,2810941,3548927,7565041,8458935,7417283,5969567,62772,989492,9553215,4317038,7995660,1547520,1559726,6648273,9243816,5032616,3851566,5290900,5543855,8660001,357437,7352506,9514613,1155266,4965173,5747395,6861046,2008180,1466938,5605642,5723251,4277880,9154569,3288292,2736815,6571852,9257860,2799587,7561345,8811076,7116626,5557005,358596,8676353,2205279,9602412,3708970,6056845,4893313,9252825,4716847,5250751,6605331,4231461,6406017,1570505,9978856,3267064,3578686,1445794,8872707,9301937,5723675,8027277,2590230,8460490,4599130,1848090,1260078,2160475,659167,8376705,7717480,1017763,7053059,9922759,620176,762029,5979605,5513490,14854,696453,764241,6620186,4927914,7170258,8190692,4906770,437323,1769378,6352565,9310031,1071316,2076240,7337308,3661546,536731,1936438,5509637,1796810,4096914,6168804,173516,1814394,7186568,7226575,1737154,7806744,7988604,7716759,3320234,8003459,8413212,4084475,4623645,3341126,1254734,2814338,8247897,1692058,4583716,4600462,1002090,5655033,6676703,8339399,9316579,7213435,275837,4826216,9010245,4372752,995021,9183761,6187146,8181590,6410336,7924301,5988334,4398940,5641061,9308569,2402399,4054273,3393045,7026045,7395400,4647780,9840383,5643298,6339839,4424100,243761,7341929,79133,6920464,5681328,9395713,4133899,5957166,4221930,3144144,329918,5216952,2327906,6517065,3398542,8738242,4441367,9386876,3137183,82428,8695446,5539583,4136701,2088492,2565629,1532102,6736273,2406012,7175400,3076112,6830113,7419161,418042,6909247,4339626,6099370,6304960,8473525,2056537,526891,1617670,2386456,5743843,3945577,8903522,9142385,2683819,3344889,8529262,5821003,3427317,7224708,1360586,7564019,9313201,3926215,9096122,6049474,6332228,6271522,9125586,3162342,3690684,9543629,71589,8030310,5643000,6376550,6503836,7699537,6903442,8121507,85994,2647285,2067085,8989516,1789671,4750904,2334406,318933,571908,5761723,7543642,1932495,3325743,6856843,5858710,2421865,2906318,2190939,8693388,2031904,5353281,2384072,1575534,5424871,414383,7218534,1801422,6918220,4918071,8704864,5039728,5004066,1352150,7106813,3993582,3141821,1857718,6327988,3460754,2429626,2089712,1004396,4362121,5415455,7861240,220832,7837321,767558,2411772,6530709,2799463,7765054,8914781,4374997,3189926,9329165,1593531,4991348,6247386,6511603,3696213,1287114,1515669,5048363,8393928,5509252,8190184,251646,1837241,1650939,2681273,3926954,2655336,7043395,9342410,516577,7264228,7179731,1284135,9676000,3710440,4083599,7441055,2625222,8458597,630981,1954388,52129,5622330,8201774,6563732,9318543,9488889,8079402,4366907,7882817,3588655,2557092,8134463,5425897,4208032,815737,9352851,6863368,7859132,8695261,7379945,5123360,5874993,8664081,4799361,9585433,2747680,2240416,2210656,1206277,2871398,4165044,1258407,8493728,2366819,7822139,7812272,1855708,5901542,2179180,9738526,9490198,4736273,7872990,4916095,8944305,8688727,4268947,5807673,6547859,2964208,3187619,1671219,8839202,1851700,6470581,8424636,4599381,8710997,635292,5805659,1582395,4800337,7064066,76124,7167157,4886206,7888397,9022866,787749,67577,8761392,277947,4803850,6634382,5194043,3748156,5323109,9462990,9555830,1870969,2427199,2743449,3542188,1266401,4595150,12769,9691038,9194532,8723767,326330,5000191,306163,5126668,2064258,382288,2293826,6950465,8270685,1316692,7738215,8338263,78085,8016163,3142113,6712467,3210206,6890270,2035577,2673197,6446100,3906546,5100396,9189549,7448735,6366798,3784700,7461505,6057836,2979232,6185272,6384167,7979424,6491436,1510836,43683,6873724,3804662,6994148,5144409,5121355,4732363,3482672,5199440,2748526,6624786,1911907,5958733,3515056,3947485,8631930,9961157,7854031,3732327,9150706,5302766,99126,2935407,2764272,6156962,5914639,8949544,2541130,3894064,5440981,4051966,3937747,2314705,7856629,931896,7459114,2977984,5664260,941787,8177424,8412786,7566574,89332,4371520,1081631,4036818,3003451,1042788,1890849,6735778,193495,7193616,6834904,3128902,9957888,2991867,9043542,8907433,5532998,2937606,4348414,9584964,6875353,6663120,7441594,7807250,4122235,419578,3471510,5064022,8597003,1884297,2630597,8686335,6255817,3712229,2723154,9259268,4755017,4614003,5995047,4948513,1807620,2829952,8077416,1765509,5821820,7120958,672943,1354818,58564,5021358,939783,6933918,1684478,8381377,4741168,5806713,8800956,8212678,870736,7397959,96975,3501333,6084295,6352793,7213563,8807449,5612062,1968580,3421453,1607110,6917094,5229073,4437062,4994510,6994583,258883,2115468,7667526,1613701,2174033,2688884,2553485,9107952,4373362,934862,3849121,180076,9735818,2061800,1050812,7133778,2158776,4552146,3218073,8511569,1765709,2025522,4123631,3734290,5446976,5730741,651384,676050,167804,5645894,7670633,426687,7761362,5338159,2040389,9935396,8027044,4593874,9043348,2400406,5528736,2892469,2580482,5264555,4954270,3631295,2398333,7113046,8183441,5616407,5624615,9949151,7641930,9748247,3683441,3088906,5478989,4334825,3764956,5646794,9980719,1435589,6073481,7742082,6773749,8113871,7677479,4800793,2707745,6720828,7201200,8236482,9613298,9781683,3501038,4567568,3412979,5899371,1680614,1596420,1515778,7305230,1545572,9157709,7053477,5229013,2246615,2532467,9563839,6011572,8179261,9544559,7447162,4252743,7286641,4220911,2366614,4964121,9021705,5074360,1684949,6222906,3310842,1298247,6004590,6811880,5865815,9417569,2711252,7546429,1013990,4227031,4851659,2559562,3384740,1905137,7788575,5631356,4437604,7352414,1642928,2616866,6896973,9090090,6869609,4183615,3311002,9236224,9147736,2332708,4310584,832685,8555614,7621427,2130933,4560204,4433308,7996748,3977773,7144560,5543178,4991763,1371591,394838,7551325,4756332,2299976,5339901,387688,6737581,2692315,2030617,9354447,9589289,1120708,6224057,3772904,4431711,5460281,2920641,6764419,9770866,3753327,5320033,7392293,5884260,9880238,1825601,3881008,3858012,8970162,9424187,8849775,341754,9819025,6401101,5098086,2119002,1741002,5485775,8856583,4433318,7516393,8211030,4022607,8637101,4435088,7795512,3068812,9895369,716153,9833232,9666236,4469480,5153265,7058530,353740,5033504,8884132,4234749,8891516,7854294,3658937,7741292,8196049,3477963,4142393,3294135,5596965,5883396,8779911,4453548,316715,6296304,2664579,4339323,4933406,7099667,2134835,8002219,6995037,2850989,7835451,6661274,7320469,2988717,3719804,7674210,8022221,2603936,1908960,6913737,458231,5567897,4655029,8654280,9045860,8797423,1948416,4642826,4680820,728328,9096374,4997535,7024632,1760954,9336858,1958039,8860621,1471694,9960259,5855659,4322683,7795710,2516933,1643152,784427,6236737,9317363,8806649,8840674,1226323,5720387,9298906,6794221,375416,7953187,5840082,9172840,9901603,482908,3853660,629931,9579283,8851196,7654564,1340237,8188055,9612604,200859,9659749,9572863,6056518,3982432,7368574,8573452,5625585,8153001,4810190,4942948,6959651,3650864,6169272,2680038,2949771,2963493,3055455,902958,8803576,2228295,804562,9286484,6081956,1434494,8865768,4933153,9089058,206006,3121208,8701663,406865,2780957,8274526,6463384,6763390,5643100,5036836,2388975,3796102,9847026,7331924,755754,3497891,3501197,3435792,6447662,6464691,6491247,7350621,5268267,8719543,8155183,4554752,4801500,9589677,3420520,9734653,8678736,3626526,2855861,7380399,4033392,5636819,5654926,496777,2400209,1298027,5533614,4789185,5094129,5380640,2121110,5849883,8878532,5622308,9285676,5326195,2086999,5776923,2676816,7355267,4496467,832000,1910019,9297967,421677,5330539,9032620,9100414,8957066,1888482,6480813,2990458,7525301,2135739,3487236,9925510,3433766,9020850,4714696,8527896,4401491,6835807,4377780,3280023,2458115,3663456,8606219,4545114,9440380,1283036,1900382,3936847,2115036,3810401,3234815,2536714,9140941,2267435,1637128,8098008,4155917,8117942,1088467,1681218,253682,4575703,1606729,3687449,3596553,6321426,2215345,7998044,3157233,6593126,1278068,5615348,256583,9884287,160463,9696963,1167323,2060845,3633811,3282359,5871246,6868626,5819073,5012188,9136061,7456202,3110196,3291979,5574144,4198663,4973198,5827826,8774366,6579928,9515276,2370919,2901354,1730622,368964,6058587,8323748,1647032,1673936,8580331,1531319,1834399,8277294,2698642,3895244,1911106,5981002,9766491,8779732,1800076,4778680,7915794,9256278,7888876,1207773,4830423,2087540,6180972,658250,861906,2760900,173526,3232826,5662254,1904148,3601790,1720842,227897,5248823,3394779,8808228,6780142,5229178,7085523,9478785,9124423,8996629,5459787,8890915,7776361,7259864,3669595,5692156,6516143,1558472,6899929,1346567,3646012,3080901,2004817,4507918,5841802,2178344,7740745,1504057,4082492,1342536,3224899,4310390,6591359,6619679,3118618,3371502,1848857,204141,2850287,973281,9200771,8310075,9864196,6977133,5569940,3533792,2669289,2086083,5092264,9569219,3432650,8738276,2650120,5437468,3246195,8491923,7615812,986941,9995980,1698305,2329477,3220880,6008695,8920837,9840559,9127314,2292339,1689417,9331456,5142627,2662698,8532227,3452703,2526895,5509361,9022643,6060687,8178650,1108727,1152951,7747869,4541378,9891228,397990,9978846,3137424,8889913,7594659,4124365,8885894,9292965,6453842,2106774,5301661,5374680,1947334,4428975,7667019,3636751,3760431,2809647,6299449,2292659,6262350,8826345,7802020,5284994,4887032,5980671,6393722,6039984,3728540,935100,5931213,4126531,913947,9068637,3016445,8508606,3193002,1902339,7801572,9646845,4009113,3103233,5021525,5956447,7532209,2688545,9593199,1292641,5498193,5892648,3585301,1760544,4718994,1387322,7045538,9606026,7367993,3439260,5646011,1096534,4374361,1577225,5223065,5288308,645862,8239510,3796915,3838865,141850,1598487,3485711,4150963,4701721,8507236,107411,2233930,1195782,9700610,3526572,6693976,5593259,7111873,8454520,312253,8499195,5500059,9918280,5867188,8939320,5564292,6963722,3313681,7141517,2186788,8601989,7787380,426299,2398904,1626245,568149,3997392,5111956,4719113,8699113,3619193,4826525,933044,4814976,4527136,4459616,1508952,120395,1571489,9963473,432649,70685,5463532,350930,5937873,4402852,5915223,2901596,7716534,3056740,5088385,6318523,844121,5514685,8717428,2470367,6082835,2714821,7582323,801948,1413935,1201517,5628473,2346980,6016494,155609,6806596,7525447,276005,8378086,7488920,708655,8448772,2952453,1059585,4386645,7355305,6974808,7288242,5071840,31549,2376628,1390363,875670,7891313,107792,3346038,3974148,2822614,928362,4776097,4236549,2129879,404571,6583529,8146374,560181,3390126,5671821,836186,1768213,3160742,1544842,216985,6113195,2604427,4603631,3468501,9579236,1891874,8540341,9610786,4268502,9930705,486457,2159816,38498,3832495,6133964,2861112,4760857,910061,7097662,6890737,1314632,3681191,5037111,1874813,7071318,708933,2711000,8839532,3869675,4255842,9056518,9982870,6860270,3660149,3451372,6439506,5552024,1991713,6050293,9820526,1922418,6536750,1980342,1960917,369245,8114307,4822029,5130102,9024368,1919691,2020839,339001,5600883,7057951,2213815,2672202,7766884,4924815,1511734,1636559,9180658,568252,1619430,6040928,4228402,5070802,2480435,9780426,7062515,8530728,9600952,8984934,5067479,1581295,945851,5436724,9695602,5767881,566827,8719971,7687572,2587667,9058973,3288456,9645618,1272788,5960658,7412502,6197604,7472393,9049062,5378262,8040645,668492,1419191,2269047,5739294,3899627,2049474,2801810,2430356,1650427,1786745,7497835,3231722,2732597,2934560,2927325,8500478,3501388,1647296,6188051,6089055,706269,9476507,5734674,1979058,5437166,3147177,8176662,2909559,2196240,3554925,950204,2864732,4974117,3219252,8604027,8873744,5268727,1405838,1304100,6919154,3192583,8801936,150876,5925180,1736497,3078201,4425659,5237885,4725498,613710,1326941,5431768,90218,7061616,7410826,5527384,208793,5587489,8436944,2405034,9142414,9387149,5269766,4116531,2606402,3873794,2990276,7875129,5279632,4294377,4794283,8472216,3096313,4945160,4397397,4832810,8023362,8823056,70696,2748860,9436767,1397637,8180628,9526985,8459254,5591455,5054370,8668047,1178944,3491315,1073081,321359,2878464,6342848,4437891,5484866,216643,7428168,3359995,5496276,1722545,8154278,3968492,4818859,3099438,8365890,9651670,1122800,7188946,9722366,3871661,6625714,1120004,2052290,6152700,9579258,7643746,1207071,8247306,8822690,4698386,9320388,9144050,7576850,5663237,3581942,3061716,5879880,1010110,6421712,1376156,2732656,4575990,5344649,7551515,7675429,3710539,7203185,8798230,899486,6925552,2669892,7525201,8045557,4722182,3677901,7624815,2365928,4884973,5872122,1188619,9583359,5192510,332670,7160209,855748,3914613,221926,6735628,4924723,6643638,8111785,7657379,1219629,3456435,5208895,8895059,7166975,2412081,7693290,8066462,9337633,363182,5591664,7383190,5085365,9269565,5008006,7451294,4154538,880128,8639914,3737898,6072639,8972584,898107,6928387,2887197,1120034,3664016,7811921,7763673,1775802,5469301,8983302,5232238,678196,7878362,2399214,3090277,5571652,465676,2427911,5934835,6057340,9811102,1020200,5326906,4819108,8471494,9481445,5699237,7111408,3219343,1771876,6083993,4117451,8700264,8971191,5237485,2364281,6783112,3001158,4140083,2252414,1984461,9372322,2930610,9862823,1771536,6020888,5434476,2237213,8448799,1369311,8294553,8259901,2389512,3621460,3079010,861006,3102906,8778247,7972415,6322249,550124,4056409,439701,9250388,3027600,5677187,1614669,9810713,8678346,5754753,2063127,662808,5127075,4993738,525631,6898611,1014626,5960108,9135824,9463426,7329419,7430378,7723328,9718931,1051839,802339,579938,4154745,9580586,8552354,476995,130710,2608763,916696,9381099,5636364,6593884,995769,5447078,5272230,6750522,7510206,5935038,1877597,2503944,6460670,8776209,3518571,2420778,7912034,2981998,9750198,5342413,705327,9469129,6394252,1507666,49068,548998,1088253,8601423,1025993,1218964,1210187,1942690,600063,6846551,8536574,1595832,2293630,3808805,8346355,9803836,9743844,223953,2307781,6204514,9000162,5826353,8625293,6912197,8808352,8375491,2254611,9513679,7844621,8648864,1021346,7893690,9197862,2109599,6495113,223856,3328563,7705300,2166547,3928627,4551852,703122,5524460,6845482,4511927,3870815,6649319,4255771,4094768,8957101,460286,3094931,4783454,9085579,7128,3591807,7461070,2261739,3105486,5305692,910603,4126832,3199382,108466,6236432,9694495,332322,9564996,7399795,2498869,3493623,1951647,3201991,9018083,8797130,7713919,2888898,5446449,1969691,6983667,4403550,2429977,78598,9187005,1515556,85726,2778812,8976627,2347466,5884299,4282320,3258070,11132,7481702,3366536,6247565,7176198,3698859,5812561,4575993,6197729,9306185,6527641,9399721,8324269,5324771,7113640,1213168,771221,9083332,8196835,5174772,1513309,8275433,4361778,3028866,8361160,7140590,2005494,708626,3024890,6287814,3966697,3036022,3769517,7333234,9283587,945715,1032093,5096149,5521709,7229822,4402334,2049350,6629544,2726604,7374122,3743185,3939772,8145343,2826517,2136607,3320116,4339827,412041,7681894,7368693,8773201,4822485,9374188,9481828,7847375,5662003,3448525,883398,9431520,781759,166986,377235,1813853,5263136,5898945,9043676,9665471,7948295,5673220,2392075,5322417,9416406,6331847,3467761,2242923,8468455,6787877,6582750,8880496,4469771,3951444,7653698,9292257,3325633,7135527,7139632,8987636,584053,8023031,8419156,1365813,8190018,8796392,3179666,3453154,4695337,2223343,3118625,2643633,7896564,5510700,7966051,7312970,1842548,1433812,9555894,311003,8221690,6138645,9191500,2691462,90089,6845199,1983719,3415722,3980726,9123352,2403358,4564779,7146383,822515,5930593,5336401,9618907,9110259,8789555,4314245,1333603,1908181,6957878,9230167,7418881,4923929,6543137,9261429,6357742,6099032,9572433,4579432,2237677,8763933,7270894,2327766,5609132,9254613,5743489,9589859,8377965,8146848,4154639,5524349,8969363,85232,860751,8588271,9195492,9650307,2902516,529095,1558488,9860395,9759262,8977370,4784324,6302400,8238799,1142067,2401432,7811233,5721499,4639109,6575166,2992393,6966876,2184299,2247007,2710366,1774159,624973,857214,5928798,6149323,9826578,6014030,7010074,8414849,5209522,6660381,1317366,5738617,8218870,1177761,5497880,7196240,5962086,1800281,5435040,7104153,4201714,3246273,2825653,8840824,9821440,5818047,5807700,2005740,8065055,8518067,3779899,8690028,9375281,9708697,4839352,9201859,5722728,1849426,7616709,932250,8509808,8934076,6670868,6728679,111838,2168749,3924919,6073924,3969030,9359960,3178078,8170744,2606233,6003732,7011568,2427674,1821779,2819269,4433414,9886834,1337336,8213314,8576863,712618,7922012,3416215,9914478,3644740,5265642,7531188,4576991,3775451,6465264,1247860,504130,6577102,3416609,4429049,2651027,7385640,3789009,5829105,5556385,6395243,1832838,2567953,8822917,3654617,5387223,3256332,3541452,6724560,1469646,2118316,7437179,9391658,5534532,7351657,3036399,800174,4882845,7613390,4575625,1348110,8861250,5079756,7925212,2277860,9508805,576239,9663500,3297815,6405345,5219885,9693059,8238184,7787839,8515976,1892801,3175063,1772309,5434254,9899623,3241955,7552570,7336802,2633614,3087102,4688460,5670013,3887277,9571306,3283403,8462902,919416,2144654,3542658,8844629,4422514,3051464,9420869,4086015,6349280,5826215,9305900,6042339,4064399,7093739,4558316,5957201,268803,6330626,1391455,168426,9572581,8944026,7505229,2206195,2031128,2193690,7876209,5918405,1764997,1159613,4381308,2684413,3304267,7923967,1529043,7726782,975432,949913,1812797,7324712,6776128,1118698,3367052,840527,8212438,7925369,6797729,8481241,4255995,8189184,8649667,3828577,7133210,6154897,6034773,9164339,8348588,3910982,5082744,113585,5070595,9464053,2797999,8374863,7388020,4327042,6101645,8363453,5276955,7914442,5688166,2053084,9033140,9055219,2893611,7245578,6980588,9691341,5726820,1236584,7880525,4376487,5065161,5013736,531385,1099934,4178075,8879973,5010917,9260820,8993558,81512,8724874,1791557,8456375,6112895,6118600,4558021,4476348,1395556,2472464,164514,3448640,1505604,9219733,6342252,8751183,6200322,6033593,4478004,7436906,3914118,8854492,2502068,8927855,9385877,3602003,3105931,8265851,8612920,2366751,7259410,8694433,1091625,9050968,7150808,7204520,5169568,1708830,1680869,6565124,4181294,1845383,13764,5686899,1065117,6356017,4438083,7265439,2389610,8916087,4702346,6303729,7770579,7204414,5231584,7156456,806417,8337515,5422308,9419338,704267,2681718,8113771,1795893,1732686,5264580,9000413,6902255,6973410,681283,3467379,1154704,2526666,3481144,6841603,3591783,9837161,1279686,857223,2226771,195774,5559569,8530501,7966353,2763983,3762085,5122810,3570401,2099601,545118,2989740,2803868,3226836,1103511,4599762,4959523,6368092,3600176,1861778,3341502,4281459,5329158,4496207,6808125,8810302,1337811,399909,8647464,2617498,1257133,874236,2813272,6816702,9404737,779625,9580686,3166823,5902435,3151088,5266424,6447554,6140828,8070293,9674390,7244339,2670055,4633913,3612432,6270231,6495692,6953934,551690,1824850,1450142,7359816,635152,2787953,7759726,9282617,5405452,9016859,156853,8218724,5833562,9561590,8998350,5414248,2728414,4900786,8565336,7994838,1348340,4706164,6065132,1022731,1950504,8735188,5656645,5562936,5005419,2152337,2516871,5557110,3977188,3967014,2916927,4612340,6754968,676653,3894958,2160420,9693513,4051811,379145,5527075,3613402,9377496,941324,6341816,4278282,9506660,4336655,5626623,4212825,401788,6649355,6163330,9136976,2306000,1726267,4142396,4458338,4243138,9699506,8435526,8210152,2616434,3047867,4965121,3293088,6942825,7125541,2986601,994637,7504686,8513677,4608040,6882182,9455001,949856,1160465,8961662,5286512,6787089,3174488,5688300,3436444,9337818,4825277,5742445,1064085,8967673,200783,5307224,8667180,8636310,3517377,1283614,1684178,8482498,4576702,8627004,5608040,7563304,9621641,3112726,6076981,4229681,9994909,5531983,5179538,1155375,4493645,466051,7942464,7668133,6154351,1378908,7005951,979628,7121354,8070037,9947302,7322138,3377262,8614482,5958448,6894640,9898096,7642627,5377138,4474799,6269631,985179,2038103,5891273,4097906,8115085,120954,4092815,3647068,5300493,5248191,8140714,5766544,3190655,5808847,1920896,4569564,2814799,2900525,1690918,884837,2847827,9013056,4262099,1462309,4971505,1156740,1360406,2614133,6533879,5835206,8883764,7519058,7873310,4775037,1616964,5988396,4895992,5709780,9635464,196486,957971,7776179,5963031,4148627,3585026,7883927,8718191,6399826,784453,409110,7284663,3632280,9422167,1546763,5094590,4393673,2703503,6454997,7007806,9237383,2290203,5891570,6756441,163514,666608,8373405,6151910,5562601,4083186,5787375,5759087,5041157,3563554,1722118,9189784,7148580,9606046,7907976,3548407,390499,8317086,833070,4022780,7739253,2379834,9117371,2132927,5083338,5572369,9140733,4320721,7862573,5032303,1077162,8026087,5698912,9450568,4177998,1261513,3533754,9965373,7020601,8574912,3528927,8742719,7764696,677508,8348766,5672672,4225915,8739266,3989759,5058986,2762047,1729013,7438821,1879418,3861940,2522159,7451788,3002673,6842881,5314361,8034977,7920044,3340449,3733889,7370613,7518447,4995403,904367,7483820,2016004,9479280,1012747,758724,7243976,1690256,9107490,2916649,5916171,7846756,6906408,975158,608803,8635421,8413979,2488222,2497361,936139,9940010,5500035,7779020,5254371,3535012,5699065,8594820,7268902,3069678,6113267,2264305,3974046,3597088,4280309,3453326,4609835,5039033,697303,6300092,4146524,3613952,2216263,1993281,520361,3191422,2602085,9155783,1605401,5090307,1653145,2541541,5030318,7153180,320561,284690,688193,6019627,8879511,7957095,9089305,4992779,221400,3063351,8589867,4501710,6516678,3199703,9540744,7213981,9499795,3687269,827934,1716059,5680550,1348296,4907481,8282635,504079,6512882,3372943,2157225,9054423,8403261,9310406,9374985,8687951,9998599,5394612,7567462,7955694,4483918,2560242,8177095,7547269,1150109,2678805,4063948,4349812,2219550,1277930,3849608,5906819,2105864,5565667,1587369,3454161,473148,9870005,3958241,6986031,3242948,6115466,6040455,1646210,5425872,5415440,334162,5424471,810053,7901625,3380166,5293971,461867,1557261,2841241,1611976,4236067,6905190,5961789,6455618,8183120,9811398,2362437,288985,5377065,3949807,3743146,5850214,3819812,7701387,2836245,7062761,3816854,8876700,8708971,9242726,4292141,9043133,4667198,5102195,6944758,8047365,396166,7406625,9604627,3237408,9018602,3840695,142598,4980392,296313,8325718,4791790,2658750,8614704,168855,6608558,2357850,6019069,428370,59238,8855315,7491132,3876092,7732015,6200103,3118819,2024157,5243237,7786018,7126352,2187995,5833383,7522519,9594621,5438011,759928,8613224,9278706,902526,3593616,9575019,9228245,8385406,2233770,7842949,8554262,8842328,200800,4573332,9270699,260038,3428647,6761831,4136131,1160663,2961935,7254951,3184821,8205172,5040969,311174,393168,874353,7833693,9987790,6312364,8593622,8601014,5591071,9496148,2194631,5166091,8724394,580038,7399861,6567344,9134301,6242190,6768145,3707633,5512890,7028184,7136281,2274722,1164315,8296945,5236657,8419266,1481766,3441830,3460236,1792940,3834999,4334589,9626634,3822790,646954,8220256,2423805,6238025,7716405,4618436,1404116,6440800,5198475,8803978,3008145,4332776,5046169,9776290,8040410,559059,6804474,5176691,2833781,7968790,3473637,8070439,6388056,4955403,1512269,9848292,6748344,5347269,4182882,6374979,9170059,4829836,4595236,1593864,1067862,2311642,6212301,2471979,8752442,1410776,1275957,1760587,5743552,6322126,1536878,3783962,6881185,8341352,8960654,9714967,6310142,2434291,7785406,2698199,7389695,9297676,2546492,4138039,4644945,6729374,513019,3815005,1559211,5108255,5408869,2627073,7419898,1621171,5099052,6172340,3031947,6375009,7932928,8775499,2697136,9469806,2559462,9578322,7811159,1520116,9293289,4121302,3954408,7078696,6819501,1344103,6376372,9365993,5482143,1021318,6095367,5995162,4836323,7654578,1103418,245193,281652,8523316,1866364,5380704,4695657,4898312,1755714,2628585,3673812,4452851,2098392,6233274,4031173,9909551,7753391,3324463,4030854,1707799,403159,850355,3051902,6779532,216348,8534045,7800850,6311716,4529208,2637174,3966295,5632626,2882368,4247947,4155943,4748733,9628652,8851601,9647045,1384367,1480186,3320857,5837219,3578579,9554132,9868392,3488131,7307523,3192856,7518985,9015322,3596015,8369341,2067224,375547,8585689,601270,8176398,4897406,5130478,813572,8863702,763105,3695941,3111650,4919049,8444674,2740303,3770650,8091719,4124670,5250837,1412577,9961890,8829416,966709,9830283,2317548,8274232,3023139,9836533,7289555,6619154,8205874,9356780,6994702,6791564,9958050,5171100,1688971,5088529,5984673,552673,5851635,9680614,3664323,770684,8125288,6404626,4541334,6217008,529297,9792172,7629585,491187,8621588,8596295,321470,939137,6870527,3344609,775671,4160082,9963764,8981546,3516863,6958467,5773110,3474913,2129568,7462082,8563443,8114241,8014755,4415078,7794856,1679079,5185762,5920144,8083705,9727097,2137153,8613003,9519269,9766739,9104191,8140858,8363034,9425661,9079995,5233561,2770271,9855666,9393644,2734036,8837212,2910507,9692503,4610323,6385421,1822071,2072405,4948864,9936313,87161,9363942,7731169,1766240,4549705,3651314,9849946,4276802,5788467,8462950,3796072,5555206,7567141,1936930,3918241,6992803,1016926,9151803,9763074,872593,8545448,2497111,9709806,1455956,2189614,4320130,7841377,4011686,6392536,2790242,3947999,6479697,2154184,1679169,8245938,6703889,5330483,8095885,980692,1118951,6558835,4776764,6674158,4125976,6713694,592399,1118780,7730621,9744203,881854,8603214,8289651,3378966,8313020,9745607,5568580,2633150,7586984,9580267,9025686,377226,3528267,5505384,2531411,5207436,3751322,9235301,537920,1847208,215993,1656872,8406043,4992758,8331030,2532020,1706453,8923430,3650800,9437074,8667633,4532655,8040289,6957285,7911621,6353310,6702892,3480202,8986460,4289876,3060469,8012147,4667103,6588737,3517532,7198515,1796174,7268855,6433816,2334095,9116063,6649810,3990967,7522107,1642568,2321998,54127,3349022,1245429,3704928,2786096,9913063,8237583,826385,6870348,6149205,7179695,3573240,9629407,6166156,7863117,2689877,4178304,2530221,9278615,7695837,9728736,1074789,4964692,6162553,3408884,4080756,2812363,7399851,1602863,4454932,9721850,1656990,7803955,967279,5361919,590051,880342,3599503,1416437,7750690,9748708,8596133,1323930,9378116,4762290,9187047,2067993,8940595,1717269,1346608,6636432,1446005,2421398,1601125,7608558,5830282,5681881,420922,3230134,7284744,4875855,2951984,8941735,2679811,3919264,4303655,3269863,4799606,7903158,4686300,2550296,7651866,3282434,3874227,7029982,8044725,3061275,9097976,6985321,4778544,444585,3621754,6224550,2865983,5222880,3833108,8696265,904761,4254031,1926400,8189506,9129887,4878385,7131242,1809698,8797649,1434897,5079561,3597255,9338055,9765862,6147552,6989922,3048297,21779,4019905,1093023,3083054,3117881,8078344,7861599,3562466,1700099,4086149,6428449,6922979,7919258,5124715,7827741,2173290,7051116,6017247,1303178,1929501,3148490,3112876,727150,4583388,8192438,4324405,3921444,7958301,471957,911366,1006598,493737,4931272,2099622,3576792,8049153,177967,1438391,1611620,1878066,5524541,8040070,8801046,3443799,3164785,6628787,5617090,215901,2646035,6920268,2145403,5794525,33145,2872553,377914,8225583,7196959,4299358,6183884,7668917,5210725,7190483,8162654,141997,9290105,1739447,8191150,9468072,3177838,9802770,1346139,8702380,7842840,147185,2146180,1007626,6775973,7763270,1223528,9422008,4683539,3368931,5216534,4716684,6241485,5594448,2942267,3438444,9893806,9126152,1107361,5104531,6316636,9270016,5246529,5606741,1009463,3437679,5074814,4187302,3240450,6420954,2889682,1083291,6568140,5035863,2090918,3344113,2799133,3314446,2766121,7482672,6683378,7982656,2199357,2924864,3577104,5141624,6363308,3470911,4267777,7470670,8575443,584413,6740687,3821972,6191155,7750150,7259652,1265970,1937453,500103,7686925,4827136,1583394,4255065,9862999,3674312,7599178,2662133,6988759,365300,144805,3672138,8347957,2344162,6597002,1925061,7485787,2960311,5395973,1753565,430981,3971417,2337978,7171669,7793389,8529134,4921819,5053042,9795105,6859273,5553145,7482030,1686409,7136540,1737095,1549408,810853,9336274,4211541,7799613,9701575,4356347,1471751,8049532,6700510,8068753,9974594,4186298,1029064,5370567,5939863,1460046,9341984,8277842,8631715,7135374,6806976,3553535,2188417,6602082,412808,7741562,4084112,2099218,4878103,5821207,3648626,5688956,5157482,7860168,3488569,4859057,2216515,4960321,2908589,8917025,3029075,2883184,3103324,4058140,8253751,9043187,5518187,7595736,7321029,4149902,4731111,4128006,7703438,6919528,730088,8116247,4661091,4814200,215465,9539194,635408,3864092,5228150,5792891,1724260,8716720,651948,3940776,3677042,3560538,2857802,6706117,6443723,5961126,764257,4697475,5004313,6282444,2293211,2325343,432347,7024323,6453350,8135786,3943851,7183438,6252033,8604942,1997639,6467499,8144136,2633048,331592,3372287,8425940,2055852,2089008,9077888,5996629,5766050,2638427,8854431,2472167,9082151,4815557,3236425,3779626,9819871,9518869,6072837,2145215,9951217,3097160,8598565,8087003,7041012,5782004,4339037,5645954,7779643,806536,3790091,412692,1138129,7162378,8838632,3193981,9251387,7916521,9190611,5017438,554949,8045042,7489605,9637100,2860600,726031,3416726,2680472,244901,9489564,4825687,196118,2586725,3424252,8283122,9627737,9206257,2622159,5273692,6985901,3428696,9063783,7398593,4566825,6226162,6237226,7760807,5477550,4153748,6951418,494988,4708697,4996461,7984594,4345798,7857062,8710625,7762525,537534,8955526,7252090,5363222,9151645,9838815,8787475,7434767,9466553,7993732,56927,4740245,4979633,3485623,3804029,2378227,8052449,30192,8615453,5813256,5507742,2769202,2764675,6002730,7477900,7761137,3987324,1823698,5618199,2697950,9586224,6155734,1653477,6838314,1518956,805122,6677129,306432,8239890,6143683,8300164,8296818,883928,3279798,1782442,4687958,5658025,9834891,4718150,4273479,5648148,225892,7042681,8412824,6228623,4520582,6173961,215947,6344281,1792161,2913897,5930505,7947895,4567375,2768819,9466852,5372497,9445949,9773284,3612388,5589632,8073449,1909207,6473561,1353248,3691649,1161519,7011273,3526540,5879669,1284753,9174689,6105562,8327435,7587513,2334185,2848017,3761475,2550133,9192298,5553636,5464031,5122804,3501532,31406,7891624,2968385,5403904,7337573,2741670,9016293,2927206,815120,925500,9400768,2168368,4617149,562288,9179641,8143690,6441958,464395,7318380,2547520,8791830,4905893,4881706,1639847,8667369,7431839,832146,4221006,2895871,5954950,7722538,2927277,3846574,690924,8331182,1184148,3432594,7347475,4111354,4247714,8272976,3512123,6416082,2890125,4074411,5595724,1033816,516369,6060119,8352196,3063889,4851949,3258090,7945596,6491797,1925459,5377435,7323943,6146465,8273306,3278893,3869004,1200584,7125468,4559928,9531766,8309616,7992522,6879242,2420970,2240237,5152218,5933094,8656319,8042344,7505,4252043,9076160,523874,312163,7428356,3587764,5164112,686446,1533360,1655909,2611906,6910795,8979853,8758371,5184102,2258746,2627376,6384687,9384214,7187304,5916453,7693831,5179827,2795696,114802,7420065,7947914,6047896,6076384,5990258,6055401,328428,5066419,6579275,640591,2494775,167039,5804704,3181222,1700400,7460614,5793128,8611195,6440467,4551500,3795298,8699214,7178876,179985,8083429,4366181,6096439,5777260,9546009,8892135,5892062,6966075,6840050,1939958,3042460,2830309,7995360,3370889,7896728,4574636,4011481,391504,4741675,9816185,3572726,6442075,7276799,9365855,5053271,3717267,3917355,8848570,2416482,1096232,9028555,499911,5462414,5124995,6277172,5008424,4017131,2169234,1974499,857182,4109193,5016959,3687491,2104554,8387848,1584219,6679190,2399329,1975724,1420866,2215515,5548450,7862942,9492315,4914305,2916213,3209582,8831661,1764784,5626065,9927893,793340,6125976,5390308,5918335,2403148,398732,9935467,4572383,2373232,792649,8681577,7390191,4480140,786131,5778040,6064360,7465322,8177370,8040084,8886188,392885,3588535,6749130,9885201,8502840,9665344,3094783,7334501,1430128,8720848,7262395,2223468,4846825,2652703,8141804,7249974,3051436,8077271,1822358,5424668,8869921,503936,2814859,3350062,1290068,8592900,9414422,8755390,6770270,7454507,7641578,7163156,1043043,4390709,7048357,9545884,4056053,143141,6880386,5486182,8863990,4142781,7709651,3710815,6795485,5851455,960790,9846921,3928727,2783148,5271589,2798648,3287084,8086449,6148710,4577152,6679349,5563133,3332543,3449620,3017641,974122,612776,4060684,5364831,7661133,3606569,9420885,7804274,486955,4907067,6668264,4629736,2616718,379080,1425222,8468174,1339870,1272143,2396902,4123019,6543733,5195551,7410103,4630182,1344262,1987256,1309532,6907396,5319800,4759152,9925037,6293922,5371929,3985722,1658753,3033062,7592291,1079639,837337,8079246,5986706,7505602,2708983,8603425,7884682,4134206,7071600,9224553,5406350,9468502,3347572,1950083,4664054,757676,6580266,6008316,2744933,7889798,2915712,8064733,2648951,2840750,4358655,8020880,6826473,6017409,1053943,4418764,7097048,1891280,2498011,3083755,9396882,5206995,1687181,7281564,9341201,8758781,6506118,4747551,8227284,9853690,6697635,2891339,611366,3277901,8899655,3356299,1167700,1815368,1421033,3816651,4656118,5779689,1837532,1482591,1797098,2891475,5901356,8894147,4782756,8399368,1977903,4179638,3606363,3665084,1461203,2947565,2423866,7967321,7695117,651150,7821011,4392752,3542489,8432378,7670654,2442145,1788678,8838354,4257513,3209711,2655006,8913632,8989400,4492539,396224,786499,7384014,6297581,9680647,2166771,4696949,1658550,6346409,8303313,5323634,7807613,1250878,7747501,5774934,8945996,8398652,3595946,3338749,1941142,2028325,1009403,4383287,3817003,9847758,8640801,7026715,2502765,7554434,6016116,6995304,7950658,6802616,4379319,4248239,6483263,6546090,8945189,8141813,2892500,7248502,3465448,700113,8499381,1212949,6475047,7445377,9611601,70994,784126,1552743,2099319,1793530,5936031,5916323,1641289,4576832,2943039,4144054,2131267,8959155,1139359,81925,5761771,5518678,4330165,2245035,2064769,3275355,386848,4957269,523857,3852297,5657383,9023239,5065246,2132431,6468617,4676848,2203425,7252744,6229591,4302745,9046274,2165623,219069,687563,6742456,3162108,4831618,8873723,2121263,5970977,8955649,7883035,1489656,3285815,128070,3554426,6561170,514919,8511696,7085028,4367216,4169079,6108267,9432462,6301510,2576885,4109311,8504936,9829629,338902,2807682,8875904,2504526,3026751,9563467,9246982,6188859,4395086,8120705,8310123,366064,7076354,6193158,1855720,362170,6321229,5410147,6923340,6836148,3921843,4008368,1203364,8090923,116636,635827,4392434,2693521,4745138,2897370,2523150,5084041,5705053,1399054,7588567,8731804,962522,6835550,4920663,5357608,4956255,3230786,5723673,2032610,9423945,7579393,2394780,5745175,2989540,9318121,2581323,6911384,3326489,3784688,5002307,3443126,4420516,9394741,6136647,9165654,2292112,8659798,4249696,7997165,58853,1838264,6728969,1021375,8673814,1649633,6378984,3630070,4880420,2102657,5662681,4304365,9682051,8057461,49541,2671592,7375583,2630864,9582976,702073,6415553,4585284,4145199,836069,3980025,281847,1724,6272137,8941645,4251420,4269303,9000499,6089684,998272,21875,4763499,2647905,6400860,8393569,7528326,8503518,4056250,1832692,8185569,2113712,1882233,857162,9489295,4513097,440138,191369,928650,5025422,4336568,1764720,9005448,4618415,1766444,5277586,3560061,6017864,9546889,2560560,2107549,545162,2582436,6871049,3193068,8983296,5264619,721394,7486814,9320870,2554086,5672384,1434582,4436319,6529546,923878,8949417,6969685,1115247,9878068,1995108,5451816,1642788,1000556,70232,3409232,6278143,3630293,9427097,5825032,6190854,1534647,6370194,8773290,8405696,9563263,7756587,3670315,284657,5243401,2991185,2838743,915786,4425768,7275063,7445332,5349647,6224480,4415017,6464895,6102548,6410126,1916712,7745336,7410683,1986944,1154569,3688826,5617238,581666,9513859,1808093,2116314,5884054,581384,522011,5447317,8337971,4192327,5731974,3581373,7183513,8570718,4497159,1609282,5845781,1942492,6958929,2070261,6357509,3423825,8172809,2767636,5340538,5918146,178319,7327482,7072716,3867146,2944721,7654383,3381005,4752814,9770697,9265059,5334198,292708,4712376,3672170,4485035,444351,7253544,1668548,9015069,1750703,3277830,4860850,3693195,236760,6931111,50705,3660586,5103921,2818341,9001124,1022068,2996661,6328607,8094784,6863807,9273328,5749167,244812,4026143,5519864,9509872,9360342,5812573,4222248,3032513,297609,4666599,286057,1966158,3681669,2036760,5243988,8542519,5729955,5480749,5473631,5780661,9141336,577553,8599003,8142461,1599621,1595664,4471068,9694406,8459472,3744397,5443573,8704285,7770541,963438,8214157,7130883,6776012,2436406,163396,7073621,7103005,449453,9039779,784675,2486214,4283768,9327194,8216170,9764518,4800825,3996831,8905854,5378379,2595834,7048315,6978000,4191499,1519384,6672407,2650971,5263781,2115980,1355256,3034322,3079419,9569414,165206,9855431,2005820,328602,6929053,9108826,778056,5968833,9893501,3264270,252601,9220695,1480440,17120,4021521,5477272,8922974,9399901,8073107,5971289,6377902,2264606,7490673,3050309,4915578,2754455,5166290,6270835,5788777,8245709,5840249,5953983,8101141,7846070,6282586,5030195,6954896,7060642,999028,6848398,324913,1251630,6069094,1805354,1268750,90615,7282626,191725,9490517,5355734,6163014,5868419,7620341,3653688,8918728,2535919,6408143,4085018,8806755,2196921,2330728,4647005,8150905,431870,2493076,4433492,5462066,9447972,1494135,6461095,6296370,1819048,7712725,2365464,3624403,8981476,2456080,907030,9173201,1946598,6262764,5336216,7815017,3883105,8989905,6733746,6419025,5398049,818765,5225781,7594971,3149493,9872786,5745876,3581364,2365862,179369,9043430,1813835,1673504,5504526,8110206,3492553,3217252,475671,7116956,2198728,2931752,8023986,1371930,4878350,4286750,6708147,2693367,8169856,5698052,9427114,4588881,1096102,245879,9814663,8691073,3395372,9687450,4436950,6976737,2053312,4616319,6020168,3867148,6289824,1524694,1977355,9782377,4741946,2453026,6899334,6940675,5384779,4923320,8312605,263129,9210071,5020753,2956497,7379928,718805,2383611,1968810,1814907,2629490,1783473,505980,6024863,1470923,4942931,3001601,3524236,9559250,9021769,7391385,5849074,546464,9368740,5631452,5288410,1821767,2530786,2229086,7206546,7454107,541692,7469676,6664179,5562445,426173,4044107,6281250,2809785,6012917,8096158,5439276,7796391,8602139,1464140,9267314,3545070,4465741,2791551,3104321,3487511,182936,8953396,4033975,9551677,4584848,9322386,1373444,7115635,1551472,8579990,4569742,2093165,6049666,1233921,7655610,6475840,5278029,3936861,9285626,1290947,2033019,4724902,9087338,635159,6189043,8354653,4180230,654784,1146204,7284552,4142295,1329141,6237948,8176271,880818,822797,7498657,2254263,7938432,9050130,834253,2508175,1143295,6883920,3742097,8798905,3359761,9020126,2735767,2645388,311073,4768787,7370291,9398412,5403946,3559334,7753065,9584177,4214118,8899270,6868729,8356414,228412,3106677,6532685,1109230,3929475,4031343,3363493,1867907,3081473,4197747,4376082,4224769,1081668,8118179,3023675,4441430,7138306,5759442,7086818,7449379,528229,4457109,6847792,5932176,8016444,4600857,5516353,2230562,3500128,2385083,586976,3728540,5491761,7119662,4837770,9421236,1151005,8201264,1289143,4232479,2399012,5665226,8457248,3480681,3783406,1480923,7922112,921712,7240365,5008931,8371092,7768595,9466041,5218884,3700771,7482485,9819742,9217125,9713047,3319870,1602208,300024,7048410,7093969,7419687,1886181,6515206,8570692,87446,7804349,2803171,2486458,3469576,1260420,5967140,7252982,2741343,3889252,8174694,9981709,8898184,6545787,7750305,8364225,1764671,1451077,5846710,1584413,668202,5559758,4904283,2270411,5859783,1952694,9364381,3279470,3838875,5879587,1850163,3926321,3683937,4653334,6412780,7153513,5913754,2379921,4406496,8655098,6269173,2581191,8636807,5167357,9126978,6387112,3531583,891650,7838189,9378293,2476063,8506392,4938051,7380347,776804,797835,9333041,141185,4077305,3171917,6020773,5927468,7098238,9704711,580803,3511019,6858224,6494558,5890940,1264720,5149656,2160114,3845911,3786464,7327472,2972890,173576,859055,3864540,8011766,237349,6340604,6518159,5175401,3720952,7294963,5973236,3053993,7436149,50541,6225911,3456923,5978010,3324150,3161634,6558814,6835169,19859,3053372,2726109,1284579,8203028,4886224,5130491,1989492,2213696,8103382,2163069,3072752,1967922,174836,3310101,8308526,6692995,8485502,2029478,3987958,4458738,5083472,1424108,4509280,1309383,4881031,487291,4633534,8042665,7046105,1468703,8062524,99477,4194813,9347104,8302506,9081037,4477596,291998,1294734,2580978,2455068,4367487,4548901,2629904,7677588,2857427,9322899,6163090,4886906,3310858,621829,9970379,4734966,5131110,1279763,9615997,5618401,5913297,7658663,2664506,7382001,5721188,2763984,1576814,5068292,1066491,657852,9545889,1358489,1952587,2126867,3813558,6320074,6675768,6443462,3997662,9533196,5766362,160753,4420103,9077220,782583,4390482,3812187,5913693,5670246,3428185,1532094,1583543,1086848,4196601,8965544,6808037,6960586,542359,1876329,8027077,1200212,1422219,9385567,3152799,3549086,3199125,9472874,224855,9642588,3470537,9758052,5408950,3631290,4178155,4486171,4413874,8568638,8298358,327567,4238884,1726543,1859661,5822428,2813392,6056263,4787973,9621429,3016850,5330332,1497759,1043927,6530545,2919978,429494,9683345,6469065,3628620,9156219,6693921,3271208,2626756,6451973,8680159,6258047,630129,3166330,671921,9198767,1464689,999489,3437652,3191233,2859151,9260080,6004625,8915414,4048054,5626055,1932264,9378386,7123815,2976192,5908932,43794,3405687,5592277,6512860,7034307,4748496,3206781,305516,7375253,9658754,8985676,3633301,288884,2152006,4305223,9487651,3616696,5304712,2925304,6807929,8163863,2185385,2812555,7079278,6233439,8438611,9011543,5611826,5562426,1987735,1520758,5606221,5393423,7113035,2119081,2427730,1861532,5325862,2733247,9236785,4984617,1718924,2870087,5273501,3870931,7175310,4761153,7487627,2480022,7686457,4295556,643886,9871842,7108112,7723164,6105281,5546723,6734707,1717108,1109150,8722443,3237866,6715371,4115866,350902,8834452,6543597,2212434,4160315,9276845,1449220,9144932,995769,4319307,4418434,4866700,1494618,9179587,2354327,3974640,6866045,6649884,4618527,6737888,3757996,2341691,2843170,9304719,9076399,4560278,413869,7798842,7798144,7129240,1914709,8149047,5963693,8458306,361481,124008,7735152,1810702,9268941,8730921,6130010,3687375,3597621,7624628,2866963,5951949,1599269,9733008,2601834,6217796,6470897,6359830,8559488,9314067,5664550,7635887,3874345,6078419,5434730,1672490,3207660,7349440,9821537,9171354,5807746,183019,9295362,3542898,1993722,8564304,2273820,8123732,2251679,5871442,5748361,5118643,1823392,7347631,4851651,4425226,3565428,1322549,785056,2124916,636616,6449606,9760804,4510962,2528026,5195535,6183453,5735686,2544975,6004991,4907040,8352722,6188010,4202403,1895621,8181733,2766707,4169441,6305465,5018387,40884,2053827,137030,1864276,9401458,4988682,6289502,2966887,6311231,7074558,5091803,6947847,3524165,4852608,1458810,6052191,48143,7642263,1787877,2593119,3647254,6694918,945841,9835265,897322,2841462,8016998,3664029,7010904,4322464,8682417,7051788,6376291,8819447,8916064,5777750,3808129,5205566,8744637,119361,2280125,3836441,7067208,5804290,8689050,8526019,1856481,8737194,6168282,3644359,1330313,9815536,339278,2276155,9650801,1236600,5117618,7667799,4900630,2128522,1990263,3583047,9180311,8366555,2402495,8096376,4144305,6210624,3301942,2888943,6329986,5582068,6725385,3397195,1386358,5414435,1923214,3242840,4151629,8091496,6887200,5481942,7907032,7226478,7758097,7557834,8463079,2875715,5225633,3363709,5004238,7215897,6946756,4184549,5582452,9349251,2280925,9726758,5559876,5582868,2615702,1889862,1164936,9341087,5287057,2551295,4755522,7210272,5794136,8907151,5301768,2681336,4389093,3208801,9907815,2147191,766635,8370894,5022906,5992269,1734604,27145,3208166,8681360,4211694,8790619,8030612,6492620,8517377,3590489,2075488,1133079,5480352,3240425,474166,767410,5791721,5229689,7977682,1585857,4136840,3279450,4267194,8525934,6488251,4175010,673125,7254887,2545904,5696032,3247156,4280508,5723177,6455322,2961869,9934872,5245942,992482,6427492,3763320,4582972,8502981,4896399,63324,1743406,5370566,830735,7535127,600255,8808417,9120985,4737096,2087868,3388180,3263030,8576120,7563190,3936155,5831007,109095,9632188,9078164,4389604,5355366,5533487,7351474,5290238,779429,8343956,1717730,4542749,2926928,220712];
echo "\n";
echo bubbleSort($array);
echo "\n";