#include <bits/stdc++.h>
#include "dzilib.h"
using namespace std;
const vector<long long>Y={3688808,7423788,1808152,196187,1679062,866280,6913199,651371,9150732,4214846,6775316,457033,7143127,3997699,2605878,7543315,8079314,3794783,1422734,8861751,4876974,696843,1848097,9717864,2328019,2500740,1627638,217174,9345066,6375925,1467275,2816940,1982025,4331430,608786,5004409,1939514,1762137,6163367,4094432,7165063,9360236,6554288,8670175,645396,609298,7196870,6928403,4298074,1433545,1229830,7780673,7213481,270986,5691191,7003824,5486384,2994386,2756300,4000225,6091619,1739868,6071639,6118381,8193892,7609257,9443928,7307758,6999050,4531732,1587922,1320947,5795238,1161883,6521460,4900651,564641,1752480,9284970,5804984,1061473,6232913,6946195,4172178,62852,4434992,6086163,3248308,3842238,5791546,5866418,2710723,969343,6745886,9354054,2279033,2501714,6267246,8783688,8191569,7987114,6381880,3504697,2724134,9054414,1106447,5908484,2070173,8428081,6897927,6646280,1711800,2842664,8012686,7302555,1208109,9072194,9429562,4975045,344699,4831389,1931228,3630150,1734374,3872312,6426320,302011,6939418,1623169,5351028,319385,4481873,1792602,4224988,7760230,9265950,5532928,5235230,5452258,4335318,7415398,3044841,329633,3249630,5252109,9649414,5460037,9634479,207925,2550821,8497437,2752281,8522862,6877850,7804966,1551140,6523972,6546927,2908872,6515149,2550869,1887708,1075049,5282907,5122517,9244053,3389953,4045734,3045883,4525078,6941467,3813787,4625998,8282599,58597,7005879,9487694,3175427,1965366,9472338,4321353,292137,3302777,3104248,7922997,1438801,9657208,6264492,1542542,9433603,5891651,1558752,9635418,5306896,1233025,2852154,5934737,6998684,5272632,5761034,7761696,7501263,5680476,2458608,6108855,3236795,2095417,9186235,366427,9277736,5651734,5313199,4218116,3563112,4869865,980708,6794629,4630765,4856110,6246505,5731302,7968383,9642736,4457354,9091588,8199927,2823929,5023387,7523305,5750489,462209,8076006,5350177,3191169,5205126,4412205,6626674,3310229,5854555,5532101,2900231,8999224,4944573,4985366,563213,7166721,3675952,8685700,587098,4046142,5557088,7168892,5481825,3188498,2506417,2129052,9381822,1341289,7408042,4570578,3248125,5149685,1301247,9090187,1372397,2139574,8409525,7010907,8456906,2780005,7794895,5905608,7850596,5260884,1045448,2971146,8154177,7760988,5681718,5128461,8000412,9207375,1529498,1695998,9621381,4034247,963385,5204508,6885201,6064265,8886750,2899152,1254410,7701799,9388996,7967489,521942,6375353,1093828,5067366,8275521,2356123,5430851,4583832,4857938,3503643,5049016,8377612,6257343,4434171,4473491,6660887,2477122,5889403,9678464,4556414,1921204,3547019,5804912,3871614,4926756,392118,402453,6913529,6676320,3287714,5487748,3129464,7779098,9245907,9615461,6293530,4179601,7397555,924811,663594,540133,2124726,4241276,7696196,4719970,4652322,2643826,1788192,7894502,582095,7501053,2822227,973330,5166253,9231597,2903310,5892146,6374895,7179172,8423183,2641748,3467860,2475752,7759839,6677107,8295201,673968,6520589,5862626,9013752,4049548,334842,7578434,1243409,6966975,9175797,8252991,7716062,5532334,5182576,5432381,8771841,5847340,9168254,992746,8180897,6057225,6264316,6163222,7445209,1536736,9498811,8340757,5279417,3733225,2016850,5387457,2301626,7575126,8714134,228997,4846812,4384020,8131469,7250732,5761795,3760774,2817464,4810412,9617666,4048711,5251799,89220,532640,1789659,5908777,8495002,2014969,1821910,1164700,3996027,8411571,1787256,9220223,7952478,6488040,6695066,6671466,3659071,3652308,9494112,3110333,4455040,7729052,5868758,4722209,5154364,8348263,3181401,4836041,9473915,4704798,7416525,7815595,3210660,1469872,2861400,6073885,9012123,6540610,5788097,9216090,988454,44816,1215992,2160822,842692,9653329,2117728,7216479,873399,2412783,5577645,6539163,8561460,3583885,1558468,7938184,1898312,6585935,6772663,2179705,4729499,7668440,9609784,1943095,8286358,7720928,2872447,4178911,2026162,7408287,6567875,786563,4793628,2689920,8537595,547591,3614691,5505055,1812513,7883535,547290,5704412,4741871,3150782,3979220,7620664,7194533,3940767,2263232,1226100,1249204,948006,7047303,7221480,77806,1590652,3877061,1160626,6835942,5879555,6417676,4103348,2921120,4683211,3479967,1293635,5557099,7485883,6412443,3687836,5646733,2085259,2842683,4319252,4348165,2840883,8491542,7978828,3930637,881430,238736,8168317,2007537,1959195,8490883,7078956,7626648,8613152,7460822,4094271,5082981,1522867,6468776,6554144,3729817,854644,3634129,1961817,9665984,4847385,4433807,714742,1754328,1558233,8546428,8767130,2477247,2742710,5183758,9506363,4299247,211311,4742762,1343377,3292773,438592,3862795,5913937,5423825,9494273,5187873,5411094,6975133,6096366,3051003,6626359,6540971,2005160,1031070,9632681,3213936,6985366,1899078,6178733,7008143,427304,9353319,7088255,6681152,2224587,9359613,2327421,8274793,458662,3125813,2404928,8118050,9586568,1923901,8590683,3834522,6397731,4679016,4331573,6187779,4270240,8737492,4246668,5375214,4119779,8013010,3659585,343135,8015580,9280266,390688,2415171,1361525,903412,6494453,2766274,2563373,9093641,3906887,8119522,1251171,9724318,215303,957111,7288775,1464694,5773153,7807416,8867956,7648293,8732156,7274892,5809842,1023700,5456538,8067614,3847197,847020,2480102,6606770,4845675,9713037,3423178,4417342,4193140,6999377,7623622,1785618,5382027,6299892,6583259,7738656,1836469,8741957,8332904,8633324,154080,6364790,4697169,4665952,5094103,2705802,1062228,1764529,4441636,2635168,5777258,8505521,1366046,840222,1989867,1794112,3007127,6267376,9422935,9292398,6745026,7728286,1022566,3391152,3383251,9075382,823305,4237338,8283132,5040345,812020,1629637,9233578,6120589,2301331,1311875,8417580,6747598,8272409,5479767,4707006,5049302,9070319,4460999,5664895,3732458,5936841,3184877,3971003,8582297,4512740,5024078,6647513,9177744,2697768,5890372,1429141,5082054,8076307,8353673,1508404,5980451,450463,5921519,3280034,8610078,1034113,7252369,2716472,4748307,2253969,9166792,6525074,4741841,7077089,9274929,6816838,5902051,3975875,4438743,5354348,5619335,6912528,3066164,2400285,9201944,4100225,2728763,6451269,2661701,5382292,3045160,6505201,8813899,5333501,4082083,9318529,2778778,2509934,5875578,1593126,1423411,623114,5570161,3158926,6722870,874324,7342835,3901386,2349766,9272394,149631,7781348,213106,6906920,1504192,8097210,862254,3467279,6298542,1502990,8616449,2567715,1495399,5340549,7780937,4677938,8767415,1246521,3086802,8632187,1522583,7766835,5838180,9386388,2950308,4145271,6988003,7693549,7721015,1923538,2625169,222139,7746462,2727337,6201641,1501727,7917590,3051410,133161,4947819,1663814,1489849,9236430,3299929,5174656,3472058,1383836,5949682,1781205,4390646,8793025,5210028,2986648,8645985,3346226,6402487,9052753,1661749,3111096,6678436,7204536,2641851,3254174,6246928,7337982,7986020,3786256,1526909,6260937,4243318,8457053,2428029,9216404,509976,95728,4757890,2208413,3385081,1115435,7484893,2353417,9288687,9420602,743430,7792843,7801320,7249776,8250090,3630513,4377242,4357135,4255606,1279982,7216311,4321217,9585515,5759878,4040983,1542476,3227899,3436749,2705544,110002,9574862,8549520,1130752,1303667,7945650,8134792,2537236,1651759,3796257,5592696,4803721,4707680,2377991,7128920,3952824,5747333,6002077,960392,6687746,3689961,7571727,7326725,3172845,1581603,1131362,2357515,6071520,3599953,7745896,5182059,7956265,90994,1673854,4091958,1773582,3751613,4272799,5325939,7262181,4522211,6529622,2020543,4631619,253758,6663225,5173292,6372992,4150190,2946180,7895584,6547497,7315810,2082639,5378190,1077598,4411623,6141747,1976974,7823266,4150000,1939173,8825244,4783486,8549411,989285,1807008,9025373,5941394,8008634,6390027,4925664,4223075,1954001,447499,8896837,2394769,5042342,2177884,6495671,2722816,3897499,9191030,961888,2698141,6357346,6850288,5220198,2025849,3678551,6970187,5667594,4807043,1539386,6627904,9023830,6902207,3994565,4683438,5399665,4311830,3351677,1254270,6515978,6422197,7487959,4955026,7971454,9657955,9719428,2303224,5347899,2272244,8656395,2763374,121944,1677307,7203217,1003732,9277351,6660858,2062153,2369800,3029011,7711277,2674636,3083799,5225574,6990485,3216725,2138075,2922229,2549931,2621806,4999218,495470,4389059,4369286,4356391,1436835,7119770,1666348,3368925,6878293,3517638,119255,5274363,7187123,3539265,7909329,6682702,1746389,7667689,3237363,8647002,4977849,4040810,4676326,2255850,6732067,1062481,2721933,7990363,2367611,1661682,4017661,8559194,1564951,5023589,7787430,3450031,169268,9437860,8059406,489991,702741,2249876,6811458,8967971,9719193,4041831,5705154,7064433,5641957,622945,6762208,1316796,8608811,6913749,1720584,8640105,6910434,2113038,1590801,2385255,6253837,6225278,7583466,3466876,7407489,9439496,6760248,3094962,1917579,9407983,3423918,1344085,9107376,1900869,8682464,1909273,6339046,9198698,9446059,2220229,3964110,9076170,6597410,9696479,6401527,5647574,2944406,2022037,3547082,5227015,6116849,7056337,4217816,293040,541265,3178386,5239467,8703904,7369939,4963309,6730782,2860195,7578441,8521028,4612943,314495,1016007,4432640,1081933,50686,8667652,7484083,6565709,8487369,5699086,1780940,2900640,5734151,9305554,5489818,8495611,7679902,4358268,5248254,2433606,6724246,3432268,5125073,5709466,728820,4534683,1380847,6552681,8210070,4897136,2163845,4143699,8633829,6710478,6073580,9121073,7600347,4422978,8279223,7070604,6652660,4744658,118607,4001535,6812139,5338860,4246455,4214924,6323379,5375155,6548834,1701972,2568141,8528960,1212643,8960070,4796099,8192468,3317977,9675213,4761438,8615105,6602049,2476886,3140373,8747514,9208411,1426489,3635723,2577772,1608267,4634503,2831898,3640390,1579139,1973654,5094309,5498374,6830021,9578993,466926,5909698,4870294,3571872,6057887,1495129,9266808,1707403,4467758,6111887,4669899,5430990,7897230,3506121,8485234,7420909,1032655,8625579,2482263,7213674,9356019,1962301,8055080,2264396,2961403,375368,8032148,8797164,1191155,5405984,1582242,1800847,701404,494962,3617716,2958830,8920789,7484677,658820,4028097,1184607,2865561,8291403,1659398,3730057,7533999,2158956,3475699,8936873,4095242,1364048,3822702,8415981,4159053,7895794,5622188,6259844,6857758,3971660,1468733,403260,8164941,7681439,303357,655765,6143606,770083,5930101,891155,3960639,2812643,8839613,9185777,6280248,3463591,313152,4960131,1378040,5763865,3151384,1977016,1545027,1781439,120583,3744401,8673962,7034397,3569003,3784489,5315903,788076,331663,3399983,1766914,2761761,7177182,1131141,512790,1064991,1998796,5848953,919677,1089032,1753096,6130496,3409985,453732,4406253,6442428,1677288,2400225,6098686,9349714,7699701,9591637,4752880,1173803,7496270,3645070,5842873,4107507,9167445,8359865,7874878,362605,1336660,9279617,1636008,8594011,9421913,2882138,3933741,7118447,1919768,6818148,823138,8616542,3972097,4878268,360294,819718,9253813,8708109,7438598,3762754,9626727,8382676,4752173,4833822,8422180,9449883,2636786,8132397,4503029,388353,8076261,3133812,5492232,7536430,1105406,1878440,8755148,2178489,12939,1464183,919601,9433728,5960170,4804390,3038003,5579898,6890791,7753437,1404364,7697990,2839728,7793701,3434446,7883532,4332743,5775260,2443741,1639393,5800420,8038337,7227669,3695205,6252010,7725602,1667110,2422019,7015148,5689799,4709321,3710815,2533402,8226088,4422784,920117,4050674,972002,1212191,1622086,569033,4091195,6939451,1716933,2630129,9015639,872822,3724963,6720424,1454722,3680979,5777125,4743431,2949327,2719419,8024309,8715204,4578560,2264175,4794299,3514967,22852,511554,4035697,6486944,4030003,1783968,5186674,7297436,9502082,8545632,7265819,4706871,4373765,5716313,9272910,9033001,1621595,6413776,2578778,3470244,7112046,3624839,34367,3065149,313904,6294096,5919485,2579693,6092293,2023190,6305516,113477,3522521,4018622,691431,6121877,7260769,1848763,870245,309246,4433307,8724027,4920818,478088,1136354,9677539,3578387,6854530,309324,312951,8595670,5376823,4029388,6352385,6687517,8572546,3067619,1753955,4472372,5293957,7562659,544936,8369364,5328287,504693,5491217,5898239,3632886,4302200,7474269,1888852,6001214,8085890,1359503,264103,6846757,9063185,252684,2462506,6946305,8245928,7695232,3222419,665651,1482047,4382452,8664845,5492469,7873422,9659689,3935410,2196010,5489782,5263815,1543531,6880514,8514865,5889164,7057533,2973426,7584987,127660,9332972,2702290,8510082,6535811,7894423,9089855,8417533,2048755,7755150,1084351,9552789,3262860,3977466,1929725,1054780,8237327,2405965,7936050,4218391,4443432,954337,1595098,7407613,6321273,3115748,5780040,8462344,4823207,9297073,4277174,9722801,67790,6591706,866027,4050237,3413313,4296304,5600223,1484071,68419,9406180,5091651,6787502,7083945,8236398,1175508,449599,4802662,7644848,8785492,5050339,6141749,8029825,6462164,4208299,8248179,2976985,5813103,1855498,840506,2269723,2322471,1254068,7514012,2428187,6591142,2798471,7700524,6646856,7867234,5555500,1960625,476021,2525990,8435462,6905337,3404462,8639433,8469355,7137691,6996531,8029542,2106113,7498800,1602942,6731442,3731495,3578048,933227,2965145,483695,4031429,5139624,4492994,6909947,926452,2402796,897479,2704104,2829450,7688918,6363080,902744,5034324,4434001,2566906,5840816,711785,7968955,4916855,1843070,6138767,8421446,7251139,6053979,7269731,9092445,3649228,5510984,8450798,5883954,3253217,6818557,5925459,2028462,6032729,2372810,5045186,3415065,9705115,5211347,5616056,2160535,1416298,7550642,8142238,2411508,8271920,8594666,1832814,7879861,6851486,9176637,1862026,919009,9084586,2171368,5519545,5522853,1005168,9167832,1162859,2307959,1224795,2152753,7286952,4398616,6157663,1638761,1387067,4318986,2746808,845330,4292900,2791257,6921277,1228347,8748828,2359006,7459934,5003452,9147111,3062246,9626105,2028032,5814083,6379948,2900788,5078126,1834375,8146305,9722221,8452367,332108,469546,4371924,4248332,7113020,1873617,6485166,7130187,831150,7290278,5551585,3060404,6964319,8883578,1504915,8283439,2523464,860410,6922007,1852440,6438479,9628833,3814731,1935714,8007267,5113460,554218,6225605,4079469,2672110,8647944,6169226,4063032,6362855,6380092,317469,4401022,9684975,1545353,247976,9613939,9721339,4986931,6021374,6492307,5670797,9007202,8916418,6216078,3118271,2023635,3383159,6484347,3090154,6754010,8150414,8993600,8729533,2127359,2069120,7675564,5509055,5136064,5399711,6063087,7294644,7719308,5284468,5549320,820008,167583,5111390,7972332,74754,436426,835966,179340,8250379,4044030,451873,1518634,1007785,5044286,9392356,6872367,7990752,5314997,7056615,8002832,3068650,2534050,6882007,3327336,7595186,6407904,2858437,7362219,6717227,9522252,6306857,542953,4587790,7002755,5912716,6838957,1298678,2977348,263964,3054362,1030756,4595398,1259605,9147541,3213477,7167846,9041735,1269223,5141854,1634876,2222271,5869543,1184060,5223490,1132871,4084992,4396955,743055,1877059,184922,6496141,1519964,4673421,5736195,3463326,90549,378858,7444141,6337827,1260455,6792934,1945782,6617658,6692046,2383724,1563128,7585319,5888421,2876732,8929575,6012575,4380089,5408343,4780226,6843954,6192748,2388445,8498345,9368479,7838468,2041464,788105,5150964,4810727,8808165,3886443,5588948,1188634,4462344,4712796,6509711,7814313,5617205,9277845,8197794,1616914,6588935,3744012,1664185,7992509,5148442,1922628,964227,6082953,1889448,2436520,2121569,193254,1795700,9335157,5464848,601671,2159635,8547771,5418155,983066,394141,337806,6538744,2542957,672085,1085528,5680691,2904239,4154941,4013197,6554251,3811035,5909220,7939619,9712109,8584157,3851622,8422196,1313804,6260668,1628289,4998651,8915877,688441,4720616,8873344,5875467,7812242,8138648,3270945,9498750,6216085,5767175,1364370,1992911,915691,7628387,7109467,7562238,2397408,4824750,2961323,7388004,5197814,5924822,8087879,8893670,2034197,9048530,2127119,8137075,7094289,5686997,3230839,1594957,5266422,1663883,6201532,5853756,9616089,9268652,761733,7368990,9375209,2098741,3301139,1091579,2595380,421558,390438,7792148,4133082,7295268,5953362,9655042,7392960,2945725,2926701,7926990,4903767,75368,8802664,4377087,2859300,3269461,562425,2166517,156425,847646,5675079,2459415,1386382,9660402,3976066,4074773,7376197,6570672,8356639,79399,7433495,8003206,5545947,1120135,1006980,7366086,3336597,6702758,5736206,804395,8179483,592055,3546812,1350534,8067026,6272776,8425459,9381464,4146401,4156967,3198810,3728149,1553895,9589709,9174829,7044752,2127288,6038834,944801,8620258,4052783,3161248,6389448,8027889,235571,6395638,7909276,8483421,7045973,1968401,1946600,8264662,3852211,1609071,9586961,2377866,3371044,7070325,5822495,7049273,1410840,8124056,6353408,3951083,8716446,511173,8216540,1503012,1181115,8398143,865101,6555678,6676093,3306605,9693691,6059199,7923692,5344221,4062197,9712813,702020,13962,4547222,996444,7770993,948377,183681,1893951,1385577,1608856,1204746,3194708,1295671,7861215,5638646,9268691,1815355,2990283,2931608,5559579,2083310,5047786,3809206,3235466,7579853,2984603,240059,7201932,5182427,8228626,4775804,1368439,3751102,1905274,7207048,9448914,635999,1340473,1965696,3980942,7991705,9170262,3779152,9669675,4835902,7928459,6459183,1612159,1200924,6377668,8853426,551006,227702,1588048,5065944,7467448,7325649,5837585,588793,1715956,71451,8891855,966592,1040316,3487275,1221793,3497141,2926572,713725,5839294,5093244,5539214,6088676,44215,1415178,972364,5036091,4919167,3547801,9425803,889731,3018821,6192303,4172206,2683118,2784036,9308812,1998509,7648493,5405869,9169242,1345298,1305399,5085591,3550675,5307958,8608113,9611883,684809,1184429,8062127,8561473,5120540,5319163,1469977,5100661,8128295,3081089,1023196,6298634,7027711,4219327,848370,3134448,6158358,7458112,7581445,7664937,7165389,7623974,7058607,8735008,6752654,4469156,5338622,6704490,3315767,5445715,6521612,8285515,4026912,5320811,3330485,2252223,8119649,947444,5548485,8070620,1926533,1148599,2451118,5861150,1456181,1679032,1459502,8149375,2235657,4021135,3313276,1094113,6571901,3503539,2422480,7683626,4870260,4205822,730036,7736194,5565178,6435220,7754262,3030656,1741410,69146,811215,3089855,7449954,6056504,9395505,2576434,5432181,3321694,2299841,3524998,5731505,9357625,6790808,816425,5422651,4878604,8828793,650034,9636743,6083563,3105769,3754855,9414827,9691628,481929,4138,4920083,2975005,162271,1516351,1892840,9637010,4719026,9086244,2601406,6184218,8570571,4207421,1422829,1733196,3240163,9720483,5771093,5987268,8740416,3125489,5086403,2927998,4274238,6030046,7085334,1991150,9359553,2001750,5988206,5035123,6862444,6476251,6888273,7914507,7708486,6476855,7312474,4628422,5881466,4897351,6043920,962687,5286658,8267507,2487823,8412508,9133898,3137862,1450017,3101090,52705,6329260,777959,4840363,3157722,462961,17010,2014853,2637895,7083292,9467827,1958757,6126605,2533798,2562948,7680386,6370723,8390518,3055606,9589520,4089018,8150553,7937716,2508634,7751722,8772238,144936,9266648,543701,6889841,7433123,6733476,2966070,8915197,8657270,3285928,8553857,7607113,5892018,9071298,3839432,3284155,3041209,5370741,7552862,85922,7200361,7945206,5135916,1397363,6944798,4915767,6901618,3280274,4601259,8877127,7802987,4367955,3923789,2303101,3833754,1199360,6318923,4708197,5730877,6415971,9018472,9592735,2338218,9350550,7641595,1892272,8192930,4744660,4679745,6789156,32549,8335247,8932126,4867433,7347247,5339700,9432964,1180273,6828639,8250428,6066944,7998543,6030764,8950605,9235722,6695490,3660024,6682100,4985236,8168616,7449399,3112670,3112134,7497857,2210304,3230661,154975,2794322,8329740,9430663,3007031,5127617,5779400,2892913,433332,5306403,1922470,5467693,2254058,4511297,4224238,1765781,327586,4560798,1553773,7095201,5663097,5081442,4705712,7358956,7246901,8069636,6305289,1958108,3081733,4753036,2832549,1633696,844019,2643977,285047,3748786,272243,6406983,773769,1752461,6671511,145211,9189827,2049713,675795,5879545,3805750,554080,3303325,1437617,831596,6058834,5529312,4152334,3814965,3242882,2014151,2582615,9667687,8901538,963681,5749819,8787622,4359317,1333480,4984999,922479,3127889,8170697,2155300,4051321,7882977,124743,6042197,2705294,4861998,8800390,8138528,3870215,4725608,8441256,5963337,9000915,9318797,8955891,1198588,1555951,8112497,1466287,2827974,3387299,2122655,476257,87153,9611262,1250974,9232125,4138348,4302961,2748008,9124468,8468942,6916793,7319982,6947500,2664379,8181718,1365209,3176205,3113497,2424969,372045,5516776,5160414,8243491,1814848,4585555,4388927,4284563,9623037,4398760,7117774,7111375,7584891,7718066,2941247,1540221,2076747,266881,6554971,3036641,6942568,3065022,4651158,8265497,4226038,6461036,1773470,5639557,191909,1841365,9651104,8334902,7120286,7603037,7116025,8566900,7407067,1853122,2700981,1067173,3103690,1769220,4682771,9502528,7163866,584237,7777236,1519083,4470031,9699619,2584303,3070333,6173236,7441328,1675128,3515641,681147,5948218,2857112,5818415,6726629,392394,1894609,755944,1538823,6345696,2459837,8468807,417119,3582125,6620054,6050578,2388791,1946976,4179167,2162613,2937159,6675656,8185554,6752086,7052134,2831982,6469725,4179398,5858495,6796087,2594100,6617341,6693294,6647866,781554,6984554,9576292,7772602,2702888,986201,2484498,4129884,4339172,4322514,8675078,9245926,7433405,7052876,4301260,9056601,2595182,6323173,7018457,949104,1587020,5817286,5509114,5887492,3847504,5462539,3875882,2300235,9353822,9553465,1792286,4061269,1491310,7732206,235917,1070981,5229552,5359569,9374113,1580326,5772139,1744945,5328014,1667548,615118,5426061,8230602,6590972,564011,4106739,5599390,5048887,2624613,1401978,7209384,1709343,6221850,1652121,7279822,3690082,2886742,8587996,1348490,5411141,269506,5263804,4888467,975191,8035694,3871195,6062600,7686519,8615695,3987833,8308992,862570,8441785,6332462,2084389,1689815,2879109,398344,3136125,5769037,3095388,4953871,3649213,6386886,5421833,1908065,7685131,9585851,9048332,3006947,8427033,2568846,641639,4518546,3207958,1167793,8784553,7514590,2147587,8016378,4269304,7976811,4215763,5976450,4757301,4302852,9080826,9612792,5399926,5142649,8610091,1412134,7105143,404142,7720833,4921560,7990659,4065499,8647365,8512821,4453279,7743123,9541847,9723904,8392987,4509987,4408925,2953096,179972,750380,6096936,3377508,620309,6336382,4358622,8016545,525365,7433951,681504,650546,7395800,5487333,4141103,7075799,5706181,7444012,9693508,2940354,3064820,3519652,3801914,8712861,2465380,7794692,2981596,3620323,7954400,6944443,7965267,2744134,8743603,74130,7157651,9470759,7285899,1290996,9025502,8658525,1763541,7697096,8639243,604271,5013639,8874782,4722563,2415953,7317327,2201423,7323783,619630,6456755,9489603,9433186,7195373,5414626,6294703,4788366,7071334,1075750,5612263,672390,1484702,1447961,2896982,9063193,8187940,3381464,6730424,2585435,8480884,2219771,6038991,8458462,7659165,9332732,8279356,7978660,6056624,7100225,5773431,4831281,1841974,5278406,8704312,8215894,6396646,9509750,931403,9304075,1465423,7905129,6924128,1343478,9642972,2289888,1406166,6180778,6013273,2648779,6222737,7875113,9081466,7603794,7430734,5561548,7064229,9484681,7709253,4241972,7608739,1769457,2329926,6572888,2553485,144223,4567740,8476626,7027811,6114867,4552420,38610,5927444,5120952,4804643,6672491,5109526,3897509,7939579,6695889,9320308,4566281,2962685,258096,5792653,5879543,9568142,7324456,2451572,3092982,2227359,914601,4620960,4713750,5921305,3683505,1875086,9085191,832339,216245,4015697,8103905,2420844,9421037,6949416,4534702,4394463,6852678,1813795,3230196,6471843,5590015,8434403,6029090,1113414,8583940,4224914,4067363,422248,5459786,2013075,5505586,3218436,1999407,8647516,1983473,2620353,3803912,910003,219286,6354789,3387692,1017164,8385367,9185216,579625,1334868,2271314,901472,9235086,3525236,7729104,5022785,3924250,389909,1670598,3782164,1738466,1678908,2048048,4975132,4847698,6528255,2132391,9315256,8141885,6729183,4302835,344495,8146159,6681015,5035089,5078398,6706303,773517,3639407,4462370,2744008,7750384,3799308,7613103,9379193,4955966,1366648,6229030,4942246,7530674,8029307,5430079,102576,8757883,136200,6149585,1910116,5528100,2638071,3434967,8287786,3694055,8178211,4961131,6277876,6860102,3931335,1312246,7569298,8146704,8891394,4861684,6755115,8200850,3241214,4807552,351457,8307496,3172079,2387653,1428038,6483435,6396641,5572548,6203177,3145334,2738776,8341694,6286055,381925,4381639,8009986,8343200,8271495,2248074,5108964,5418313,4162718,7696170,1432886,2441126,4071323,3500350,8171588,7418730,3663374,8380341,549774,7165433,1352999,160474,3860631,2826880,4869874,5074580,7301064,9234114,4079123,955318,5572581,6232388,1415636,8682741,2219558,3815234,7820129,8265008,6070339,9601611,834443,392702,678377,4235815,7289503,6026566,3819620,5609497,7955103,977638,4888464,6871314,5858995,852246,1490100,5687652,3667066,8870542,741739,5626643,2930188,7882307,2310895,9060661,4180200,6788469,4765875,960487,4325229,7345710,2654407,4467611,9020225,5728308,629538,495761,5878887,3827069,2400406,8377450,7262705,6389140,2066854,1045035,8986423,9168997,521310,7699499,692871,7779482,7063047,118352,6447759,8531231,931082,7222021,7726396,3666800,951359,4010994,1832128,6287753,9676845,578508,5131539,8981101,6356020,9490243,1798090,9504625,2854720,6126275,4623851,6396782,6216875,6363995,4720454,1702020,5521075,4863004,2405805,827717,6238446,7836542,5993483,8000778,6908327,2877309,7157957,741830,635540,1988443,3816888,4377808,8313201,5225176,127738,8584096,7661999,8545855,6105517,9015616,3667069,9111694,2711345,5141933,967082,2938935,3964089,2887358,6762599,2057404,6244098,8191218,3744367,3852831,337625,5859289,8783987,2247425,2320248,7477113,8658959,46661,413659,7382662,3577080,1880395,4887257,3607495,1338128,904061,1644293,7816044,4779478,5729200,7563371,2688672,5140577,805852,845671,6442772,7149119,8270469,4772513,4815433,1583881,6061042,3103037,7238414,6363833,6280524,4595170,7893300,5209132,4896223,1563304,2741543,9476683,8012616,18728,9682375,4527707,5431578,1109411,685079,4955567,3837951,2063011,8170060,6417531,174114,891177,4264758,7918780,6018455,6057970,3821840,785867,8994026,7646429,9641171,5304751,2290360,6761643,1120985,4568657,8889416,6011930,2634043,2374411,6223114,5958336,6311999,2064305,1780460,7852065,8826120,6194570,6647571,2540844,386049,3379477,8452845,5833997,1846186,9550065,5793527,6425461,8742133,9617691,493000,545365,8706912,6029051,3213971,8424584,9376872,310889,3187230,4017000,7075177,8849795,6325869,3286428,763925,7584009,1990059,4097289,5208498,6225053,1985812,7774279,3213239,1919714,7535646,8352882,6491692,8454011,4019670,7213658,9645688,467330,5933777,4172472,7683854,5880229,1848742,7117834,7787360,5979026,8958642,1816891,7226734,539086,5982289,6947960,6232745,3261117,6672693,4154416,4243551,8578714,341403,3714754,5356483,2500401,5407255,5621424,9373606,7781485,5900807,188857,7565525,2552681,1196344,1974150,6521820,554856,8848435,7272613,9392979,7855534,4350230,4243816,6551252,3998197,1546108,2280706,2517477,2369277,1402511,4008696,909351,7750866,5475045,5854607,3479212,5029394,483938,3200830,2797885,7084593,7473386,1035917,3795137,969885,4318872,9402625,6050351,6793584,5458158,7210146,6423127,704643,5205361,5264628,5909942,3398456,4016077,6562996,750275,8776940,2035206,2378286,8905267,8754545,5552337,154514,7378883,4422780,5160311,6576604,2812209,5625,1240005,7481838,5668772,8682312,6635101,9549515,5650129,8878831,5541789,2883071,5903513,5158401,4129723,1358013,8792432,7374710,1676969,2110603,2649066,7960500,5808964,4650390,1422099,384817,5555757,3775985,5397933,725925,696544,2732804,5197990,1078634,2424006,2535981,8196731,5469921,9508537,237698,1172395,2428885,6955697,555244,8198095,1027916,58342,1993907,6390867,2388050,6842564,4542170,9497401,427031,2172789,54981,8588415,8241301,3837342,2670769,9480271,341445,4086895,1516414,2500336,2998590,5183509,8428662,7451305,2967646,3410327,1117589,581554,892354,9137765,4002473,1217174,1193446,6833854,8595377,8396749,885708,7512093,3039310,3453720,6410720,4320098,6365468,566769,7085282,2358548,5594453,3158928,8858726,1078856,8269871,2386638,2801106,3309000,5032125,4036862,256879,5254224,8521482,1345677,2371728,7620441,1707442,4390769,3601385,7200295,2484893,6195746,5298529,3247024,7841505,853930,492301,7213295,4925616,500778,3267405,2003250,792216,4765291,3674008,6488202,1254476,275892,5504652,8280149,3183808,2065997,8936833,5987911,7768744,5497576,2993733,2007648,2018282,160375,5175094,2670455,4888324,2918005,9352638,1728295,1615897,7342701,466899,1017308,9456834,4136636,8316082,5366337,9060836,2378133,3034109,6493472,727719,5045745,4944378,4203803,8314719,7208079,9484222,5613142,9663136,6571198,1777919,1164312,9147663,5435418,6909429,729746,8102950,1138389,6361082,6236262,8890711,1099706,5830514,9592579,2058448,1171104,6031054,7202195,6572937,379978,4446132,4881668,7244813,3145281,2306583,2083026,4438538,8593496,6020093,8955142,3365091,7041261,9009736,9481443,406839,5109817,4623613,118248,418082,239427,7098626,1925851,4394384,6729269,5423326,7847143,891337,4201006,3482591,678631,671994,529459,4671978,8684931,243608,5013121,5359446,6367077,635488,9187028,3402310,9313849,7526818,4826074,1925647,7393997,4396636,1547740,2715722,5706640,2507882,6094144,8248754,5970979,4217710,413841,7331819,4226054,2282043,9047203,3016491,2322224,5144172,960258,7872258,2073226,3635234,9522131,1082878,222068,2337929,1852459,4876288,6487585,3414729,5784658,6829480,6837877,4278190,200213,2702801,4455557,5210537,5289242,7853009,5658088,5834620,3279940,4313383,8340137,2402813,3778131,3388544,4097754,7947226,9432035,2401422,5187589,2117668,3110371,4735179,1173739,5880899,1262578,3114559,3322674,15884,1485757,4585028,3423598,1706196,787379,7345514,3448431,5066059,3917418,849479,374350,4512708,6725111,1489609,2653781,4048789,1306771,3058599,3676155,1038073,1261427,9500759,1401939,5786708,9309670,8697764,4201689,7266055,9017784,1175566,2048661,324074,5517940,4588520,5802020,4360307,2469775,2845952,3783954,4209395,6416574,6436328,2955120,4016969,3196462,4082538,1238883,7784523,5440463,1567004,89906,3510329,6778904,7661585,1030746,4986043,4173977,4711907,7983375,9113851,8499411,5473199,492553,702120,8517777,3005639,4881964,4319526,2975714,2009737,5831562,7946551,3380646,8982383,3738399,3735647,3422092,6250024,3378574,7556527,9522218,7397364,2390234,6711180,1545180,9019433,4470744,1957627,6004351,3355413,4084666,4811999,4503499,6931978,3296571,7511456,2505676,852676,9031193,4739009,6694162,8343030,571073,8499723,2647875,7999181,9001458,9185008,8477543,9546189,180455,6246072,1182222,6336252,1577610,5304664,6178716,705665,2906604,288130,8745624,5040871,4614358,8519053,2437628,7387696,3856224,6419721,6472197,6352490,5639731,8794101,1546666,6040172,5557350,2170426,7518718,8945304,1521591,8150528,4070853,6951227,3735222,2126991,5162734,6416354,1785658,2765782,3105829,8797117,1945188,4774959,2527068,6894412,9712256,3048514,8517396,838215,1969586,9211472,8516299,9199214,3405861,6020605,1904947,148585,3706807,4494403,903539,38281,6270535,3431724,1332142,4496853,9179403,5717107,936693,2781515,686018,7290808,359046,9630823,6756807,7433548,1818226,857725,9244092,5275132,4046487,2885648,6294486,7940732,4598351,5287285,5347632,4654817,4548510,6086074,8046911,3062071,5211209,7889095,980504,4420902,9461813,1539219,238016,3330287,6068795,2119502,1871496,7716872,529225,761901,5765714,8947268,7643821,5004243,9428615,9545829,4314230,1360492,3360348,5644318,5157646,9617362,4594535,1143335,6835167,4885789,8501754,9609681,2231697,7928146,4223250,8412173,1267663,5960229,313910,5089998,4671830,3880363,6935586,8417581,2214978,4605369,4246911,4347414,7344004,4822685,8736870,11493,2217740,6882283,6735262,5523487,6332543,7557671,2969154,7807730,8753003,6754132,1545909,774964,8297977,8542744,4548930,4243286,693876,9711099,4284243,513733,1044335,9039292,837423,7776286,7351678,9258743,301350,9363103,2936528,1971979,3918274,1001010,5563619,8880966,3793294,4798190,9684416,5587165,3055597,2777349,1638128,8324208,5354674,3057429,6798187,5864934,1944523,8535437,2232645,5378365,8450263,7465546,6662677,2758893,1363355,269262,6670956,2314652,3660917,5324392,4535852,968518,8594126,1511975,7576779,2440182,7057055,8424873,3966622,8358656,5731433,4019187,7619390,8766588,6093843,3588627,5347475,599431,904981,6678729,5919993,1418871,4885334,6289060,3485389,9131593,4101751,2795794,1219312,1326922,8901943,3643501,4054865,3148548,7246340,5855445,8186206,76480,9943,6086234,3953744,6653816,1552014,9533269,5025582,4955597,8914248,6853671,3776929,2471633,3093525,4013705,6195951,1862280,6885892,3841400,4684165,3657454,3006163,8633234,2470899,3323652,8803316,8140442,1788871,1913161,5411437,6186211,3793086,5999860,3742847,5289959,3735595,6432336,1888897,4567852,1873065,2040967,7434038,7198090,9078420,1564860,7395028,8179811,4021437,3249287,5261442,4569849,6407688,6318789,2417181,7572907,1958995,1572234,5880312,127084,1262513,5083664,9116303,169667,2392425,8286126,5926060,1767765,8980742,972911,6977658,2611050,172889,7137776,8466938,406283,4573431,3952153,948642,2725065,431046,2964258,8098752,9415946,6210615,3942600,3049974,8028340,1941951,4416262,2633783,3122161,134363,7851291,4179353,3472905,6172224,7818780,4782490,710528,5157383,1322280,6037333,4876468,5978709,5635235,5223927,2011773,5167771,2269866,3551116,2114032,680777,1958594,9642121,5608904,6125097,1732819,165444,8701401,7172458,7705287,128873,7788255,1994616,302876,5309596,6741427,7535781,4251295,4313150,3302894,8400654,777187,5834009,4771027,9181050,658826,2350427,524311,7845930,3746296,2078900,4458301,1648043,824828,5093098,2155921,3012734,9398702,6695127,8533881,9645809,2068875,5526192,9352006,3370136,9447464,8976015,8889013,2940579,1939243,5429384,2668464,8676631,8826120,8511138,519685,6091762,2814439,7164897,7863142,847598,7419030,7952249,2402139,7662563,2460990,9660615,7744460,6442885,7840078,3702492,1595897,5678940,6550794,6341512,7022836,882034,7415653,7838112,5366680,2711372,5612290,5030699,2602530,5342074,3289529,1532328,2725012,6043376,550736,9165883,9187041,7634904,3745814,2784873,6490964,4308778,8984471,5176398,2526189,6535507,3809682,3593120,1412837,641445,9614122,1634229,9061449,2843951,1959018,8385990,9199518,540344,5299570,1793544,5494256,1730171,3264874,1649765,2265814,5063410,2847663,4651553,8794375,714203,1656630,3684497,5253319,4549061,4313482,436560,7802764,9650770,5034216,8882026,1324711,1724514,9656631,6982370,5598140,7650017,1641339,4594383,4918939,4053168,5607139,564320,6775506,7348215,3071542,2722070,5773618,4174414,2546676,1560000,812649,931221,3238808,8924513,2870064,724995,9085703,5934119,8265360,6801066,4019010,46893,5751375,1305615,8822217,1525744,8445277,1233626,7357853,6329409,1129499,654956,2248894,8285471,1431654,7783029,5385882,3171468,7585110,277182,8638353,874070,1824111,8086125,1021623,711668,3890852,6950071,5065436,9560073,5000054,1830483,2688971,9258004,3901574,4464319,3183199,8832149,1505781,2025688,758218,7175392,7647048,4024530,9384370,8112353,2724557,638082,2765795,8514820,7496464,6217380,1854920,5466237,8857269,5803460,8095069,5553626,7798578,7313575,3679402,5956682,598919,5687622,6884308,2619584,7189573,7114985,3749716,8052569,7815355,6120844,2712442,3910800,5889798,1232211,380529,545431,1123557,1092979,932009,1577923,4506421,4513600,3017584,1303464,323542,706451,7522616,7325423,3101212,2582015,1795462,7199492,7959784,2358611,3329328,3080364,7563667,649960,9079234,5487151,5052340,1822070,2475259,3265755,122472,7338318,619446,3266451,7016159,1571828,6738211,8621128,2494686,3203262,6352187,190683,1665538,9156797,6392997,1324940,3853068,8744112,2577266,4757805,5295378,8667650,375356,5719905,2220491,3874728,282581,7239489,7932741,6222176,5647281,3879875,6193333,2725565,5251525,9028754,570013,4633060,7320434,2543425,4003101,1967575,2516013,5423056,2713282,3059970,5850603,7248545,1287675,8631917,8442151,8181153,5269612,8233364,3242745,6550865,8398131,8117868,8338934,8343342,7759565,4258321,6037675,6215166,2799996,5607017,3175906,7850004,6855361,8420153,7130658,5187465,7270598,2362700,2395985,7993303,7344162,87155,8037840,7294617,728600,4415627,3096663,8067488,8264844,5941207,1380037,5678465,2789855,1811808,7104087,9623512,7695983,5221706,7337538,5153876,5169425,3814926,3564824,7183298,8725884,3695408,3395700,6319632,4294287,7144295,4061925,9346491,927028,6650796,6603845,3837618,5336345,659153,4766685,4949771,3803998,2808516,7788252,7233836,4476096,644312,3898149,9565765,1383081,5801998,7794753,4991232,9642029,1730133,9719162,8867359,9425274,7809071,5927998,5653458,8697031,7738475,9055358,7049177,3207472,1589367,4744447,4016576,5291558,7793317,668750,2191635,6067246,9663963,4954002,9217674,2714412,1185523,6708498,9274864,1885680,5811281,8600694,3310208,8443961,9127258,9049575,3054664,1411602,4094283,4571144,9423952,4456910,2213274,4917239,814775,1422355,4731595,3996752,1252225,3364617,7527527,785216,9011769,867476,566963,7734352,5303513,7906192,6129599,5235834,7310018,7606240,8534552,2212834,600616,1274112,6850792,4889238,2953503,4605213,2765816,6445932,7013285,8089417,545187,4797452,7745049,4754191,7655591,1419190,5872387,7415693,5074269,3430670,2904492,2594130,1085696,3840257,1601324,8698885,4648316,5376463,7189234,3550585,6098954,1080434,5467932,3720828,8585887,5826220,3195993,2763510,7368502,7914944,9483823,781074,2130387,9566755,5416877,6261302,4680366,5122457,216686,7833088,856977,5161008,4840636,9001405,5819790,5913536,5133383,3921538,9180704,7367281,7205014,4021301,7609800,2689658,2179563,6236946,2172932,2732660,1683439,1565732,2257218,6371345,5185415,5291909,6714864,1351750,3306939,9469989,4136256,1285809,8630792,1243459,8318703,6826800,7266043,652879,1243465,4274005,7262199,7285664,3150154,5916404,8161982,4268150,126763,1517869,9482844,4492600,1252955,955135,2341538,7456868,5550549,4088531,9062396,4493148,3061594,9569326,5477764,8460045,8796582,2382077,5816369,1310247,2194864,4700052,1183014,8360794,5554597,4539912,5108053,3632024,8575094,5456399,5452665,1468528,1865818,4967914,7941306,7154090,6287539,7946574,6124567,4554259,1324424,6082560,4824403,5160609,4344865,536542,3203856,3551,6970980,2086618,7517067,7765528,7026303,9030647,4421950,8750289,9251204,8515260,9679184,3444650,1476933,4929652,531304,8736307,7308628,3792256,6793464,2579411,9600800,8197360,9346891,7505067,3900956,5332515,5158351,5796139,7693994,5293664,4054386,4660722,7666034,4641860,6523991,5869540,8120837,9598597,1575586,7275240,734182,7716863,8207525,4985069,4704927,2963295,4105180,1618151,9483512,8603956,4036001,5236887,3722051,7251545,9403351,6138474,5587119,6200087,6877106,7380138,6089687,6324391,9205237,7429590,4403302,5318413,3215824,5126582,2838738,6376858,7094639,1115502,9406750,3897099,9288877,8150927,5125042,4899096,854034,6663905,1683505,833018,5896538,73187,7015504,302920,7012757,9449462,4292411,9116857,6226379,9429889,4740557,111369,9282880,7411018,8920571,3831514,135178,4053611,7567418,5803162,3948033,3273810,2760584,6074836,8167088,824579,3442652,7558699,9086349,2169458,7481249,8719922,7092690,1391973,7425649,3559635,2360582,1357837,2990050,3329710,7944860,8067170,7155670,6051058,6187026,7051275,4583369,771696,7539924,3532619,8176907,3458813,5341002,1543701,2231772,5853467,2867429,6025610,8569188,6013960,1090924,1758358,7153150,3898329,8231558,4605919,1357311,8455899,6580421,940403,4042389,382365,3825349,9455817,6173398,4385093,7623950,2463820,4990948,9254026,2010904,3078409,2514952,4667463,82368,8613286,8727598,9474510,8085893,3607797,1033701,4353387,7025512,8117972,7208743,8341146,1843665,2991393,2553635,8379873,9153570,4040947,3710330,9317335,9582385,8866081,8869703,9225362,2352672,7172868,2459204,5248824,2944025,1493591,1332535,5019066,2284561,391928,489320,4277011,5311951,1781380,4578011,8429754,6221070,1377228,5469678,4350444,2719933,7928084,6611759,8120007,1069506,7354591,163743,768766,3397390,1364707,8506597,2593799,4024240,3772479,9144258,7468090,5244811,8683653,4262167,1218742,5536726,6741963,6576488,2100146,4643659,2480373,4467029,7385475,9260346,8103501,4982494,4023085,6701156,5137284,8520377,8298808,3689469,764965,7501211,8307864,1592787,4480589,1199326,4948429,2451473,5403343,8685563,690127,5262258,3316909,2811604,6857497,798144,8077741,5757249,6081086,2020003,5731792,8126782,217782,6616352,5221972,8701385,8439066,356380,2770910,3518279,8226898,7260521,6351966,5324148,549214,1425112,4707364,9321051,7287935,7605699,465498,7859195,9430047,1957418,6744519,7185998,2961707,3991305,4298711,7737332,9289297,4829141,5255750,6493047,7326969,7263863,289498,5924453,369029,8664728,2703840,9261580,472981,9176784,1024043,5392947,1767550,9428394,8838301,6002351,2183066,9352445,3340777,1243692,5655582,6812989,8924042,7524819,8255062,9057313,4940057,882212,3779178,8243511,4850504,7923611,984945,984846,6745764,1053815,4159992,730196,3200164,3441813,5703551,618662,9594261,800254,7882088,6557074,7693597,1134087,6690160,5593370,8932417,4177677,6509171,4315488,8634881,3841828,4981851,2280966,9609256,4112650,5335305,2414914,212158,9250962,8018310,8403518,6409688,8271713,7222554,3430498,2686312,4440486,8647172,8746555,1859660,4479160,913667,6559142,3511393,3989393,5927926,2177013,1884983,5726141,2671385,471387,7146097,7230698,6910129,5638446,5131140,9315865,959762,9023689,3860784,7223097,5364728,1161888,7837026,4224698,626443,7708983,2032806,4923403,7688108,1031288,5522439,6785796,1085843,721360,3831498,8864459,7046591,2014837,6816364,6388463,5234097,2212164,9696535,5335023,4648072,3958826,6227652,6636625,9182323,8539068,7512059,2255305,4445912,384743,5950997,4278846,2584144,7435480,8110191,7321986,5212063,2407581,81734,5089800,331246,4292978,3783432,5559434,1559846,1274333,8241468,3843874,5728582,4850289,5230426,7793764,5109115,6657261,4550412,8104838,7642336,7396691,9183758,8905552,6967010,929001,6542115,864046,1044360,3349955,4913480,6793352,7298366,6558564,4439235,8813847,5702120,3868305,6067373,8541426,4363303,5715433,7447939,8191198,6243729,901996,4983765,1061994,5403045,7802716,1761840,6415056,3989873,4957870,3191892,2719019,6205831,7104048,9364020,5676977,8795537,6395052,8013392,320584,3200314,862452,6476552,1637395,2112326,8045437,6637971,4313147,4815241,8056895,4384201,9149928,7245626,5171701,8675812,2886532,4762085,3822867,6525676,2937405,6565873,6094852,1979415,7339523,1367751,1223924,5586683,995274,6589041,1400723,8028810,8537683,799786,1795670,1456830,5222811,9220964,167346,4075147,1201596,8111383,2586436,2575908,1701036,3754754,1370927,728765,7793505,6373408,900982,2537395,4868419,4449471,7001705,2878730,2682686,4206761,6592925,4542741,5364113,3771803,4599224,2973895,3227997,7861220,6706907,936552,4537111,8506064,6378746,6219069,8840647,5744757,5034117,6557552,308802,7644411,255132,5964650,6177289,8486339,3157637,8036720,936468,7514097,3424078,4825497,8474,6339908,9392536,5086015,8772249,8233762,3173515,4387719,3318444,9604333,2070658,6697344,7915546,7053649,1948854,9281055,8426834,5702910,519367,2664635,7236973,5364769,371814,846738,4574501,9249693,8085338,6193050,367655,2323624,9693903,8819132,3640638,9280573,9609402,9418191,1184058,6292758,2139716,5210983,412395,3376399,1069308,7369946,2877749,3316508,550902,2353949,8266439,5719754,614873,8724656,9332562,3182157,6438944,7330025,6296763,8592527,8627889,2954179,1655406,7753088,8311017,6619182,2029205,4603558,8743853,5844293,3377381,3265554,246535,7841410,8986368,6166300,2158441,6328295,35793,8827708,194562,7606798,5771710,4670459,3067197,6405797,6231408,8679061,8448601,7111474,5070867,187105,1547162,6064663,2830080,7994614,566285,2860895,8638907,7372137,2552028,9097662,8517565,6191353,7421316,3307156,9372036,676295,4490472,7810133,7827161,2531864,733896,2384431,8022718,1081038,8903069,5788308,3705181,1199003,8563606,613146,8477214,2102553,7731800,4686480,7768683,3075629,640568,8648502,5624059,5370105,2863850,3650569,9388856,5101305,1350660,633810,173774,4579549,1889272,2998149,7742135,9688388,1287892,8716453,4027894,831980,833478,1246936,4528941,997006,2024253,4866,408492,8301603,4915650,2924920,5973187,1428576,5417915,5297522,7865093,228540,4700438,7401101,4156831,8805844,1986927,4516431,1027981,6176627,3219047,3912117,8035531,3374490,8990784,1681801,8272386,7620984,7097265,4490468,6670765,9151552,5136016,5005223,6877084,3903837,4987981,1116932,8762156,6606742,8711418,8265100,5045538,2975895,6438423,5597723,4349317,3079879,4111743,8566282,2749645,7850316,6806544,2343658,6414995,5054012,4680724,8049168,2260980,8006590,2066879,7953331,8274296,4419632,9155483,6214243,7510024,4974897,8690604,652446,7094878,8900698,903517,1789852,346421,9421975,7076448,7498858,207687,8258458,5020449,4986832,956092,4959857,8039352,4172806,9641565,3471981,5322696,3281589,970645,1880945,8054467,2781679,1228487,6181098,1137743,6804544,4169020,7793704,9716583,6730902,4637569,1837754,4736781,2036080,2269864,8349435,3654584,7833717,48029,2671768,1465206,3064658,3547943,2101187,4267631,1524598,4142762,9271335,3152762,9698101,845134,5851899,137013,8544913,3125472,2344351,8285202,1580551,6830785,4869963,8429955,8020428,467798,7193778,20437,2167640,9121096,2160333,2956396,9057575,5200784,1708388,1310666,3886936,5912048,1288429,7697161,6030461,895329,2877905,237421,5982683,1793292,4991273,3582711,4234562,7266744,354015,336510,7456037,8603780,948420,2361278,1817022,2785217,6984021,2220150,707968,1572788,8778971,4598476,7346883,1040490,5645680,3234114,6967687,6512336,3777763,8857714,9274259,3005484,7942765,6722682,3062150,576756,7208469,4576321,7376793,2615335,1177184,5586356,7279289,3991021,5226053,5710998,7381200,8352002,5229208,7953214,544897,9086662,8792664,1157814,1800709,2797096,6316387,2474742,4649222,298617,6893967,283370,8718937,2859695,3663244,2288147,7883703,7043476,662958,8579315,8695858,3450498,138446,6262282,2482028,4920060,5785810,5767141,5555326,7888296,1489359,5415713,5769682,21163,75714,6781991,282882,1357257,3380844,387174,3919481,7940712,7424611,2675966,7922053,978139,2784674,1764304,1878430,8393717,1302886,9097743,1008788,6326026,4634669,2539164,2678846,7986525,8731178,4933745,7276347,765489,3770654,7117328,1216037,3060616,900781,3066732,6736641,8593300,6762732,8546969,1199311,8538858,8444465,8539171,8364447,7443267,3693120,845758,5251048,2681045,1269753,1941884,6852851,5122502,6076572,7097779,3050463,6176606,7724179,402820,8520637,1946552,3569553,2617427,463434,3440745,2359199,4939331,5383422,5359806,4156572,7101429,8978621,7986895,1276127,8241007,7013380,7795425,3709568,2495374,6831885,1714773,3170384,2477733,2656579,7790336,5397999,3833074,7834154,6205518,2757007,7119397,6659090,6675033,2132567,1239616,4895758,338321,7014038,6875141,2921993,3230819,801463,970682,199625,2328614,7241438,991887,4447036,9095150,472486,660767,1334684,6939841,7170160,8705274,8242610,2677592,2559321,5589463,783793,3071676,3283378,6046956,3230503,1848802,530244,9226069,4664487,4948322,9593948,5103277,4726206,3865040,352632,1194934,6108614,7970778,5977939,433626,928917,5346240,7681118,106448,6623770,1430864,1818091,2866940,8387198,9217717,3643591,4464849,934137,4795457,7105719,5894116,7282722,1137180,3828916,5020574,6503522,65167,6801972,5976123,3274566,2518884,6315406,9718605,7928562,3911665,3875830,1819412,8849982,7266335,7926129,1922010,6937782,2998327,3793487,666797,6870117,599539,663483,3973648,5208186,2861159,4271316,4779536,2319935,5579459,4029626,588045,8008417,1300156,6982384,4711683,3060225,6442037,7750884,2959883,4938857,9012839,957830,1925129,7879797,4924129,2233730,5084558,8734101,1061178,8073747,6649635,3295098,4063787,7079000,7678149,8898911,7673805,1036653,5750449,9705926,6583701,9056540,7829554,755779,6207145,3953015,5809170,27072,6295210,5549882,1799333,1693249,1237643,4795380,4059030,7325307,9290771,7669771,6062370,4535141,9129980,9364151,2449265,8843746,5134281,913446,3504676,6841341,9380120,9213125,8176194,3257270,6367002,1732375,9023182,3792946,4209325,6781973,889972,9272162,6110423,1094493,3402860,4090356,8176476,8641120,8691110,5299677,9374483,8197147,1400947,2340572,7477304,4337921,2696801,581903,1360780,6383074,2764425,4415294,262258,4478564,2107785,2687040,4456758,358752,5651594,9576303,9651938,9580306,3014716,3339295,4020180,1455352,809421,3824057,337995,8769108,3794406,3960320,1560828,4190908,1646942,7963662,569745,9028047,4173439,4092468,9510820,3471728,5674456,3435738,7605535,1586212,1312186,4302188,3476052,3087097,1692461,2014536,6568765,4243069,6847459,7212493,6413630,4114051,3075374,9434482,6184717,2062231,7976556,6360372,7838401,5524796,8330848,7898496,4005183,9042514,2848310,548980,8545665,511887,8097877,2441724,4846686,7801692,3626541,2129346,5039077,9226038,2282962,9210455,6802040,9249952,4099669,4326194,874725,2286327,4105951,8992741,1108611,7068072,8223997,3857138,2334451,7765784,2860326,9678911,4632677,5488773,4484338,8279868,2205116,2585630,4414719,6120203,2104428,9223117,3097439,6511044,1535581,5741287,5991401,8483922,8164161,8352486,8604927,5209522,8093835,5800112,2748114,8356876,7629401,8255066,2996930,6515785,7967217,2584959,8065875,2828473,557096,1398754,9719750,197128,3191670,8208621,1038876,2670758,9121098,5742787,2598291,1512671,1008947,393509,7762400,8881390,7971642,5768144,3016007,9414542,6578703,7839133,7887239,5864518,897891,8993031,9665066,4909477,7083439,5904430,4736915,4693977,3679008,4332777,5510072,6461939,637578,4456326,4732107,3701724,6790568,7052031,564825,4893328,4419522,2169300,199411,7130191,1977309,7321115,747589,9430423,6158902,6386848,7965736,4783121,506484,6927906,1290377,8278433,8233808,3015716,670686,5781466,170952,7130672,5783774,1836992,5108546,53529,8070213,1800611,8856846,1730363,6012548,2661805,9563711,6248985,4278940,7269795,46127,5361550,5676981,119197,2485757,5797716,8641027,6359659,1076860,4728785,6290107,8343189,4474053,1683749,5844296,7104669,2522440,7743482,3706034,1883102,3184554,2761303,4379639,9157313,1679869,9590624,5870421,9299837,3778583,969285,2940305,9292572,656654,7427528,8886318,5011318,8336066,9633872,997458,7074729,3661911,7672437,8306035,2256762,7348070,3941272,8495755,2933849,1909969,3189697,7661962,1256741,5260080,5819935,476868,5342036,2466610,6688924,3802285,3953378,137619,5478049,7463288,9211601,8891017,1030754,8943869,8658313,7392318,5159105,7819091,6805022,6944649,5229176,3470242,7876369,8238621,6131131,8482962,7919228,713338,1348731,8145325,6724124,2892377,6290400,7592922,172680,5628418,6318767,8597169,781217,8477889,3522872,7217811,6451211,6341350,3231189,6487749,6094752,2633923,5136186,194724,5429312,3061120,3552663,8697942,7078881,2545585,6290535,2530456,7381883,1470,8093154,9697573,9461459,5825332,7239654,4134466,6419606,6136908,6648273,6615927,9521785,5639382,67848,5133274,6555652,9116680,4742701,5066253,5690107,930202,8488420,7642694,8120614,2046523,1226433,7381037,8278182,1939832,3073558,3223170,7190758,3195966,6311892,3763240,3046785,1708271,5300770,9459656,7235562,9178124,6263285,6187144,9228164,4485659,4200005,1420269,8551966,6770028,7575222,1686303,2222790,5073666,6987881,3829883,2126963,3314683,5615039,5084746,9719309,1678405,4202972,3482063,9695855,9215175,1174486,4278065,597268,8027057,9177858,5978098,9274489,6575559,1074972,1317750,1905386,8848807,3627972,3785059,6682472,4301767,3407167,9041980,2991940,3822870,3770441,2042977,7116187,6924981,3634281,2103426,2223719,2103793,5785629,8159859,8568436,7785078,3278758,1820979,2479612,4832005,751896,1405216,2077021,3251749,4172310,1320259,9533835,8479791,5339456,7422995,7291636,599056,3008013,5222263,3271911,279874,641515,6342996,2303285,9649730,5972924,8948407,5032280,4473697,5540236,260488,9633594,4013831,4563871,7035390,4491226,5651159,3660238,8513732,786457,4586954,3489418,6581682,2106861,6459919,2997863,5881215,4316611,2961469,9479319,895969,3498187,7056010,2939104,9255519,2384398,1661768,4245671,8077973,3129606,8753180,6903468,8800267,5734893,6167244,8200186,1977933,5681217,5135157,1773093,5073333,8880262,3438750,893033,1267228,6286345,6220798,7042514,412422,1650242,3127252,2421157,5608544,5130318,167689,6097508,7129222,1799342,8524928,464083,1957094,4631700,9199152,2339313,88519,3782062,3021429,8301424,419055,7410272,8133206,762953,7481722,7594765,8073971,3586119,5366149,4270119,2440140,1992188,6553356,779151,3434961,1215384,4456928,1916148,3991508,6350121,4151625,1212492,6775269,6739651,6359094,2174148,1181809,8897069,1634949,9673431,8401812,4099846,9333136,7195209,3904063,4094997,5335408,7127266,8723091,4890589,8895383,3082649,7754773,1941616,5101591,6815751,7229420,6155395,9414623,2563566,2751060,3172838,5666554,2339612,1345480,9652420,8348957,7712702,3547780,2745200,3532158,2478338,3335224,6429733,1875530,7747204,2858140,4553688,8033514,5004130,820441,6431883,2045403,3870851,1256446,4090075,9267846,7283124,9558170,2501136,292916,9068860,227482,8980091,5250568,4972463,9123456,7645974,7433845,144978,5391111,7419132,2512315,6181887,5355977,34646,7843522,6099926,7833923,2752635,682288,117529,4743496,2570500,4326004,6912601,4908732,4448415,5751548,9048600,6192704,7773170,8939472,241823,4234136,1383014,6157901,9612467,8525099,8449488,2962261,2816240,547325,447779,8688372,9030470,4975487,1044636,2144814,3858941,624194,7676194,2119831,2454609,4690267,4251868,253106,5862291,9014581,7702590,5637093,2529601,3942499,109890,1790757,4849618,6846766,744754,6141474,6908053,7383895,2591884,2344410,7458306,7625394,8992823,8215767,9724930,4148904,9285914,2171003,8564864,4249604,1526032,3411045,1447985,7176964,7952368,248401,4335033,8837473,8949741,1110357,7894844,3312419,546117,8686194,8714534,770883,2951592,4604569,4780607,9554079,2414995,3350514,8590847,1783827,8653257,1357401,6423878,7331849,9013137,8654683,588538,5056894,662008,6400001,3365715,448893,6407155,3945757,2584309,5063127,2643836,3448633,8034607,7053220,169058,4100921,1968102,7625450,861700,7190556,6451814,6593423,3197083,7908008,5350368,7964124,1265810,3392086,376548,3143722,2744494,5989685,7405890,1400240,6247368,7493639,3763348,6226667,6614836,3314055,8311171,2864379,2159233,5363956,1626378,6583177,9313492,3466042,3449329,8723096,1966919,9296371,5657255,6235902,5429261,334577,3890056,8622171,545897,7294485,7668959,7453855,6048962,1057771,8425436,3286390,613401,7011499,7409800,6094128,6400206,1501596,1056301,1599904,9019935,1450970,8459668,9154995,1075315,156691,275745,8612807,8394551,6181908,4520411,8847194,4498693,9255890,4019841,2474853,1392668,4923745,7557831,951323,9239101,6512258,2892000,4360399,2957601,12227,9691935,4337468,3667828,8843274,7978738,9349566,4926497,4293575,7157261,5609259,6647969,5945105,6012201,6122451,9476810,3613486,9719760,229287,4399600,5433037,9644376,5669700,3279859,3174418,20737,5010855,3230686,5699294,1015890,1790885,5682697,4174145,3759857,6544967,2017363,5726925,6471763,6362469,6562287,5493144,3504785,4401186,4685151,1443507,7299142,3470081,698249,4580133,1140894,3145981,8454001,828602,5482712,4293495,7993726,8608863,6483767,7449863,6703236,4956250,7069925,8783028,575779,4269502,2424268,1288225,2903758,7045842,8697934,7836770,5707026,6360905,7542395,2745519,1114753,7365042,8953192,3491790,9185349,4020106,477692,2149706,6734581,8283361,4849159,1896283,2830158,4252675,1897557,9644206,1416909,2540095,4485457,699120,2323617,5011823,3985079,4771644,1123472,1498307,3590279,9224070,3113772,5257081,7846664,7673388,5122843,3061359,4311438,7210301,1135900,7829392,9584663,7126584,3524644,4359176,3617077,9540246,3219513,3836235,3203848,3234047,4120478,3245218,5108323,7949775,92969,4869751,908581,6728668,8461065,7597683,5884921,4475677,4130789,7765319,7065115,8851339,8716409,5632694,1585213,8814065,9039365,4831468,260840,3760197,6574805,6274411,9337482,8216119,3009769,1903602,9025375,4444123,1292502,2957084,2895010,2731014,3166711,3931302,8619488,994580,793404,9216210,4480481,3756865,8099105,1561735,8252570,7876387,5875528,6841527,7188417,513412,6929908,3141834,6008122,4694566,7312459,3413028,5839193,941575,7280049,3461603,5348553,3298724,1231683,5844698,2265479,6227299,5459111,3745774,751018,9490805,5079209,9010022,4453827,78872,3234639,7931266,7168664,4600710,5674444,5372306,5374419,6363220,2094330,5474813,8546690,2689782,1826049,6259468,2254974,1752815,4236533,7165206,4193792,8800449,3877968,3359194,9245745,3193960,3153408,8289618,682343,9617717,2596649,8868737,7180321,3823990,7299248,540610,5471338,9191781,614258,2321347,4218444,6890416,8077755,6131138,9425926,8827861,7493177,5160976,5893664,2701005,8758988,3198912,6278489,5170973,4744768,6980903,7504904,41460,7080940,8388075,6900105,9540540,5456038,3249851,771570,8938549,1803253,4339629,5612191,4286786,1516836,822343,2186367,2946088,4189536,2930554,4571288,373361,5973679,8995623,7333718,7113887,65410,732037,1741829,5580620,585802,4049925,7365192,3251603,1627448,3725801,9477318,4689231,8942182,5390303,1661873,2159060,7059139,6545199,3332236,1051862,9048707,6035853,1812375,3087829,7402841,7505550,8396428,3315083,3137409,3883229,978201,3082576,3105052,3031692,1603452,55174,2047259,9162002,625112,5871075,1866043,9221662,4510665,5197587,2255433,2693499,3350030,5660852,7856434,305055,1663955,2013423,5373788,3457340,529802,6052341,6061959,736339,483808,418242,9440437,679995,607258,759388,8973801,5739714,2578583,3444779,7752808,2796616,4439238,7541015,7753034,4509418,5076182,8640088,7979063,4325248,5972767,9026014,708981,5751140,7121897,5835760,553928,6145151,8429110,354450,9299110,4217330,9610744,4823939,2482000,28603,1563751,7411616,226783,7405046,8240265,5492815,8518381,7176369,8534800,4748263,1920481,889274,6082301,5637163,3964810,1162064,2653165,189018,1894934,1215367,4991378,2871355,8554602,3229493,2781872,6597390,1742127,1600529,8517947,8451534,8690237,854947,5928243,9107564,6998249,3110318,2088017,6802710,6845802,9276289,831358,1605532,3215077,2157740,4274533,8719643,7579596,2257550,4992081,6497584,4466019,7157323,7373478,9573356,3785650,2003223,1619858,2912904,2989840,3910714,1627562,581391,8799046,4426350,886309,6007511,7031174,1784419,4848209,696652,3458359,7399113,2847284,1140381,4719361,8346684,5366113,5760355,593948,3520678,3886415,5457638,1410786,4674490,8756109,9295348,2241824,6276108,8437025,2402677,86331,1421005,2954952,2340423,7578565,2279739,8644879,6531329,2669535,5003257,7018979,2367919,2063678,4890461,1959408,9343304,9521341,2361366,5823712,5885793,5350897,5395172,6623499,9487216,3578304,504759,3354922,9441971,9027520,5681258,2206145,426918,3446179,3330607,3741952,5043848,6049282,242081,922680,7953848,5510234,1670625,999956,6117904,5237235,5500916,3351387,6881925,7305085,3052336,9267600,2576400,6622319,130982,7801916,8692106,456851,1399535,4094954,2278700,9527803,3329863,4520219,3957547,3182378,7192367,1065879,7984744,4463670,4644619,5429223,6859660,1852302,3014003,8571626,8815207,5495033,7654055,5070090,6536185,7178003,9197017,9066525,5343549,7846452,5908861,5004330,8052937,8946088,7893473,9306462,7483749,8604595,4311483,5199301,8090137,3256441,2205068,6941914,3311482,6689519,7709453,9192058,4737904,2880273,4960382,4663598,5863157,2934041,4003119,554156,3648213,5156019,7359581,8742410,9702080,6569470,3951736,2827739,3332507,5870037,7866220,8185694,1829452,5948762,2489418,9690905,1933695,5033687,2031736,8745107,7936120,6770282,1364204,4494177,1166783,3348796,7758712,4102853,1062342,1732522,5024429,7828061,9634590,8516026,5228226,1527956,3412018,7117228,7769358,7059737,4018442,9378771,1766092,7790313,2525544,1525467,3888230,355292,7140303,9492804,1256299,5361841,8857010,5903295,6365945,5244768,8149493,262564,6057121,1753083,5785195,5796926,2334705,4671737,8389475,5467341,8163474,8074566,1765353,6752103,4128968,1333936,5242428,145500,1259964,5059411,9657458,6290829,3991681,3726986,5010280,6422237,4505823,4054946,3786263,2618570,8051203,7889009,3899617,6139333,3010518,9695469,2018679,979702,760232,7406439,6200783,1968020,6839300,8822599,9519221,2978797,1381850,8286568,8419579,1635391,1448813,7525443,570993,5417626,9169218,949771,7400624,7190442,3394238,4893818,6121125,4638302,321735,8278916,8734551,8630429,5969334,3022260,6344744,4167036,4932507,3358815,6831827,7041041,443205,1964963,9484368,4062571,3959771,5794951,9222827,1407649,3765921,6393660,1433406,6686507,3919821,7749560,5807146,6301342,7446107,9350396,5695823,3630155,4878428,2844956,9278555,191115,4631743,8355301,3379449,8372680,385712,2639436,110725,6102192,5405360,9019293,2846359,3063668,3971972,2399566,4563257,385363,40717,4963823,7504934,8938759,4896803,134175,1886456,1785425,2842058,1090758,255573,7569022,4659957,5235942,8560262,6115303,1918618,8714097,8518392,8524872,739308,3255183,589848,1112400,4108290,2246182,4234122,7886638,5589094,3106556,4979169,3783169,26498,4392175,9675700,8712460,3020070,8679154,5945554,8261827,7077512,1907769,9025362,3687724,740065,4976404,995381,4237706,2034442,9281940,7502556,396966,3900813,9221270,8929133,9217903,1146503,4828434,2621718,7709238,5514908,1499317,6557611,4080627,3018985,2944101,3954844,2806891,4326352,7551579,1337786,2931731,2759449,2594889,8452797,4221392,5681971,2673292,6913650,2086852,1639356,7602792,1310504,4765127,2039940,5519307,9421900,6297063,6042518,8178960,6245824,3460564,4575967,8142496,5699433,4850819,6672891,4095967,7772535,7305594,5332464,7505073,1589277,7660932,298602,418741,8545643,1953327,1775920,2261329,6688371,675560,4631202,4839098,5250890,2230299,4920576,4100033,6335881,4089259,9476066,7056257,4972116,369133,7945120,7005468,3019482,2380461,9571059,4347319,6042267,7337084,3347080,8839090,956576,3618692,6086818,7836740,8696808,7345429,7961764,4570012,1923363,2969322,1103452,2226318,7888860,3659775,6407793,8114829,9702282,964465,9491102,5446648,530238,8898860,2566119,4106024,9616726,1910728,7962327,8126054,7863660,6775864,1766644,978981,1874903,2613896,6733302,7755428,5153601,3270704,6960910,3143556,1942889,5572669,2935335,7862221,5042710,2124402,2310674,7225172,2435635,1965959,1741309,1384679,7538209,1963843,9323244,3946855,5526505,727495,5515177,1494904,9444568,2033293,2377365,9287641,548418,2836751,4455996,5651265,5606674,5021514,7539007,7443947,2209576,8574559,3614278,2474089,4639816,2331014,7733221,1440694,1767923,4917584,2077772,7981930,8465972,4007703,4314618,4032274,7137204,1579204,9451539,2598332,1251104,1783130,2070221,8203709,5271692,1922705,7999166,9281286,5847106,4920870,503715,4592454,3232679,1042468,5391347,160402,5205218,4623206,876579,1983094,3477355,9407892,5855700,2349148,5488632,5822227,8564856,8354589,63862,7680900,4324312,29183,8659615,6652134,7773222,1021717,3909706,8616788,4777806,5832801,2620530,9048780,1968159,4419666,2072226,1678446,9397996,5749008,8278901,3695464,301260,7140105,3012595,3414292,6881354,3492978,1849995,3448912,7114949,9615982,5566490,3841610,4639737,37407,6478474,8240387,7658185,7140852,1097198,3725730,3964088,7638651,8635431,7400093,8785087,3865510,115376,9727192,1474492,719978,8573238,5696732,9008603,4605756,5154943,4107955,2130130,654229,1195807,7529606,1986763,5661957,7187538,4928429,6925180,3339898,7866824,6480414,3294678,601642,7266692,5247417,3945250,2382768,4712956,7431304,8261603,8494622,2311891,7181223,2934755,8487412,9524247,3708798,7987724,6416858,8820858,9450216,2536015,9692885,5427425,5091772,4640552,6279436,8098561,9248265,4639364,1071068,2855276,3281066,1870359,1737668,1068032,2963832,2931627,442822,9663534,5899295,7482730,5765869,8391116,9040595,6388161,9178819,1785260,35495,6369622,290534,5631799,5512009,328836,4788728,4969881,288238,5373539,6246058,4078624,5126548,6904001,675866,1038223,7350275,1532397,4767007,5088423,5986956,3904307,2254946,3430249,6824976,5393253,4160816,4574568,2635089,560872,4687682,3472707,8542865,1174253,2796399,5840182,2361553,5818555,6903644,4474632,9004450,911172,9158876,3106481,5212237,1901294,7504839,7980320,3919766,8953501,2275183,7278919,244180,3076858,2273106,2184142,7883684,6296060,9568800,6652975,692404,7454265,1170180,3046359,8689164,7043012,3994467,8724341,8760122,576748,6629287,3541772,1682709,6742302,8067508,4658606,5337893,605044,8132721,6228856,8159748,3728988,8448445,7840988,2762898,1323554,1853652,2922556,1238796,6728307,2782551,6333025,8278167,4065798,6312772,9137250,6780436,3360259,6015539,5354531,1195885,1982693,7316405,1395987,4420776,5703420,4986199,543232,1504445,7474746,4280456,8897222,4080473,8297028,4092345,3408738,419563,4798017,4499965,3768021,3555776,9590130,7373844,4652379,2631620,697417,2974733,2238596,2563614,2107006,5915567,6604440,577534,654568,2044259,5303669,4101404,1973019,2246832,3236645,6692599,7230879,8745435,3250514,466935,6758809,4916060,2893721,2157289,5470187,9364002,2811690,9724332,1458487,6456681,3584260,155363,8768554,8185437,4252431,115732,5591871,4767846,4308650,9694670,7383716,5273087,923767,7825917,3061580,6886343,2397361,5092808,5879897,1496851,1826042,7050217,183857,7843236,2373463,1945489,8084250,3923556,1630838,4262611,7723148,7189259,6503610,3790582,343804,6996598,8478329,7629083,3807206,233162,4152610,328954,336755,2126690,3592223,4555069,9110807,790539,8002105,8841248,6383087,6113825,7459677,1912511,8381524,6566977,31901,8213581,2917479,58398,6924808,2153499,465457,9633157,9365582,7547766,2551595,3119179,7445113,7043112,6689334,7551722,5128610,6839649,8343068,1097498,3305937,853713,6382788,618971,7574316,8798011,4177175,7216893,788631,9365327,9383941,4755654,8320064,2631811,6838268,9614942,6609791,7724234,9664878,3254932,7899259,6147093,2522723,4133800,7830315,8622690,5478341,5904172,2787493,7652858,3352440,5362978,1622841,2627556,4559589,827732,3797784,6854341,7482756,7737900,7222765,4532830,5614272,7797778,4765034,768860,3383074,8725026,4151910,1814914,3889838,5884830,2936309,7931546,6356748,8347133,6129200,2376701,5207033,7946284,6426428,7112719,1042308,9388367,4654388,6323657,6040609,1944414,2337338,6861372,5943239,9289025,6006334,6148842,8331986,6161208,5340002,5164203,8542882,1231931,3518622,3403729,9514874,2602865,7006059,2761297,2683362,782796,4729809,5016438,7267473,5311687,2512433,8993459,2434759,7670713,8135491,9247400,985656,4351830,4824942,9236421,6717784,4781238,1870677,4252702,2573621,6737178,4513527,916342,1084242,7174759,3716618,3158063,6819732,5437455,8324573,7049613,8701681,5801938,3989976,9037903,7272461,1999650,6598884,5999838,1393124,4902480,3194574,7242721,4112093,3162276,1251944,3008945,431815,2770317,479444,6747065,9313743,7197242,4078539,6870183,7640058,2092299,2873700,6917889,6648631,7417093,5786369,7034592,6150723,5965145,5323188,5837020,8177704,3623972,725797,9635115,1653679,7117414,870421,8213715,6841489,5969114,1388525,1657801,6366160,4060563,5407639,6349721,427418,27760,207118,512461,8322569,4074923,95419,816481,2595748,7662728,1666492,6162437,2353107,863370,8454493,2064522,5205429,4264083,5645890,9067235,7206233,7561359,3856552,8704029,4118697,3037117,5700386,7537407,3789893,3807464,5113224,392051,8437823,2621231,5676190,1923490,2215859,6494161,786767,9192399,4172636,7332760,9575162,5669626,453973,7969975,6013649,7302583,2741237,5174884,1044991,194098,7670747,9489861,4478137,7696835,1526881,8461230,9622491,8054599,1181325,5858610,4109449,7785045,1840660,8325758,350887,5057340,9677277,8975080,4939243,5020250,9310461,2288633,4727629,3469302,9543228,8570063,751535,4245395,2388917,401832,2317611,2964745,8174145,9415886,7220968,460922,6802224,122098,2843908,7265028,3478088,5232735,1305762,8853963,1147842,4247543,3026627,1384985,8653421,8652724,7477754,1018897,7098993,579640,9027378,6392374,2810581,3321013,5954234,8900265,8735336,8764672,52613,139390,9152527,8942281,8198701,5012312,9087727,2301961,1558201,4107298,71375,9284070,2234527,4186755,8137586,9489514,222396,6830582,1678241,2199024,96728,8590249,5285119,1639160,6072139,6411268,341438,6969701,8394206,9098909,4825224,1805207,9480073,4999069,9202568,7976380,597556,3288047,838474,6100424,8825594,9478859,5309949,6895504,6050238,1981825,2940028,2445625,5568949,1074027,1351802,9112336,6339589,514515,8285330,8807137,23092,5764254,4328731,1281052,5786245,4538858,7898766,7273968,5427526,3857598,7856557,2485215,5832958,2464395,951424,483175,3019243,2513532,96061,8924288,2705737,9441275,7911678,1224846,8825365,5458957,9563812,3486753,5773389,6705396,7545907,2078995,7632601,5139407,3916224,4389482,4572423,1471232,8335850,4480094,3033042,1844790,7721069,2459769,8846459,2074593,7759959,6599986,9460226,6488434,282079,1377010,377032,8352434,2773243,6111828,9633615,4250458,4930352,1715841,2284798,9690923,2435754,3529484,6374907,3024028,6519823,2485651,192012,9349303,9283460,1664478,7200249,3583618,5705857,7427836,3616911,3080549,5815869,7357999,461717,5485313,2267350,3585760,3329338,8086423,5641143,7480301,2463934,5551188,990968,2051369,6598605,3545305,746466,6601515,6152293,6107993,5402816,5845318,9410384,5551992,8772623,1860239,8112210,6997573,2402859,8151684,951803,7348116,4309674,3232665,6951476,4276390,8250676,2417666,2845096,2860448,5759781,6318501,1979866,7882889,740899,7231080,777149,4867781,1351541,8448740,6381750,4537985,6803234,6007132,9270964,1263508,2219766,2685709,9288733,2491103,2340901,6172909,6455747,6613678,9456155,2574324,7758902,2174398,625386,8314100,1687899,5926734,2887058,3368734,9402143,2438764,6201455,5790436,7152805,5920124,9059351,6350123,7092287,6940004,7688356,1325972,2531023,7051083,9637302,1257019,3280000,6767865,9222496,4764926,8057426,1329137,2020808,7113811,2128379,7482579,4250577,94592,4524608,3179116,2523111,4056657,7850352,6981616,7301170,4658746,1749790,8329808,8029478,2511951,4702344,4071066,8826757,5548815,3796294,3804151,8951819,9116862,3547732,8339209,1838442,2797455,1865571,7339978,2917850,6974325,5336087,3083957,6558708,3041116,8681670,5527027,8249065,3775104,9481555,6036598,5679495,4380409,732297,2380197,7544375,4491474,4223339,8715067,7520146,6452940,1771340,4591815,8613076,6200235,4669006,8506258,1881202,5728942,4855606,2785512,4788269,4032813,4294681,2601511,3984010,8437344,6269377,2494614,138267,2005031,1889681,4386877,606007,3019473,6137409,8327992,528775,2458206,6372246,7820300,8891230,5545292,7900847,2147697,6405598,8433808,5207955,4003757,553084,6851965,645625,3097660,657463,6298445,8234163,5539126,208406,1916627,1134714,7990786,957888,1647004,1563540,5347772,1059891,2333264,5532655,4487336,3783013,8593603,9558578,8987550,6521907,7346965,183985,1722182,7004229,5883266,3036498,6765859,2828105,1505887,2844587,220945,8302565,4506067,1794640,826479,2049574,127005,3518019,7934551,2599184,1138109,5929682,2548453,1257046,6327059,1263521,458331,2765282,2441769,2991888,9235228,6134185,2425782,8583291,7533090,3917872,3896059,9563692,462443,3473440,9433403,6902720,2656452,1661475,3531147,2854801,5741386,824483,2797082,3467324,8466972,7044335,1043043,6608563,397332,7564810,3362043,7457748,8476846,4895061,3728449,4698807,6496522,5806721,9059859,948799,529843,7303831,6872991,8239469,9526349,1152731,1966342,4485522,8254221,2615823,5742429,8413968,7876466,6648910,9365738,2773330,9460259,7784996,1878076,614980,8034052,1963750,6955887,633264,9665516,8204201,4579473,303161,4901481,4767061,603713,8861252,9236793,7406209,3609784,4963926,924601,7644337,4179653,861496,5659740,8967170,7994984,244659,6459164,4115848,7463713,4993886,2467756,5534699,7299355,5475186,1106304,4945338,1970948,9284107,2899180,7422060,3122388,2222812,2227247,8607328,9512914,7256000,1116344,4062364,807151,1079546,5634901,3984662,6706376,8521506,2501411,9218062,9719252,4311227,4229936,3716497,1915739,9092620,2884073,8798479,1990165,8630228,1465326,7056223,3673516,3349866,4859645,6275425,961171,3819124,1973037,4098424,9473729,8012413,7628428,6064770,2131830,2406184,7975068,6077018,7134526,5237902,2526211,9104020,4221845,7165126,564166,4507212,8140868,9208968,4380805,7937431,8904037,1875489,8374200,7610159,8468753,486372,4568969,2070367,2945697,4420411,4286420,2809967,750764,8932609,792401,30279,2821141,891540,2855328,5920194,6625702,6661591,3359192,7605848,8733709,9071670,5603503,8998546,7845767,2721419,7050536,2985678,283063,3365405,5534031,5694943,6485017,8869665,391284,4793182,3894888,4872373,8975833,304937,835968,4412361,8330962,5560290,2150407,8696174,1725899,8680393,2833564,988065,3847938,7873566,9069289,7465501,573889,8076417,8848071,3039924,8530003,1321438,5154907,9429471,9321738,8564039,7887454,3524082,8567419,4525470,4823853,9107181,8815358,1972990,8201790,5042769,1785185,515698,8946987,2605375,5204593,2712910,4466487,1943642,1863749,5180256,5366153,2356730,3381006,4524561,52710,354775,4458746,2066346,5886595,3764693,7228977,8843577,3515625,130553,5734631,17670,5114810,7300596,2137502,7997842,8286435,8572656,7269421,8487102,550805,5354612,2171990,414932,5002706,4133955,5104620,7082683,2076706,4837235,2443398,3239800,2420324,7685824,3992915,2893904,8629229,4109002,1097468,3962165,4708375,61679,272786,1165942,2569131,8856587,1514823,7394088,8369799,4795837,7124756,7834503,8738135,9440669,2827498,7623372,2489033,2507029,6412385,2484819,105066,9703228,6613078,1079050,6777041,6048506,6399261,4277120,155872,7821481,6449474,8695794,2894047,6585501,1108030,7465687,8913711,9200452,3636300,7975336,4833294,3852276,3879086,8918600,9658638,89335,5967220,3507600,8651273,1711081,8445562,8662658,9592826,9126709,6089345,6736129,3694729,748370,4898201,6002777,9096783,2364339,3471494,1401953,5836877,8323564,2283265,3610800,6635585,8833913,7468030,360963,6406390,6303949,6244863,2177705,8683707,1511711,7804559,2674883,2980609,7767129,1394333,8319512,1636127,5154674,1450539,5665849,8808613,3137207,8506595,1824523,1558007,1252105,2937332,5523980,688003,6428759,1542310,3239617,2501935,1259161,3470133,3057311,9407137,5567946,7914207,4334511,8317426,3751255,2935509,1575989,9218611,5945099,1032506,1029255,5932260,1936623,2317473,4050842,659214,2616318,8856168,2354307,5315214,5623198,2938048,2876457,2437084,1754548,4373718,7937479,6836547,5434542,9111910,807293,7669400,1110796,2373111,798184,5247442,5604260,4495013,9710520,432928,7433174,3153093,1487063,3171025,51291,7471286,9138064,5873191,9184408,9493931,5627700,1451162,5316704,4259872,4238083,6498966,1856149,728712,3200557,7662454,4405544,1554169,1953356,4086081,7224510,2223764,8502753,2625136,1969981,7823812,6603659,4035724,4484608,1559839,8688403,5199039,2455819,1084377,1571356,1270059,9612575,9333517,6630358,7213117,6322778,7900439,4632433,9713482,4626087,9402510,2876343,6677674,7970832,6880583,26845,2501682,1220787,1550156,6776047,5553414,4575431,7793455,5659387,8148030,31383,8572847,1984633,8202452,8278611,8580284,9506838,3783787,3790513,4747730,5017254,2854518,1501331,6168626,687486,5179421,7182868,675149,5853541,1202418,6097695,6761285,2574343,9534516,4626137,1882377,8222107,7287242,8525038,5726475,845296,2343929,7700817,7955209,6760450,6219829,1853144,3191230,5109031,3351999,1256168,2981591,5812360,5219105,777061,651991,60412,1133579,4487643,7460268,9540705,8785498,7489,8049430,8076462,7934137,551468,5886617,934668,824820,4629462,6316791,1711903,7882203,4065023,5690640,6941931,6235792,5307566,8285662,2427796,6257602,2645165,7690404,1426994,8437489,5975638,5205150,4528257,987680,523718,1518971,5740004,585117,4911940,7191399,5185286,9058083,9180165,7047112,250358,3907750,2002482,667270,956879,8560420,9134341,3053242,8208628,7944215,7410871,5763619,2093062,6021155,7917332,8439840,6992826,7619417,4412255,9383195,809376,6238034,7536281,6132492,8815795,3702342,7048259,9014611,3584332,3739583,3453909,9027098,7988595,3569401,1690657,8326839,4230587,5506952,5986730,8413275,4753680,992108,7127154,2954585,9678417,3197443,5313865,3719959,2220609,6911671,896890,7030154,7814354,7579081,9330915,1685426,890872,9189417,4991874,4912271,6819984,1394068,59651,1161380,3953768,2370189,3915876,8716468,5387174,6178960,782616,4891014,1942763,8797711,8206690,7594258,9424946,5970526,2049467,186543,7114885,1405902,8074533,3336399,9531583,7063907,5123579,5510186,4009612,7992126,4519267,685919,4531313,8577595,5748542,4611893,1820722,4088542,1763373,323909,9063496,3661785,8963441,8729719,7324865,3167641,5659621,5267042,3086447,951169,204509,1419005,187837,4582463,4955577,2857487,3220252,5457172,2020050,4771694,5775709,7563404,9268983,4256764,6632793,3266004,1417252,2554911,7406011,2668427,4762770,5201489,2134769,1686693,611414,3585599,9272641,2147033,8828805,4953706,4940451,2390080,1455945,6421138,4620897,2418074,3883378,895087,3783608,5177156,4479079,1937174,8897760,7543432,1084406,9670965,5563286,7569737,3685793,8043948,3003915,4453498,8545858,6477263,8299756,7169205,2642022,7255467,7036140,466766,5883315,7418968,459324,1939866,3970744,5887511,2168413,5023213,34418,6970085,931131,9219971,2848290,5061162,2771545,641767,1474940,1399525,1982560,1686754,5590378,4549731,3674839,6727536,2880220,9509552,2623766,7977403,7008770,4626180,8124974,1397382,8726961,3342852,6983771,5441795,1145557,5174285,1122645,8255771,9000086,8107546,3913044,531888,5371239,1068091,7787267,997320,3358606,3605227,1545734,5154927,2423929,2201761,1434655,2984505,6203829,5264914,4468653,5992343,7678268,2957549,9223563,9151287,8910627,1007724,1643571,7020905,899359,949376,2011851,2142325,3767637,8244527,3498185,5383469,4191386,1953694,976901,2518420,8156196,9437657,1873640,2764252,3204727,4755642,7631803,7737459,6550323,4067631,2621869,6531151,2924686,8560022,3010462,4380651,6348439,9605368,4115727,8366625,599290,5398631,7770638,1672994,9434880,2903403,6706999,1868171,9419822,2848244,2744965,9296008,5428487,7941567,2379370,3932091,8555243,8820530,922882,8527974,2618304,6888277,5185482,881090,5276807,5311317,948888,8588392,5440534,3464929,5184056,5266015,4918100,2302648,5015070,8570789,8762856,8761336,6306336,6259415,6382524,4593620,5876466,9558971,3364222,7916232,7197084,2831019,7375565,3692909,392403,6699081,405315,5155563,8240871,3183505,1665496,5900217,6966049,8538651,2417667,5684761,7911411,1575170,5004982,3333312,8262924,1208752,4008678,2931392,6626745,9261198,8147395,4840346,4133759,2939074,1746147,5818500,3509390,1444343,7835665,3773826,2650311,5981153,540013,3895755,6449508,9453336,7606102,4306665,6407757,1162470,5084304,6253378,6932910,6981963,52991,7133038,4697764,1644609,6610171,5357896,4961813,8220874,8365402,9532492,5714165,9474231,7265741,9665934,8865970,3492771,4025900,2504085,3198803,9266515,4838481,8131642,7840073,2282093,2489104,8729877,6596590,5302142,9151530,3301911,3852860,4157450,376727,5840601,1857961,8325699,798666,634628,8142073,4823921,8183418,7967032,650346,9225009,3218591,4536676,3358437,3105705,1929331,749789,4082807,572981,9318277,6941837,1330079,3339025,1382310,6829066,826733,4391091,2297134,5386660,4659673,5210160,2128194,8180145,5242011,5435693,5655924,5959199,8914984,659131,374570,4356532,4252948,1127287,174214,5441713,4242254,3457609,5125639,4806667,5586093,201361,3492175,8477377,5004836,7564919,8764404,6666523,9167295,4079685,2868908,5323300,796500,3986961,9601179,3960993,7988302,3887295,9590262,1575580,4374076,435312,2059478,4403743,4960096,396218,7568645,5867900,7742573,9438605,1603816,8315950,6614564,8500081,1787126,9684056,1180994,4907114,9251534,3756250,99797,7546636,3703362,2765047,1768201,3973520,1409603,2959918,8845913,9205121,1575079,1912999,543671,9358633,6879805,7380647,8524185,9505008,4321658,9146581,7206748,7290284,940970,9462094,9121527,5330082,5202257,1509710,624761,1168535,6393749,15219,6864069,8336008,4370421,9286016,5698783,5616019,4546287,3428183,759089,1775675,4280319,9173528,1632571,7992822,2016978,4275644,3824523,744132,4948345,6076507,350710,1668211,6554417,5171157,7172395,1466193,4732088,7525619,9438398,4156850,5012433,6828150,2447901,6219031,3745758,3701095,8647135,2579139,5397158,1985642,7558896,1644441,9416747,6910611,7439352,1418501,7806767,6564121,4680112,6658610,8768521,3550920,9508230,676269,6833408,6542844,8567721,6327598,3817867,3358564,3900460,1605943,8936443,458437,3334031,7533707,5993815,4159088,473659,1625256,4181133,7537488,4528669,6001688,4451604,5052444,3764239,6884421,3345898,8499409,5050166,7227006,2560795,4327148,4387406,3258901,1799006,5327805,4943006,9551375,838753,3375446,3953277,7388144,9498399,8398633,8775132,5895948,8686575,6905932,4972614,8856702,4504790,7205022,8827357,5915786,8722648,6390550,9656788,5687673,2002514,4536292,4087497,4265374,4558553,1897660,508687,841879,473120,2420983,6866924,2474959,5722074,927149,5918995,8264900,6540935,9693808,5511158,3585718,4228039,8702768,2656805,4194683,2140698,1656011,9631439,4565670,6895611,4533831,8927274,2512588,686846,3400079,168557,2228322,504460,9242071,3571753,7065722,1359786,8806072,7358860,5447865,4053457,1677739,199605,6795627,6210410,8135392,1640799,8558574,8392320,5879125,2697396,8455231,5336983,1705006,2548219,6455588,2899963,9116413,3859652,4434863,2809128,5987101,9264149,2595299,8042126,9668845,4272627,9490150,6049786,8838659,1173972,5476319,5994121,8472592,5559771,3934104,9652213,7241829,8362446,8016900,8219888,5798615,2911148,7170103,7678330,1180686,580506,4941887,4347870,7952346,2238672,7893899,1449583,9130339,3848344,7931023,1832817,2940146,1728411,9366173,3989144,1890346,3609206,9571328,4964195,3516911,4706437,4829551,5284509,4269583,4976446,6496704,5578150,3972891,3626019,7255941,8986691,3086406,8257498,1055174,5142791,7165750,1818393,6467674,6086067,3672356,2906132,1466731,1417816,1251798,6817598,3082147,5194490,6143852,6040729,6868417,7509211,7289080,2032394,3011590,1915786,131951,8182834,4440788,6543739,2813048,7933035,6263342,4147255,5137230,9382285,8012774,5199169,2242944,2206901,3868703,8193574,7230899,6466530,8745267,2781270,6187597,6380283,7883624,4977077,8726854,7536066,7284432,6769016,7627192,502315,9641196,8360816,3871177,2239065,3656750,4647828,6042975,703568,5348040,5401464,6742051,2561523,4801727,8629750,4612922,4615097,4849557,24787,382795,9623950,991565,4521101,4164344,2104518,366816,8771499,6391332,7648609,3152803,9309738,8932392,2915610,5811419,6216122,5006611,2649436,1464350,2616415,3675771,1410613,7264703,5395236,7554183,432053,5878092,2408646,7484289,2321087,7599242,330924,6876810,1672275,5232079,4291184,6566117,8754060,8661184,71060,1240577,3504700,4499326,5216871,2201316,7229568,3291226,6495480,8399491,1634744,8878977,1220173,9080242,6953261,3615944,216243,3877370,8156990,8203083,6204294,1143845,6222498,5744703,9252454,208164,6513827,4750064,5167040,8163363,180808,2478769,4201737,149423,6521887,713766,2554561,8193237,928511,8550906,7804888,9012036,8050616,7205498,901593,3577473,4823815,6014244,9717215,1292433,4569704,200671,4078509,8340233,1011169,1076925,9555053,2658850,8221556,7957614,5955564,5331635,8712094,4451659,1521250,3543763,980996,7615187,8636839,7093214,8729175,5427938,5640941,7509833,5684130,5766076,2678533,9332631,4538647,8541790,8170050,6776625,2279142,1387946,164056,708109,3356868,5695871,2311509,5399326,2958668,5341644,4900188,261757,5310646,7846803,7693166,8911074,2821428,8095300,1106552,3781153,757379,1700415,1445289,4134660,2920033,5407233,1113394,2281060,1559987,8101233,3831093,4889522,2880310,4158047,2940984,3529928,1458089,5893953,3619674,5609696,4106350,535513,4620477,6980776,5156578,5807130,1859230,8948963,4406102,8701040,685969,1445709,5739452,5554541,7115694,8241910,8516787,4814157,4277803,7074926,7178205,1634704,2474732,6198983,4072313,461412,4575463,4777179,3712800,4805479,8641528,3070496,4043982,8664465,713019,8843524,3362787,4524261,8618979,9709903,4017795,8003361,6560928,7401755,3744583,9065057,7659271,2336707,9116022,809182,7740805,2494877,1036654,696564,1517282,1955854,4284213,7906577,9511366,28185,7490487,8324922,2147986,4379282,1028276,117452,116600,5388419,4975163,9661020,4515367,9623252,4329887,5356912,6381463,3156563,5966140,9076801,1867523,170211,6467809,6563575,8067047,4119949,3085753,6006444,1386033,7246294,8416394,1560812,6958420,15993,8397532,4935921,7167605,5358457,13088,7715555,3546363,6379819,1899803,4078959,4456466,6738962,7210933,6346871,5516768,4029768,2683438,6016726,8086762,6595358,3314252,6854193,8547089,7251356,7379654,7747330,6556962,1367476,8750939,2687527,3745218,6560689,1094007,591388,7914434,8883351,6674444,2738994,6469798,6530582,4105804,7610382,7694554,4408665,2499894,2161488,9608732,3493874,7067109,9578861,9726061,9216055,9274878,9552041,692496,5679523,2149004,5980454,3620087,6036557,8287060,4756230,5775002,8398625,5633609,6268117,1115073,5358150,8250432,739481,9311432,383951,3439110,371273,636170,3341216,4798103,6460151,5634468,1220094,6328917,2440557,9038476,4432931,2738610,2505627,9023243,666744,9383804,5315141,8401163,5727442,5786395,8297570,456993,7877005,5994333,3223539,9009682,3567916,1976656,7615010,9321569,4238340,6851893,4772659,8240813,3105509,2029345,3019317,1521919,6545901,4181535,652986,2020859,2070316,5820800,4910917,1051154,4600724,7502245,5524616,152240,376913,1833721,1542916,2795951,1653795,2702050,6706420,7879746,7776331,4364186,9000395,2605830,7437335,5604293,4655640,5734099,4743125,353185,8908187,2903689,2797634,4896930,3600513,8876544,9047693,3077784,1547919,2519310,4636832,5754706,7364920,2352539,9605143,2882778,1946983,8337082,2355485,2213564,9328270,6523550,9269327,1665957,7884572,4840308,7526829,6009474,6165845,8562915,7032906,4614555,3851407,5870274,5750445,3475018,5686222,4795665,8488193,697749,5100640,502151,8769757,1530162,8614457,1944125,5768600,4986526,6424487,9634654,9039576,4809169,7711702,6308207,787252,5800194,53863,4284465,1506467,4387968,4503161,4194948,4816666,5591474,8500853,4553318,463323,369580,245381,8367850,8446894,6108586,4324507,3727843,3336372,645436,7934906,1898445,4010622,3889032,6668524,3501118,7511260,6921976,2865202,9287945,7348763,3463397,2291685,6402615,2030627,5911244,9193405,8928503,1715891,3761433,3845434,7742644,8151304,5509961,2716415,885210,780366,5326071,8816296,3850118,5266073,8957705,4631288,3793610,8415934,8487380,6780029,1523049,3340371,8632360,7055515,4908994,8458075,1068161,718730,5107334,9467906,4633556,3410072,688638,6606479,2824917,7847917,5382720,2077738,7558728,4735114,2638485,1365847,251724,1191792,3379328,1971127,5210801,1576857,9285035,2186116,8030283,1036494,1357243,942193,887856,9199710,5062258,4122240,6259941,3486931,5529219,2039163,973435,8289125,2110798,7958464,1849272,7907988,7871303,7997758,122999,2438119,3416658,3143323,5952799,7171924,7763901,4620966,6586006,6082084,2219212,2854820,4741406,4127530,6372170,8673703,5359118,754064,1323655,8658935,4042654,1113216,5524504,6767306,9494276,6992777,7042708,705592,4876168,4408116,2684717,4153307,1900718,2163412,6251343,2344340,3598792,9566039,7549293,9463207,2304616,1829396,2859443,8050124,5339811,6703158,3531233,8466367,4204548,6554133,5331825,4033243,4226313,8961149,1796150,2602464,9679025,473403,1909719,7879950,4585383,2997322,4403773,8457359,4897498,2310021,5119851,8320645,6231469,8430219,7083625,4959681,4220705,2897191,8488265,8698728,3164058,6917731,3086668,5295117,3993333,5499989,2796814,5038208,612179,3954886,930155,8297723,7670771,2923540,6180330,8170871,2543750,1693398,7978442,5354385,5762361,3208646,8744430,7477233,6303896,2998275,583244,2022215,5885134,2023917,5718341,2814938,8784336,3526743,166785,3333082,1228494,4599458,8963699,4754392,4873208,2339150,3689450,1284659,4438648,8564446,6846707,6373617,1732034,7553546,5262298,9712342,9142687,3450746,6859160,4766887,4805567,7526395,8864374,7150891,3059834,7973810,1626537,7028310,702896,7990359,4091250,581974,7644243,3105408,3261570,3136932,5611101,7399434,2898187,8893774,7511184,8324906,150628,1229819,5639599,7848713,1055506,160622,8501258,8442565,2300698,1682590,227635,349459,846141,9087631,9213519,2511385,7714054,6617441,9416353,3122719,8260316,6667254,1483076,1900594,7344964,8924170,5179258,2646845,4935710,3923,8172847,244722,6729994,5761695,8299108,6975687,7095399,6530888,1844193,6209338,4214935,9507580,5287691,8865366,4915929,5412945,3262224,7817163,4118603,8114008,7960324,9040175,6930033,7027129,2635754,3753505,3353243,7093024,2362783,750651,8902119,934627,6109643,5915818,5193974,6340667,2627567,6704271,4774319,3548678,8899003,3202564,7316579,4406839,2008928,2614607,815480,9523815,7030303,1541814,9720309,6416493,1698326,7009229,1543650,8371813,1272083,9043853,8415824,7481929,3681178,1545008,7763847,7424979,5798611,7933498,814565,8821638,1865366,8663550,1640308,2764629,5655309,4773319,1388741,5352762,2698343,892845,3143184,9060639,6570608,4601227,8400231,6913243,2362172,7811362,5418687,1955012,6040490,3054829,3440432,1688631,7802878,845073,7725747,6889824,7248587,1996193,3480462,2155090,2441507,6745107,4460373,7380907,9272634,7046997,6902145,2831203,6371796,7547734,7502073,4071478,5496429,6686890,4398197,661470,5990854,3817361,8420887,5693198,5047041,7228564,8845539,6876207,4010495,7257627,5489767,2254,910296,4475581,8485559,3419575,4712013,5770808,8892707,5894850,9555234,5202825,5841238,5678279,1865666,7257183,428430,1263321,8952989,3746309,1980427,6036114,6402172,9583495,6980910,8050504,4607732,9614810,5596918,6741311,982689,2681914,7689012,2651986,9462874,1469018,6705966,9568153,9037250,7004861,6313994,4931589,697216,5838503,7161959,5922874,1445001,1544967,9602630,2909325,9412422,7912599,7962279,3931292,6091169,6868964,6811200,4426370,3110689,9068109,5019075,4691168,3935142,8805018,8282368,781390,5032692,361120,765863,3100175,5447155,1880581,1154448,4928188,9346655,4853464,6979902,3911072,7100117,4443389,8463592,3417544,8683934,4953343,3038835,3226495,5888790,7541228,6551670,3309166,8602301,3944205,5707347,7442032,649931,3328799,877631,4210254,3365465,6885484,4693048,3569310,8322686,2889391,8874854,2995453,4104488,2325157,439091,4535415,9173968,6176879,580407,1201977,4754906,4571327,8198533,5387091,4410402,2819921,7123725,1964717,6843185,1251221,204548,6537663,4267322,9172172,5178162,1089976,78363,4164785,3724110,4867207,449342,1113106,8282527,4810181,5376544,4634107,5087530,3697327,9433379,4211329,6783246,9639601,2742081,694830,3421790,594939,4554244,8931558,576491,465872,5534112,3139601,924216,2060671,7638607,7182526,1229519,3664519,3761413,4506988,5256858,6813533,3292979,4138837,7140358,4081701,1677249,1342255,2668831,9017699,1437406,397904,4077145,9657575,4150674,7473904,109727,6213170,6661356,8874864,9257499,7174948,5496924,8850453,6782605,361726,5421976,8527643,5306564,6280122,1464215,7153277,6977663,6503429,6097985,4056443,491873,3708065,4418268,5579603,3530947,7973876,1859457,8627198,3979614,8051340,8520255,3474249,5270972,6391915,3606844,7361718,9267039,4994097,6776493,1066998,3365358,2513471,6507576,9003206,7023805,9542525,7825376,7499232,3812527,3928239,6533589,1917573,8332823,5501706,9397475,323183,4214972,4601944,2835429,3403555,1440603,6360431,7697409,782184,6389385,208645,8282172,6245740,3907112,4759832,3477601,2799917,7718610,4186147,7792677,2311518,5242385,3438490,8840202,9368588,550077,2657447,9221046,4131949,6427575,5499611,2003417,7741639,5524544,3772377,6069049,894934,4131040,5594923,1017301,4453887,6737392,8484081,5496678,1001275,4261257,8627220,7277402,1698984,4442513,4024991,7609472,5290692,2191338,7256277,4404682,6388395,8104130,6235186,8098522,3219422,3227037,9338436,520118,128048,7580177,6638625,1203227,935054,3288056,8584828,7917492,6542197,2741257,3993586,6420490,3031192,3852239,775837,430482,7959140,9057493,1699355,2490574,8570593,2986215,5667197,3948189,2464573,1638602,3032396,614912,9189314,4618659,425418,318011,5734190,6511565,6502799,4442922,6418759,8391476,8953314,7749694,2666347,899933,7543187,5646077,1745600,5279565,5608775,3249896,833061,8309757,3001963,489862,6147828,8997145,4864391,4440537,8585397,8647169,7756910,8238394,5614784,7955749,931514,2017291,6987696,1227089,5292135,2614755,2847863,254761,3171535,4768164,4876661,6747349,2893928,3246151,3200875,1096959,2399259,1331208,3648796,3160144,9236903,696636,4850284,1366621,8624483,3368245,5090861,6163980,9049039,6697816,6776425,365760,7588559,8566133,4693445,7845759,8805316,8219322,5983793,2358903,5887699,3490278,8562935,3699930,1415506,6989173,2039176,875541,9712603,1659356,6928964,335915,1027609,8249427,4186027,703349,4661877,4324968,3704274,2098406,8993305,5738392,4351853,8271961,8604544,2974174,8247302,6284642,2219048,1184086,2938906,6837180,1720020,6526281,8058439,1022837,8967744,7501978,4144260,8301140,4740080,3323021,2291341,5852571,6982382,7953404,7302862,2141901,9677737,9630078,3468460,3152978,8048428,9607395,3368740,2287000,1171450,2869153,1976434,8282405,5371491,7597744,103790,2569962,5839094,1244700,822050,125133,3883180,63785,8212180,6676025,3694844,3285830,2931543,5191209,4690644,4512789,2818539,5860679,5125446,2893352,160274,3502699,8086536,218938,7094652,8377229,7696638,4402743,9109869,1060561,9475130,7279582,7694425,4088532,6765363,623185,1328687,1904481,2394512,2278207,5582675,6780724,8105101,9114571,6462891,2117864,2150029,7146756,4187560,6341063,5420843,8455100,7886975,3149599,8709872,3745480,1547264,1306763,5238417,4768425,3601197,3462128,253588,7651126,3615010,4469835,9356357,8739454,4942978,2926145,7132918,6599563,4013194,5403455,3656034,247377,6810281,1902524,8949485,6033317,6468452,5069853,2070567,7811312,1111050,6200656,9343082,2237043,2176233,7510499,5067185,4580527,4643433,3628700,6100448,232871,7641375,5134595,4360869,6219862,3082598,1554898,4441122,149694,8643439,2612774,4144111,7405658,8258317,4148166,1073691,6650288,6813622,9271257,1454163,3177857,4949673,3715309,8578284,2072757,6447388,2276736,6573322,5159408,8233880,641911,6006306,4567103,2252493,7898427,8002399,7707526,2891951,6925904,8103493,423384,8661613,9382825,7486787,2101127,2071591,6596440,149404,6743394,201494,8020775,5491766,6084862,4390509,5937946,6357528,5076771,824697,2750534,6502229,7494489,8801281,5261760,587363,8561675,3081578,3326223,8534125,750784,4022702,7638119,8989792,6457626,6106399,7715168,3773472,7431610,9215705,5807529,8991333,2970807,312196,775009,9389529,1829725,2378609,2287862,883450,7799748,1013826,1793115,7417962,3917921,7446608,491246,4679265,7185578,3887928,9401891,7406319,4981093,6836226,8559902,9331265,1924790,8743693,2557498,7076701,4256236,6982061,2367650,7002427,4398506,8555093,9658142,375153,9455516,3259231,5416086,7680613,1649897,1791418,3881583,5930796,271084,380364,7963213,8776780,7543821,5806539,1719805,3134050,9577174,4766092,7343326,8055248,9584656,9354420,5948306,4805777,4426433,5769362,2965770,1285126,762164,590240,1145069,2846534,3069140,2426572,3927794,7925737,822948,9701795,741198,1815807,622999,3030702,3936109,8036107,7953825,6573419,1261563,4068631,3314601,2714441,2204580,8511807,1836360,7265150,700748,953729,2723926,802363};
const vector<int>Dod={1,3,5,7,11,13,17,57,89,97};
const long long stala=1316,mod=9727531;
map<int,long long>M;
long long RAND(long long a,long long b)
{
    long long wynik=rand();
    for(int i=1;i<=10;i++)
    {
        wynik=wynik*rand()+rand();
    }
    if(wynik<0){wynik*=(-1);}
    wynik%=b-a+1;
    wynik+=a;
    return wynik;
}
long long poww[63];
bool sprawdz(long long d, int w)
{
    if(w==2)
    {
        if(Ask(d)%3==0&&
           Ask(d+8)%3==0&&Ask(d+16)%3==0&&
           Ask(d+24)%3==0&&Ask(d+32)%3==0&&
           Ask(d+40)%3==0&&Ask(d+72)%3==0){return 1;}
    }
    else if(4<=w&&w<=8)
    {
        if(Ask(d)%(w+1)==0&&Ask(d+poww[w+1])%(w+1)==0&&Ask(d+poww[w+1]*2)%(w+1)==0){return 1;}
    }
    else
    {
        if(Ask(d)%(w+1)==0&&Ask(d+poww[w+1])%(w+1)==0){return 1;}
    }
    return 0;
}
int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);srand(time(0));
    poww[0]=1;for(int i=1;i<63;i++){poww[i]=poww[i-1]*2;}
    for(long long i=0;i<Y.size();i++)
    {
        M[Y[i]]=poww[32]*(2*i+1);
    }
    long long t=GetT();
    long long n=GetN();
    long long q=GetQ();
    long long c=GetC();
for(int I=1;I<=t;I++)
{
    long long d=RAND(5000000000,30000000000);
    for(int i=0;i<8;i++)
    {
        if(sprawdz(d+i,2))
        {
            d+=i;
            break;
        }
    }
    for(int i=4;i<=32;i+=2)
    {
        long long u=poww[i-2];
        if(sprawdz(d+u,i))
        {
            d+=u;
        }
        else if(sprawdz(d+u*3,i))
        {
            d+=u*3;
        }
        else if(sprawdz(d+u*5,i))
        {
            d+=u*5;
        }
        else
        {
            d+=u*7;
        }
    }
    long long w=0;
    for(int u : Dod)
    {
        w=(w*stala+Ask(d+u))%mod;
    }
    long long liczba=M[w];
    if(liczba==35987530973184)
    {
        if(Ask(d)==396){liczba=27870042783744;}
    }
    Answer(liczba-d);
}
    return 0;
}