Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase «««45678»»

Convert String to a Table using CTE Expand / Collapse
Author
Message
Posted Tuesday, December 15, 2009 8:40 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 1:03 AM
Points: 36,975, Visits: 31,492
schedde (12/15/2009)
Create Table #Id (n int)

declare @d datetime
set @d = getdate()
declare @s varchar(max)

set @s = '3903044,7569634,3947703,4397641,8304414,3889301,504543,5543592,2468890,644965,3343....
EXEC Util_ReadIdList @IdList=@s
select datediff(millisecond, @d, getdate())


Thanks, schedde. Do me just one more favor to fix the sudden huge width your post above caused. Edit it and go to the last visible character of the set statement and delete the huge number of blanks that were inserted after that to get this thread back to a normal size. Thanks.


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #834824
Posted Tuesday, December 15, 2009 8:45 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 1:03 AM
Points: 36,975, Visits: 31,492
I wondered about this... with the advent of CROSS APPLY and a well written While Loop like what Alexey Eliseev wrote on this thread, a While Loop solution looks like it beats a pure Tally table solution on full table CSV's... but I'll show you why it fools most people.

--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #834825
Posted Tuesday, December 15, 2009 9:54 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 1:03 AM
Points: 36,975, Visits: 31,492
Jeff Moden (12/15/2009)
schedde (12/15/2009)
Create Table #Id (n int)

declare @d datetime
set @d = getdate()
declare @s varchar(max)

set @s = '3903044,7569634,3947703,4397641,8304414,3889301,504543,5543592,2468890,644965,3343....
EXEC Util_ReadIdList @IdList=@s
select datediff(millisecond, @d, getdate())


Thanks, schedde. Do me just one more favor to fix the sudden huge width your post above caused. Edit it and go to the last visible character of the set statement and delete the huge number of blanks that were inserted after that to get this thread back to a normal size. Thanks.


BWAA-HAAA!!!! Never mind... that SET statement is so wide that it just confused the forum software and it only looks like there's a lot of blank space there. If you highlight the SET statement, the rest of the numbers suddenly show up.


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #834835
Posted Tuesday, December 15, 2009 10:24 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 1:03 AM
Points: 36,975, Visits: 31,492
Ok, schedde, try this and see why I don't use XML for such things...

Create Table #Id (n int)
declare @s varchar(max)
set @s = '3903044,7569634,3947703,4397641,8304414,3889301,504543,5543592,2468890,644965,3343770,5383570,440012,7339719,76014,8040031,4997070,9773149,9855323,1071378,2103257,2649769,6426595,8047712,3137660,4099409,4409020,5162970,5318462,5744243,197552,8800966,9836688,8844548,252242,3689527,9050336,6954770,2563127,2645811,2301610,622241,9554859,4693127,2887526,7288011,827052,7415771,573242,4212591,3730887,5869489,2587206,8133311,456990,2814414,847007,9325588,6967504,8730656,8423033,5321137,2078707,7189305,2611477,3487223,9499821,3987795,7260462,7964035,3500057,7668520,4626210,7552756,72369,8898160,2626446,6611941,8111801,8330984,1008036,4341644,5742910,3559633,2568287,3597869,973692,1069671,1930909,534608,1120557,4802833,9855422,4124629,8359848,1736288,9388119,8612002,9434097,716768,7229868,3308143,4089950,5521363,3036967,6190484,1232180,3138889,5596365,9672451,975527,8101909,3173187,2841140,8295477,403603,9601512,1368634,7321256,8909479,4545336,5597565,7131675,603037,7954992,3495034,6178214,6763241,89887,9718642,1639225,5048694,5064772,9832967,9443072,6184168,5486712,3189834,4804407,7692191,154574,3482074,6363571,5051199,7191045,6258786,6472593,2755414,1384828,6831792,1092942,1819196,9151993,3003191,3582314,313050,454573,1690061,8940418,8711979,4063835,6678857,3147220,9195444,8309218,2512581,5336570,9253574,3711581,8879370,3921415,945061,9157117,8960209,9062053,8591031,1621002,2664810,2067312,41460,4667642,768797,9425827,3539023,4066081,4490449,8185852,7888049,4410916,3424255,4145447,659540,8047748,7344584,2447102,9911347,1054107,9685573,8793850,466863,7407541,8398934,9485452,1302328,6231869,4189109,2096463,3563419,1994241,3494678,4379846,9787663,7520622,4924337,4662584,3004150,3230358,8151441,3338672,3951778,342318,2306372,332518,9589774,7842336,5700428,9139865,6311551,1445427,435231,6243686,6301904,2939143,9781840,4951333,9787284,9243338,3926819,2681920,6148171,299009,2041045,8461143,3676388,802040,6237347,8069518,4576435,9556536,6164315,1701311,8424821,3947943,9257924,4630274,2317495,185990,9957539,3686458,1434313,6666013,8666791,4719290,119047,8825730,6835864,5913272,2310722,8546441,1951804,1989560,8240633,2377564,2310092,3510656,6690432,6155824,8857111,7330635,926813,5034339,2445286,657137,4739937,7882633,4374752,3865562,4637519,4221997,1365553,3868678,5315391,4105041,2314591,5216507,1359730,5489894,1245742,8184975,1337612,580877,791198,3734278,3954151,7654225,153127,7681184,8951458,1202030,6370054,330307,1016590,7000996,5630395,1693766,8095994,5815908,3126401,4533411,4088208,8606609,4373119,2505072,529827,5786272,2110902,1692427,7181013,2076552,9755709,5820278,1337908,6952791,9922382,324374,6321023,626033,2103802,6468010,1852102,1133856,3891923,8306407,9758834,2279366,546402,113785,4217563,3184284,1089475,2633285,8180856,3669180,4299036,4664852,1944223,5024879,1999667,1445464,6681879,1242087,9780251,5791787,5562559,4544979,7885452,3229578,9037472,95740,7458869,3243087,7085243,8499835,1087995,9483497,7555116,7429895,6740791,4749758,4083200,8879295,7272174,2101592,5795416,5086074,1025922,1968830,9026022,5936827,9483204,5195819,3768008,1986277,8873616,5297240,122612,4321571,1367593,6486201,6685311,2031391,8085709,7444096,4605912,371811,1129797,4794582,1233793,5218856,1009205,8897612,5587901,6352697,1378695,2139070,2593110,3049317,7243572,9971121,1363309,3794180,1577048,5284214,915450,7315400,2122118,656624,6979181,1690350,6930737,1682706,9416491,1627492,2343733,6612105,5768327,9978369,2705384,4837799,1029234,3811241,5328676,3894924,1335330,6001296,9382735,4978662,6315359,2603533,9450360,7608076,671975,269407,4706129,2458634,4593928,8076588,3014229,8218160,3896421,8025999,5155924,7838464,4415743,5129314,9551723,190115,2383959,6208398,65545,8500640,8106974,3868883,9231587,4509722,8760335,9049976,1307028,6889752,1228657,9236711,9101648,4216195,8133201,3498633,6515217,4285646,7772413,3956158,8974636,8863284,7783063,5275211,4601399,3067894,6227923,525325,1716196,8615238,4953621,936775,9336746,6389026,3233662,8798893,6785945,8049877,3321633,9840448,3717015,6393799,2788272,2935274,3851696,6487185,4063486,1879929,7426357,961561,7065835,4024126,5830919,2641772,2372612,8646357,4662344,8411087,9689443,9761294,9542425,4868520,479495,8732098,8403957,443689,7967854,1145426,6772476,7580395,960249,663483,3692101,3144617,4615801,5772030,1746987,6253963,3003998,9471752,6544951,3890753,725907,8619824,8677244,3908489,9382057,9000931,9223972,933671,7346234,7624164,1252848,1806424,5457563,6396066,4723491,836852,3315964,8161487,8953383,3124873,7612414,9616729,9047992,3902291,5681987,7082988,2438541,3625937,9849799,1507791,686231,6282926,4602692,6865508,6869073,627488,1606864,1388795,8737360,4546278,5978576,8986787,1947724,7466260,3636264,7354781,9076699,3127631,676194,3944978,3082598,1882695,7293273,8520569,7735315,4185543,2502803,9665272,2602038,200226,8478708,5744663,3027978,7745173,976246,1351527,534006,1911269,3161657,8400948,1915740,9246845,57841,7817542,9003992,9086432,4623137,605363,9004393,3068646,2627973,8770434,4968990,4127808,3179501,2309857,9306931,3412206,9531325,9136348,431078,2770827,2874073,6452144,4082649,8072520,9627120,2173053,2345611,8470124,284143,2034192,6702116,7087866,2831264,1297285,6506002,9496960,1896789,8697859,8385014,3008838,2000376,3780785,7186437,5584158,8973575,9810668,2794747,5278488,1609973,5871730,6693825,9220550,9009103,1422988,2109593,8528740,5249965,8568138,3560912,9404901,9123349,1189392,6175142,4159104,5138014,7752291,8414105,860261,9172781,132438,1953043,7353864,2962489,4758751,8565034,6017317,6256624,6129482,2519222,1497766,7136503,4124888,4710151,9029832,1083715,8395189,4331816,1782308,2259468,1037001,9486652,3955962,2078587,7403961,9460348,9999110,4229764,6415226,4575708,1819182,1631397,642748,5714404,6645924,3317845,8694568,796239,1776144,722718,3634666,5858629,5677771,5879081,760099,9152687,9818230,6564073,5429850,2086888,8275731,6530768,4092455,3649996,9728668,1796386,1515990,8929856,5913379,2105697,832679,9208876,5681664,836150,5194429,8770517,4213596,5802224,9217337,2475570,3598686,3743941,8763706,8884819,8279134,4210831,3737532,6517907,9920134,6462374,5684348,1297935,5824540,1860639,4873503,9039135,6053523,5840985,3220764,9340301,1333489,9291734,1463788,6733605,6966320,4153803,8564671,8142331,7397862,8214410,4952023,947870,9270471,6256104,3473295,5253439,2754748,1838711,4646720,4643970,5368493,7777085,9670217,6537962,1972770,7097566,7056076,8076587,833524,6610695,326284,6196106,3258780,9755958,1185229,5557271,5884023,8148710,9299139,4935582,6866539,2319143,6382396,2657435,8776437,2992426,1567081,7733507,5473212,9571462,7730434,7109598,355595,3988331,5324009,904461,8353599,6641606,1666684,375619,8636393,14953,2075742,7351381,8690148,2605731,116704,6953021,5384606,3636625,565615,5027977,2363070,6634438,8432526,5093247,7871165,1201601,172060,3410761,3989627,4803762,4930600,8351612,7597285,3006571,3557987,1626508,3719599,4465046,8637070,9920594,4438707,306814,4144159,3121815,3839367,4190879,3093158,8410684,4415075,1888048,341855,1924367,532859,3617862,4525943,9069202,6313585,2658113,5367864,2352512,528017,566151,153522,9520861,1641698,3459215,4891478,823729,4588961,9597380,8929630,4480039,2133844,6849612,4234439,7781892,1923071,8909956,7386333,6083574,2102516,8256311,1892104,8502882,5811370,8059020,9067069,5283464,2985884,1214889,27527,8703084,2651443,5160197,1603680,2114282,7109782,1188799,2579699,2510252,9234113,3815491,2493488,9942401,5022583,3729679,6740125,4225736,3088398,435098,4449899,9016373,1793554,4066075,4543087,8983438,5314108,3448052,5530503,9629983,7650595,5886385,5917542,1277359,9385162,9481032,6908056,9291437,6411754,92930,8811999,4490106,613639,5629985,9299370,4186574,9116976,8786984,8156747,4104686,2491948,4138445,7755974,5936549,3049722,6964687,4744846,831988,3672753,1244147,3898348,9741885,2248326,4827977,4537101,2714261,7681574,3402840,3850990,9280783,7673270,1236964,4477868,6423914,6482475,6942918,921842,8450245,7340673,3241190,5646803,9153096,5534976,6214372,4225443,1134980,6351141,6425051,2689439,7148610,4952926,4494198,7561001,5928289,9953736,1704299,1447800,1037989,3212785,4878764,2166820,1181228,99588,6055375,2028298,4752637,1223621,9705738,3120422,7819706,1594817,1240732,3467143,4090687,7155989,9796201,1982372,4302461,900449,6018123,6257265,742532,7760476,2278118,398367,2306553,1763301,2387674,3009690,4765013,7459381,2296279,92739,9271328,4105967,4428634,2894757,9036736,59008,2459891,8266019,6465493,6004643,8392916,4391705,6141417,4082793,7442436,7301762,1745197,6021661,3912289,7633513,856122,1571082,1031791,4120432,7481169,7949493,5376745,409076,7185217,4534280,8685499,6912700,884069,6737183,7575956,2892712,5861247,5971577,2516744,5903902,3223538,2045945,1942049,3629172,8311481,4217986,8466065,8036909,8121333,8752211,4759894,1969473,3430329,2368342,2650153,4838151,2129313,2564470,9620352,1329215,3968154,5712152,4555001,9241581,9257685,5741327,4482548,1501984,8042439,6006712,3128959,4629922,1105987,8942766,2174763,9529495,9384603,24155,7059445,1647960,3075573,9602441,7649886,3321733,8746528,447229,1301213,2673626,1377936,1802872,8352738,7282053,7284096,7305939,9419569,9454463,7513966,1935055,4662407,6366555,6504889,2936793,3649723,4152412,4934769,7339926,7731136,8980024,810298,2428367,7300747,4841109,8749372,1433099,5782622,3258166,8996360,9525558,1060253,7052166,6579174,9723938,2704459,2778558,3511355,7404380,5902597,7876424,1921530,4378618,9895271,1427637,261366,8469597,2993532,4905767,572645,5133537,4884401,3849325,7468441,4282474,3194111,9602919,188095,3343826,3491852,389665,95081,2335376,5905737,4798610,2705554,458295,6106682,9715433,3533094,5049305,4997682,6373602,9466298,3790953,5529615,7782618,7142241,1090835,7720635,7901045,9459463,6356141,8319501,6128207,5291328,8435496,8461510,1693988,945900,6451184,1949532,399041,3323444,9607433,8132366,8834998,8740961,8785920,3646578,712811,3448102,5708598,149544,7803190,6252762,4092603,6248838,258368,5654391,2538425,176386,1565525,9291471,4723313,4268036,5734249,2198024,1616266,2568494,8305692,4518918,1026923,9565732,9561954,5193325,4365118,2998256,9428061,519416,7564101,7993924,4745503,264630,333174,9839595,7220145,3042263,452406,2210628,9433273,795278,8067077,4358456,5328657,8014680,9805424,7904549,3020305,3038048,5818414,2250811,935199,6374234,8303397,4151434,3833808,1841413,487405,2425799,2684210,7724461,6996957,3147963,8717902,197866,9358940,852539,2778629,510644,2702529,8869722,3986013,401109,2005206,7056813,4263469,3049029,826211,198361,7243188,1668477,7572537,6308679,6630174,9791283,5306318,8284267,5462919,6671500,6997617,4563783,4196364,8128494,7896299,4664005,3178610,2968292,7918212,9938561,6073086,5255681,3966273,6926741,5942207,1360081,274729,5786854,873830,2369394,2163957,4124710,2688323,6467152,1708849,2369275,2641253,9799530,2547828,2021530,7790642,7707217,9541301,7751692,5250372,3351669,9025527,8091730,3208686,7948992,1329806,9046642,4445764,6057590,2462964,2436955,8783768,4109475,5097767,2382785,325784,9936867,5167006,5229572,8786557,335598,5302830,1791622,3627484,4000061,3171475,8231747,6782812,9080148,3253632,9912763,2738614,3054398,7369595,5979606,4921521,2925405,1744391,8482332,1346997,1902332,7440534,9933825,3076079,6546011,1845379,6390218,930655,8479229,9694888,1555806,9824593,684773,9092165,1815560,6941919,9543651,6680427,5309635,9911006,926912,6376574,3843108,2164553,6153624,6846715,1213524,5379366,5712369,5146604,35282,6113394,2896753,6495017,3919035,9622688,6009302,3610702,4964522,182035,9173945,6960476,8262729,4111544,7792430,6934805,283139,6307794,7985767,8813902,4891239,1450884,9094965,5335337,9603013,6091689,6180683,3689163,1673249,4123052,407872,2103570,5634048,4748093,1693442,186938,4206939,7217712,133941,5577871,8604133,4227529,37927,7943486,4277558,4597774,9771679,6938738,15480,2796240,5877317,7706032,6029469,8539695,4526005,2813802,1330999,2393988,2031969,1132044,7710854,1795957,4747962,6819104,1528747,676989,3386239,7592374,5091720,848569,159748,8704382,1929742,3102577,3104485,4961246,8409534,4031411,4687353,4835030,573707,8747208,3506832,7230222,1340456,7123951,1181893,9273428,2132227,4897021,9166709,553698,5019947,4801802,4311857,5127388,9168428,2917498,2360950,3133926,8917331,2485665,9169439,492635,6984103,1799492,4096346,4475213,6720159,2760606,1276706,6532466,6310418,3124436,6338775,3933970,421077,6685870,9481612,529798,6756405,2334462,2657658,3330460,83166,2892847,9478995,9567390,690828,7519134,8648225,5776116,5788678,8172778,3854642,6928483,8597906,3368597,6601396,6382192,7422199,7601845,8780301,3596651,7893824,5751829,9963951,6812319,2607249,95141,4997985,9065779,2581900,3611107,1831620,4878963,5695005,7000876,8109768,9589326,3716509,2075994,238341,8645879,4374429,3779305,3703324,6980956,2175949,5929327,2229639,9884782,6763817,2506521,2744515,7562437,7259315,7073751,1780453,951533,9414290,3466619,3107388,3036007,9847800,7814700,1490487,7356416,2689020,7025654,6811771,5718810,7227962,5244312,4121564,2917193,6989494,8749266,5312293,9719569,7598900,8933705,5288357,7321846,7107594,8293579,1974118,4802616,8543568,4451715,1326399,2983879,5621599,6903808,1223561,4547845,6323566,5106991,7948295,5094283,1832487,232697,4108296,1080648,1097694,6833353,215561,3537477,7921907,5348568,2454420,1921075,6029167,2395759,5454304,3173990,6536205,5615705,7555545,9927843,7457908,3439781,8753970,9077626,8681095,4489792,3357419,7035606,7030520,449367,4914547,3905190,2467790,1869709,1110440,5664686,3529944,8273908,2171798,123043,1374021,7317928,4410233,3944124,7897686,2290642,9324895,7308385,6292343,734005,6161951,1965992,1508851,7390900,5549071,9131252,6086808,5595230,4948834,3618398,7340392,1166980,5695641,5663317,5271151,5830847,1098305,2279565,4987893,1035003,6988353,5744476,7096402,1775837,2213115,9256684,8467907,1776921,1282162,610665,671930,9709607,2007768,1147480,6804283,9923676,4974037,2890131,8372589,3231213,6164449,4045908,4468760,4073361,5318622,1037187,2875871,6251485,5788322,7115390,6989676,9088492,2024705,3739200,8523973,2202057,4687255,3389709,6193444,427265,1370237,7065250,7465828,2181322,3697175,7236083,2039783,1067248,6524045,8109897,8854249,3852570,2365683,4952883,9248423,7050572,9374644,328967,6211691,9192321,4122858,6899393,5485592,5206349,6974926,5372342,499265,1497575,1287332,8814073,4758331,31574,5146933,5387720,608274,876936,2658038,8434938,685922,9290485,7582080,3368414,4383094,1284136,2705980,3488280,8348998,90755,2031330,6458637,3876515,5670394,4018916,4735901,9445739,6392718,3674280,6240860,4817243,2566884,2038864,7414446,9806251,1881806,1705732,3573602,9895371,5512371,7683072,8947598,2023011,6760756,1529437,519012,4937244,9084274,8591540,1505219,6234357,888451,2715880,6317806,9417688,2560150,743000,6824184,8490202,9961827,6341094,8998383,3513504,1878608,5603777,7610893,1664704,6427969,7684538,7656662,3560438,1368240,2742047,5243149,2368472,5285542,5513558,5890282,6436425,5884175,3593275,8650609,3890872,40867,8697282,8448636,4939950,6987169,4636863,1170783,1473731,6485576,6069968,1868438,2686996,2456369,6795394,8919544,2922454,5215735,6790574,3757435,4811606,3985385,2386013,8609578,1998925,620969,8268896,1488910,5585931,8378146,9558979,7867143,762851,9261817,4943424,4164026,6875397,3937752,7857252,3765634,8571507,4628110,4742450,2329519,5654008,5580932,8858223,70980,5774123,2313847,1845104,8723591,5648696,3905297,8489905,8098229,7016567,7857347,7783914,8931733,2160866,89965,6684505,6018194,6067966,7682044,4206476,4699208,6253060,383344,9248541,413186,866311,6955589,9189187,6679132,2994266,5746955,9637222,5408128,7825140,4768604,4094056,4262484,8292318,6099568,3231344,7573512,4038265,4721686,2983507,4818412,5956688,4757948,2586859,7501615,1313113,7294681,2013740,2548708,1835525,8872394,9435850,568517,4277287,1975097,5369711,4128574,3361747,8129607,105250,3839221,6820501,1071560,1293566,549643,9981369,9019636,6651385,1564471,8214716,1916688,8984265,5421097,7092654,6606759,8534591,4420396,3319458,9578714,4126236,5522115,4368915,8880023,7924868,2341611,6741846,6994919,602402,5036977,1400519,1817537,2953945,8833541,7196582,7085344,8498239,9347399,9835546,8683527,4780188,8799876,8277363,3637984,744239,3858640,9656539,1973388,6296302,7237944,9684508,6940751,3636038,5339921,7992946,2726285,9392228,9027608,9020489,438558,7358566,7904154,4606591,1127406,7582427,3587245,7892296,4841602,3171631,4397582,2905927,4200214,199239,6155791,3203511,3585470,4252475,2253242,1422291,7365006,5056316,6178530,6067870,5842043,8610325,170051,1433824,4843113,9730967,8002368,291715,1499172,9284763,305709,7910625,6898857,7927625,8947800,9980032,3990786,444589,6198595,9366087,3660269,6217125,8988619,7505939,7454100,8936125,9577386,4755370,4425954,4531924,462303,7586995,4864524,8465121,921243,9995053,9160410,179542,6559995,4680327,2732455,8924344,1053438,3224823,7833960,7737013,1433806,6850169,4914804,9691443,3285781,3586812,650606,7962014,1102880,6364691,3788248,971009,6310627,3215951,6868456,4726179,7885991,7787432,3811098,4732273,8930245,6584544,1348744,6750316,9092865,8839684,1481011,9605695,456746,2498681,8144522,7272809,7573692,9595772,2165045,2522963,4502671,4246204,2384663,2296235,5834863,2672151,8688056,6849383,1016104,5545360,3379888,4359747,1165457,7486746,7756514,5312416,1479442,9123063,3246442,8758146,7752201,3075921,8757925,1449518,3721854,9101134,8645671,9058635,7809246,7646702,5608425,7779435,7537552,7352037,2824870,35248,5065718,2665870,4130632,700197,7965781,6047265,2652843,8943680,682322,5254672,6344354,9103565,9349192,4912910,9859977,4612505,7755247,5895122,8705519,6788384,1910941,582408,5917553,5372588,202887,9069803,6422264,7286347,1499311,1362764,6887502,8924281,1751150,8102049,7628810,4213522,3747316,1795681,8647760,9713479,7910794,5373417,9374510,2071514,1686774,1152850,566254,1686057,3470121,5409946,5841661,9512059,2757105,3058302,8556627,1858360,1403448,2385210,4514323,128596,1760712,7804940,5417498,1383032,42290,7846772,8868423,8001404,3671120,5190006,2609846,6028053,2214073,2472008,878757,5390320,9872892,7392042,1635901,1941020,2179790,207991,5357542,6117405,5879798,8461458,27026,9833283,2342591,6803917,7385654,8096659,8254105,9203558,3235347,9827956,3402336,4158721,7212410,7852847,1132880,1244216,8962215,1817219,818458,6053613,4776576,2080660,6195495,3154891,510647,784311,8747783,3729822,3814812,6025760,2277007,1908719,9009745,8025703,7032252,4948161,4559977,9877645,68127,7694807,5346155,7691967,1019265,3406656,2178231,3455297,1402369,7483082,3817442,1438858,5051551,9206675,9883298,9159446,6320700,512517,9744949,5398587,7646317,6848811,6249890,2780749,1446110,1687700,2312239,8186303,5050371,848447,6251716,9261059,4166237,3569596,7626245,6297350,3969098,8620245,5630623,7793786,1837190,492155,6591216,3471494,7977997,2021656,7588102,6420009,7708865,4370313,9360057,1154866,6678222,7090460,5542054,9862824,6504046,7377126,6613478,3965853,1281132,833677,2053656,5947812,7245111,5996464,3692974,9530008,6441405,6100524,9666912,9859908,2321492,6078486,6153096,7709435,4679203,7457965,4405161,1838338,9216536,8024137,5659705,5539229,5626752,1526570,7621132,3072386,6134054,2611137,2245494,745512,5051685,7252841,4306710,3066382,6390987,1729248,5801211,6256459,5343003,706058,6993062,4235003,590846,5502497,1668248,2203459,9518482,1011540,8274970,2899489,3639180,6231316,4758495,4062568,8948679,4664996,3222440,9132970,8491865,7534394,1261556,9906844,7701337,1710114,2895270,2594530,7876116,1788003,4586287,6406322,9159778,7184119,6268808,6657783,6575725,4190499,6722492,3326227,1939125,3193828,1827618,840799,1643514,208712,2312093,9067023,9633405,1752503,7858594,9818081,1105173,2145204,4681648,4740684,2937677,5374430,1163624,3574325,9199213,2210710,3495600,2155964,9585040,2421263,6991126,938255,8765320,3220549,7954037,6564285,1508698,5984001,5552385,5942408,4413689,6787559,3935710,5916613,7865921,38158,9480236,9368025,2255644,2793544,9403792,6519170,2303978,4326914,7543520,7647612,5485559,4501997,505578,7297093,6368799,1883026,5468603,1244497,3138119,3317823,7190703,2702640,858847,8375135,6441050,6921003,4572131,1136039,9286729,6603537,9009751,3825863,9139220,4615508,2229063,869101,7939760,4357919,5278151,4917501,6208347,8066526,2738525,7823354,9720274,8114095,8255868,7590213,3590753,8536849,1679540,5233779,6339300,6429365,8205304,7790439,3545521,510572,2196265,381546,8142864,115552,8724756,6207007,3255271,6496391,9739858,6581609,501542,2496079,1853425,6758718,2978531,4865518,1575157,4090627,526740,5470466,4304610,8612723,1048349,4747217,7245996,2648478,5149624,8816039,8670635,3376875,2336653,1715167,1603085,3253494,186153,5128320,8435180,6416290,6757088,1074574,6055149,8417507,7578533,4751870,9459102,5767916,3343595,4160970,2200724,7195916,7077476,341367,989913,9421031,7039910,8751752,3297139,1288767,7649435,9982307,5285572,6461147,5789520,9645916,9085393,6727358,8719250,9956470,9807587,9054706,7973972,8550049,881875,8626528,4422675,1317724,4701040,8520243,8210923,4652265,7567290,3148310,2505613,3715271,2135396,4260997,5383299,4093741,7978916,5853051,9639981,1087039,4814565,9409073,3288540,5990171,7058653,9980078,6141454,4234302,9412059,9488553,4668042,2374887,3601936,850202,6849491,4353371,8506345,8891740,6983982,1258982,2453787,4528071,1838256,5333884,5709708,3994080,8865527,8798978,8100832,9959005,7651888,4650475,2463941,1554404,2160082,2240148,4259491,6933142,9503638,3600690,4640763,173244,7109385,5978658,6663387,9511991,6589664,2790084,4271264,8577307,2276795,440666,6658713,7079436,597541,7022347,5037867,7269082,3613710,9648550,5080035,1758488,2116274,1255587,2284611,2942109,6812388,4827259,8659432,7705849,5241381,2964893,3679193,3368282,8136176,3594849,2512677,6154045,4121184,9460465,2469856,353707,7362618,1082467,1839206,9329821,342304,4219162,6002467,9501820,1330795,4941475,40518,4885573,4164801,5154087,4081322,9578154,1164860,5370518,484626,4207632,7173741,4103172,5556814,3441781,5848317,899935,7249251,588285,3418635,8373529,5064057,4435109,3052518,414947,2805809,3702322,7891379,4549460,4109670,3470606,4014310,5087936,2982669,4687684,2697335,7339039,3839085,1516084,8049793,480413,1620016,8662583,7919371,580182,732497,9965067,994738,8060903,1122220,8818016,2710625,869199,8210243,6465745,5450862,2169513,8651570,1101532,252793,5157435,7715327,2134709,4978789,4624268,2728037,2396878,3022013,173367,6390983,9722672,2262318,7661753,5538333,6776629,4738972,3515421,3554322,349518,9898588,2444790,746688,4636704,2044048,6007379,4327335,5085425,3764638,568875,3160864,3233417,7649938,993752,2165999,2103390,8038383,5673974,726352,4067325,8791138,3179050,613085,5550861,6639559,3022815,4666753,3250752,7371985,5589908,3701021,4204936,9989931,9212857,9915359,6957265,856966,9510386,7019950,3415348,611234,7663928,9351538,8679840,3220877,5350805,5161675,1757186,6822054,419559,3137630,8213685,8316413,8659203,2922678,184058,5936093,5251557,6328098,2685598,6103991,3548121,7366064,2590762,8842471,8991513,750933,7195535,676882,1358378,5961265,5402414,1578117,5801176,3553413,497157,4854815,7194349,9829327,679627,7183946,5778208,6169398,3832596,6827163,4264038,8986378,2781432,2354005,6736562,1762182,3756233,6807029,9956004,88583,24431,4587833,3052801,2055723,3522595,1091029,7482922,251279,8928631,4361009,1824412,792685,7797958,1119491,7969507,9449510,1027846,5295602,8878765,5813794,6612247,333056,2393471,3981538,5691844,8676249,5534119,2977277,5109630,5600848,1027456,585124,5163628,5358899,7097787,3021203,4119372,3284275,442810,656140,1062462,7385178,9297614,744599,5634482,7304558,5487765,8301745,7036503,2781171,8430346,7310628,6324642,7723323,572860,625933,3931742,2070133,9819822,592848,3975603,734358,4133732,4143223,4795644,4659016,8005407,6302884,2357157,6948682,5535285,6511607,998010,3111617,6416445,7486027,5823176,8944258,7218721,7621225,3529714,9436881,1653326,8927082,9519829,5631539,9976170,32565,1493212,1495264,5352777,5571107,5314674,33611,1722672,6491703,9825698,819184,9778232,7617800,8617227,3923355,8502578,856120,1474724,9894301,9818390,4502852,6100069,6708084,9911108,7636687,6264115,326321,5129844,8753236,8529230,3225444,8398962,9065609,6832790,9170504,2348815,2662189,5901957,6358495,1526392,661666,3743044,1003436,7651391,542422,4596586,924933,1245611,4460179,2519670,1148567,7058880,1114838,1799772,5244372,3802518,4601555,1482043,9885599,3384009,4205374,2083764,7056940,1681907,4852602,7088768,5630095,2828425,1006489,9076351,4234959,7478290,8423559,5335846,7346380,7581775,1110196,531816,3674486,8212552,6688074,8251902,1620857,4041693,1380133,3536851,5522397,2361334,3097191,6968431,3450205,9217730,7196974,8877859,645525,3429146,1377990,3243027,4998728,252642,9270543,8743942,2863231,9549647,3093386,6260378,6963595,1440545,9696021,1056634,9964841,9073479,4518108,3930670,1835250,8363349,1316722,5357987,5144833,80289,4437260,9487423,193586,4208325,2038387,8259977,2636668,8374951,2092518,2966218,3940495,7071465,7080183,1196490,8992235,7683934,2041599,1402828,6438197,9258506,5501352,5143011,8713380,6396197,5651507,1548356,721114,7008269,2387023,9048868,6714702,6666833,3386762,3715424,7419970,9941964,6899689,8470716,6246492,6310119,2116127,3360542,754781,3752972,8559068,2381399,1999893,6557791,7003121,3075123,9841842,8494188,608767,6990318,6676947,4979888,6588074,8212287,6722481,5021355,698540,7068708,7827476,8196157,2525064,3983519,5177467,3023406,7863092,1642964,4059357,8953050,1264843,4910114,9997366,1846902,5831118,2056749,4211688,3458007,4898659,5698339,5570069,5895583,4651590,3961519,1612127,4475811,3180969,9682753,2380155,2269749,8536545,418912,2476342,9452311,2267866,9202690,38869,9150436,9941384,674724,9600936,9786328,3236300,1285382,4373831,1248953,5037581,33139,7454864,8202560,3367866,8396586,5563391,1864796,1348185,1375194,4212310,3087389,96597,2303120,7260682,3851207,5326005,4021110,2995874,5892608,184973,228093,1273154,6986783,4287531,5785517,1698681,205368,9219374,5783281,2608440,5708958,7464190,1256802,3539114,6983651,9440657,3772527,4724032,1940103,1821312,5975451,5893785,9292136,2933170,6161525,9931900,2975358,655609,8903196,4061614,4770952,5709351,1808052,4433347,3117021,1349782,712375,2837957,3960359,4007811,1578102,7178134,670905,7633013,5298558,8736042,8593840,9629390,4832958,4389509,8651451,1456623,2633784,9373914,2089835,5826524,8850224,3360074,3828876,3318857,4046303,8244462,4997936,9572957,535680,6989839,6803469,9518508,2058425,220906,6643303,1196025,1775695,9786094,619025,372742,4296546,8719491,1329489,3562548,3182679,9718246,3417614,8108059,2340194,1665193,9681608,3866952,5213980,8207137,1292806,904766,8528906,7391017,8304802,4134668,5655719,5896332,8121629,2946908,2185414,4332301,4982844,2741265,6119969,5600395,1612056,5299362,2660780,3163559,77576,5497128,3780542,6559557,7282377,6861246,8109706,6468170,9724697,329007,2750617,9183700,4564819,4787419,1896527,5111348,2828240,9277092,8890050,9804708,3990500,4243537,4606147,3176524,7680855,4137380,5275404,5974453,3569397,9050535,3953487,5706085,9637651,9250019,3475584,6472274,9350700,8819442,7697090,6466136,9926389,7190615,6134186,6992202,4889550,1474344,1609609,4701441,1379100,7325732,2722572,571014,5999453,677648,4398440,8079671,780744,112339,9216698,1648723,6440073,1969415,9309181,7010717,4493610,8440864,9619480,9062489,3437351,9527938,6836409,347116,4946789,8585381,5032843,7420633,2866670,6250936,2901321,9540351,4680021,3730385,3012870,4143153,5078873,5031802,9686123,3700563,5031983,2304652,1420095,2004817,5479346,8676013,2943449,1533228,2975569,2774645,4599334,3958517,6616681,8207108,9278852,2247016,2273798,3487873,8249518,7244438,3372462,3215386,7673488,4021883,6693262,2943803,5816234,4827434,72087,8083047,3042788,8375657,3186207,9703686,6684652,868083,4586403,5069351,3828479,3630669,3275824,5335646,7456494,2294323,6856013,2446766,6085285,3786501,2124599,1681220,4143282,8221581,5210482,7383406,6651478,7691822,9251769,3933812,9417115,4805419,5773270,8725673,8452580,363404,9975350,3749293,271340,3736409,9638590,4122033,9042110,720499,6254540,220457,1987602,7306184,963410,3240679,3398237,63095,1219210,5620403,5664636,8574400,5783220,9071129,4175313,1032673,4280046,6927606,4981857,4413465,487832,1512650,7836546,2722790,7636292,1656689,2595944,59094,9240115,7834821,315670,90011,5381104,5601304,4593337,8901665,4424200,5382076,8098245,5017117,4255194,4661825,5046809,686437,6509493,7838273,4266162,5110343,4446262,1209697,5212299,9902103,8705503,9961369,2894781,4636664,4871303,2504100,3776460,7967941,2158766,8874165,807492,1455730,720523,4486980,5690133,9664031,4119204,9721220,4070380,7690227,3875374,4096806,8809277,2969116,6063471,2443582,4355547,153915,4383999,9825552,3296223,498481,580132,8343169,8766939,697058,8148009,6687626,3084266,1495353,7451994,382260,7736623,7516064,4046109,7417719,9973186,9729391,98004,8757638,8114748,8844571,2990439,3199938,2120787,3215585,5781969,1633874,5583124,8245707,3982781,7660689,3027570,4042354,665780,3443581,926346,9732825,7307106,2948828,384892,7773637,4330201,1736696,6129298,4830985,4859654,3638969,9423735,589083,7571278,3115892,6250769,6672103,2979328,1142373,3147657,3192041,3426010,2104258,6755681,3092933,1332695,9402049,6017001,9821694,5172709,6194481,2774913,7489531,5311490,7142773,5910437,8172011,9751445,7007364,296307,4280080,3845677,4815402,3254959,5917439,7536849,4663803,2485859,7066422,9178151,9326104,3357986,3033419,1658633,2073589,7446930,1652071,3558122,2140139,6013625,6996612,6054335,4626332,921058,9756686,7621696,3818617,4078540,4144519,1962604,8781252,1658594,4219218,4746169,9437180,9560253,808823,7763051,9598740,2820523,9975641,3467256,7554291,644721,5021719,7271347,2812291,1438271,1139794,2136388,7496575,481449,6455745,7115161,5471474,7591199,8027197,5165673,9154694,3185413,6397134,5245812,7529421,4372526,653491,622797,9938206,4311332,3637990,7764484,2511597,8733515,802429,9693690,2065370,4277815,4392340,7571890,6886701,8608932,9687765,6972586,4435744,4427384,3001312,2956937,8654277,8824562,5597797,7944907,7509331,7177965,6036168,1763701,4648200,6953177,9576504,6868520,7715000,9764762,9469496,8197050,6721491,9959193,8319312,3635107,38197,2931039,378675,9694450,1532014,5100299,818642,3946570,663514,7937688,4346849,5690970,3006872,3136466,5126006,8389431,744553,9676104,8852436,7539275,2769420,5673365,6643507,7996081,5791690,2434091,8069646,4000325,8099914,1373815,7995864,8052158,2241803,7752574,2832890,481394,3689343,3751507,3256479,241943,582862,2200127,3913190,9095007,5040102,1520079,7492021,8728498,3861693,5692513,2256515,7262685,8028171,8390773,9925608,3965438,29045,523740,3846430,2376087,9581042,7129321,8368715,511266,4752419,9763299,8336719,969893,3698999,19599,4440783,2555987,3073247,4603178,6993436,8874887,8795565,2659795,9571825,5831892,3569326,2456215,4814369,2231348,4068299,7725254,9521904,3177420,232089,3168445,7466871,7609387,2987260,5368570,9962171,6658630,2570589,3255453,4866262,2270352,9918284,7365714,6446913,1815357,4833725,7059552,742179,2438470,8530053,7164022,2052341,8614317,5567574,1404803,1348304,4137710,1642545,9584473,3934709,4465152,5936026,8328421,1509740,6656043,938569,5305114,9239324,5809637,7841922,4199527,7282907,2477610,9439996,9695922,2539780,7070666,2977161,1945674,6589632,7534503,7362831,120448,5340578,630073,7819829,3959544,893102,8770659,6399164,1060729,5568859,39113,1021678,1536338,9003477,5051201,7631406,6041056,5252991,2050899,2656506,6543060,6422391,2386484,453207,6646156,8971645,2387981,5258943,3292215,3652041,6634096,4878644,2921491,7752402,6987802,9947833,641445,3228646,9238939,8356771,2052095,6369336,8008937,2709423,2478475,9236933,2791437,5462559,5343609,1624905,3798844,1632762,9403009,7348334,4727627,1026442,9357741,7154921,4077816,8800744,6681590,4273938,8088445,6806412,5438879,3199509,5316111,2275625,5223410,592248,3012845,2948279,9889030,9849071,4029217,5112140,5459267,1605686,9865882,4761635,4834458,3765536,3080220,5447853,1405803,5750792,1561919,7246843,4020414,7494322,4608176,2773109,3709888,2683984,5190274,6136315,4483220,2855737,4652585,3063982,5631713,4819326,2880204,6718444,9743050,8605404,4662054,8427112,3858526,6604954,6367208,2959336,1034337,3326365,2734408,7669657,9203728,3583073,5011240,2964178,7575048,5391554,7865927,6385546,3785355,8395427,3825556,655041,3523602,4017980,1149016,2382197,2353498,7151082,4013808,1052113,2642773,1595972,7817807,9695281,2987874,9517366,9713989,7830834,311665,7180230,3868050,9634378,6864510,4004750,2514040,9375625,8769058,8208274,9181032,7145904,7295903,4716524,7855693,623215,8900517,6000487,2101034,7835656,1737632,5250232,5915833,7960478,8535891,8390213,3120900,9159646,2349998,163079,2409796,4868611,6368379,8665216,4996531,7955172,5330710,1728945,2238101,2015781,5893395,8556747,5449834,2891088,1222816,6958765,7259217,3629642,1179123,546044,177610,9474277,8432315,3801777,9350941,6214342,49083,569584,5231721,990356,1165582,8413430,9531019,2684776,6527383,7508485,7042932,7617766,2189207,5362675,9943480,7599281,1377529,7924339,2827573,7632603,5830439,8611747,1753270,7951498,8481179,3557507,9198662,1708744,237241,6268405,5963885,7533106,3467809,8421265,1697234,9921687,7010064,8895808,4330976,6258408,1906133,579417,9779299,1182191,4150928,9737748,8011210,2551799,5287632,7074356,494868,6320889,3266837,1954171,3898904,4757426,8579595,9463490,5467872,9323130,1089748,5298838,1036765,9456277,4363127,6980451,6592068,4870570,6576428,1089664,1188422,563703,951779,1131364,8722896,9946089,6349167,864795,218927,7868047,3820562,6830348,6592992,9909318,5643721,7280943,9859458,2664293,4772407,809254,7637165,1964742,3492690,4204740,5570913,1614060,4247954,4984573,5900653,5613539,8844825,3051224,9252510,5709374,957503,1550522,3301851,1388535,2792033,1239734,3955205,9219616,5954531,7270,284961,6425026,7017780,2297593,3986968,5624388,7832931,9775315,8772809,7007397,1039180,5982651,9088217,7381418,2137895,1123798,9415539,462423,7089497,9281304,3743177,1676711,4665229,1761967,5193466,1796179,5704630,7287413,8937849,4390274,9582213,6405324,9918662,1332563,6119557,8510308,153972,2787321,8736211,7572358,5090065,3796040,3681178,1670699,765201,7658710,3280527,8911896,6286147,9168069,6927920,2601018,1451948,8572009,6887773,4751307,4132723,2869918,629888,4355767,3568707,6929473,9713707,1043795,7650355,3459379,9404963,2709825,3964571,4360054,9774628,6112072,1473470,4536441,9424581,9991910,5299262,8832038,550059,8751461,7998223,5073469,9284975,7187670,4315433,8660663,5492920,1630260,9952351,2513093,2507414,9882251,8905963,9592923,9572052,4514826,9385134,8810484,3303235,5289209,1379163,686825,1207353,7390975,6051583,5860846,1551214,3050962,3501951,9932705,7487390,7793294,5335839,47086,2924521,1959186,7531163,5500516,7592834,1147967,4802178,9046981,7809613,140325,538499,9384946,1343411,7937069,6210072,5000523,7688961,7967813,4228016,548742,8306738,5916067,927565,4139191,9457947,4690959,9932905,7046138,2763229,3301275,4449229,537351,2846799,4329236,5301384,2864534,9796765,2715515,1520740,5747017,3444372,5506339,2574328,216415,3476980,9520548,9942040,4439740,280024,6289355,9714284,2282121,7948312,3110500,6014657,1014529,8268549,5927181,6271422,5698329,7052073,6550872,1867370,3182994,9623602,9241429,1828698,4121447,7968007,5168324,9391460,1107755,8142998,388573,6041468,1042557,739126,9969191,5713784,1514897,1191926,4622924,8011527,4890451,7397026,5543491,4386472,7322649,2137761,8705492,7910524,9419311,1907051,4550106,4438824,685877,3443588,6038175,4961919,4812653,5758550,800909,4069145,6909405,1572438,7973028,8151391,3704438,3876007,697387,1593370,5822845,6033536,3221536,8076229,4050952,788201,1452505,7823886,983623,7281939,429369,8720781,6738055,8164344,8356674,8499227,9714836,1501787,258488,9891410,2716565,6353867,2715096,7347821,3187879,6437394,7161183,3656086,8520899,8860984,867304,4331799,4003804,4533738,3224576,124185,8139881,7157812,5408605,1166142,4336227,9213941,8801432,2276381,1960095,2741599,2672431,8949368,9160593,5158144,8726025,6111869,187732,7499592,2504243,1384842,4701210,7414033,6866430,9859139,56123,6488824,6432277,5210035,4266509,7015126,4129298,9121694,863923,5683513,3960695,9338922,2873453,3576762,8089554,2674635,3070617,5720203,7450104,8622877,6578943,2353835,6333801,1268353,9008965,7163173,8646289,456147,9259661,1590862,6614240,9878138,3296616,9435194,6019494,1006217,3878668,4486708,1742401,8133165,9921476,4763373,1668974,6575465,3652464,9275965,9935637,2119161,7284560,7650031,8000129,7499517,5748781,2446188,3641452,8916242,7381197,3173510,379652,1714400,8834943,6149807,5979312,7922796,6451861,4705096,8070241,5153228,2573897,2618366,3562530,3405522,7083502,3242192,9293174,7597941,1218708,3328485,1822793,4224513,5084422,2413029,2655945,9605696,2896124,7939249,9311035,7232910,5793245,3053891,6784106,2697667,8680748,3099967,3805562,943459,678179,8221108,6627063,7341072,9807902,6931139,7371914,986628,4271909,1733230,5781418,428959,4602457,2151564,9667854,1762471,5757270,6378649,5138636,7725880,5379686,4666196,288123,9828186,4698624,9113892,5689021,3392179,3962481,4637421,2966982,4138003,7874516,1881094,7002419,2453888,1576736,2208874,9683140,890858,9636919,37768,5288961,6144019,457800,8846332,2716474,9867650,7573442,2124938,8649734,4452397,4326628,5098346,942921,4044614,8311745,4383889,2590609,8251512,2943290,535199,221143,4668892,5393113,5168771,8882804,1184041,5807839,4637685,8223827,404158,5318924,2902351,9560393,687753,3364985,4190561,7480404,523665,2883580,5155142,64182,8332874,4747955,4609157,4180030,1117859,9122196,2869588,8657211,7538212,8626316,309393,534630,9221077,1230233,4600155,3949216,2710972,7573047,2664909,2235510,900759,5183943,2609905,8298384,498410,6864033,3330630,3139153,2194451,1581053,6670332,3934687,8594913,5906191,539424,4159836,581298,9437910,3275624,7514775,3614216,6201635,4123244,5199986,9719646,2220568,1141179,7405361,6524359,107039,4981036,8509140,444124,6663142,7533027,8207016,3350544,2084680,1417679,1866979,5596344,847751,6677741,9382549,7840411,7348196,7438993,11307,3925671,1447279,3259683,9358356,7446786,5795885,6500329,5167665,6275053,3097965,4081503,602618,9328148,7112518,9977186,9552331,3039373,6365693,4187377,2385548,8220932,154583,5129032,4846952,207982,2851622,7732955,4994921,9356417,364386,8434305,1417980,1773960,2688419,9639892,9342572,5678821,4275260,9932334,9646336,4606884,993800,155596,1921075,3931585,2056678,9527096,21585,9277782,5754191,1185200,4172,2665225,9459423,8280951,1751255,8915500,8202795,4440378,5646297,3349884,6553060,9556000,6599415,2290263,6465100,9057774,2828777,1350137,4087072,5044578,1787822,8449630,7836700,9119899,1692844,803833,2691804,2635688,7516979,4529079,9997848,3043936,7143769,9095129,5934764,2390292,7980713,6321302,8462895,3801045,555328,9468922,9043564,8766168,6021435,1654250,9942777,1369154,5558086,7079684,4844645,8674682,2868755,2558750,389664,4227138,5711649,8282882,5753193,6686741,1733634,1961307,6638021,7978157,6910994,4233632,7195013,533398,8350551,1130385,5171597,1446801,4361588,2818154,7246162,431274,8422957,6615746,1550812,3336839,1441433,9092076,6761466,2782559,617300,924351,367217,984814,1099402,7888469,5911778,1762378,3579753,8047672,632410,1159568,8293499,7843799,3829392,7883327,2307155,1569578,8023846,2078918,9042097,6502401,3699011,696809,9053265,6944382,6792361,6523825,8479516,8966937,6021206,4232035,5615646,7457977,9924782,7766372,4848469,1641806,2826758,46217,6922804,1145393,3607891,4730191,5746394,9325452,6815558,2036994,134,4615738,4394928,7007856,1082669,1247264,2834099,779631,9995535,9929252,8135769,341325,2762422,1860518,7587816,5678950,1467715,6113563,613833,9567918,8552403,5944586,2017618,9985585,6681914,1092929,6656533,6876322,8810368,2202057,8836613,6579276,7031040,9611119,4992143,4500293,7945383,4351427,4377258,263295,1518056,1228292,6822236,5296152,3986311,8934244,6543589,2920463,7282464,7835341,9529707,4670880,310416,7962387,3946231,4249940,2676209,2673967,5250453,6962447,6642240,8741464,8769575,9852590,2412073,5125766,797473,333353,7144588,4633836,3517751,5313472,6185286,4943619,7055760,7713712,8751620,8759933,2696388,8163377,173250,5066817,4842755,7598881,9699428,2905095,1045206,2918295,5138327,2028880,3527317,4314519,546064,5380270,164045,6741962,1307734,5625018,9111964,7625695,203977,1091599,5891007,3532771,7620550,3807421,5032023,4096131,8513361,9855064,5048771,7003870,5778081,4709920,1064780,5429505,5169727,5424649,8792201,4341643,1963640,483859,7445092,9119309,2174746,7322553,3244661,2706716,5356420,3367752,8803731,1013809,4249065,159818,9906316,5350823,8697040,426791,7128503,234827,3493676,2407869,3232192,4046223,233798,6348775,5412722,1599304,7435977,9145901,3249824,2154217,2539342,885302,3744888,4561843,1383503,798948,525770,2461032,4618577,4894003,5021780,2468178,7436200,333981,7554754,3798518,9124250,292064,7248394,5878346,410432,9631260,4400182,1176051,7863858,7220979,7556223,658367,5873010,7013358,226770,1924986,5737413,1290925,5294424,8405437,4845892,9484695,4845399,9924293,7687707,848045,2888811,4454075,5482814,1627432,3942144,1959332,7296544,6359199,1357859,2668336,499955,590251,5211697,8704134,2775749,4820487,7437204,355246,6329717,1387320,8712215,2947933,4983505,9169980,5034507,6179251,6784381,7231904,646580,3867038,1786509,6255494,1316063,1330457,5162059,3559842,351679,704965,448389,7487381,8687206,6614118,8469176,5452366,8834323,9294017,5606306,7649222,3145459,5571621,1136291,9385266,2592105,5399149,7775640,7330646,2541253,5950490,3440230,6597769,5642341,2715744,8322061,280392,4042728,3745426,9618674,4093001,1650028,771984,1550071,4759505,4395975,4141025,3991205,1083375,9066280,7203178,7922797,7928443,7549267,7276103,4514717,5512478,9982674,1543498,3384648,682727,8770111,4696152,3402238,9946479,3033124,1872647,5349524,3716116,9901043,5580445,5018226,8830956,4231000,3697406,2368521,2149509,7416828,6741722,188912,3676835,5233891,3944146,5872330,8230882,1537269,3447042,5584860,759730,668548,6052093,5173639,4969459,4117633,7477372,4352776,6887783,7104822,5086710,2229034,8433025,7359096,1899342,4702123,1844232,5605342,5410248,3140660,2865132,9023926,4164922,9393164,7251588,988470,1290156,3474363,3393768,8989653,4257039,9234354,5768403,6132384,7812656,3788241,3781924,5387855,4978406,8375198,3020631,2931364,5224820,9241228,9116737,8633934,8338375,1063076,9781780,788161,8764083,424158,580098,2564706,3198529,510936,8321558,4735986,8927961,6883984,4412,8838641,7123857,3937960,2292371,1657169,1370412,4202539,676711,8675399,7476331,6882573,8851913,7331731,4041403,7926680,9874039,3937165,2309066,4718943,7294746,7150587,3924648,4284986,6464363,9856373,8529754,5687592,2929891,2651872,5178555,8537141,3686398,8714262,234343,7222756,2337964,98839,2364111,8372637,5036278,3050759,8112730,3132341,2959582,4423172,4338899,5496930,3988787,9351598,6521042,568356,4057064,7722547,4791641,5816820,5027566,7331031,8400861,9502807,9494894,9053721,5920305,9037226,6565097,6135330,6075645,7367522,1495616,6120182,5322197,3912254,5338218,4513044,6013312,2948644,9409234,1643171,6803613,7046992,550812,9400620,8434707,834036,9169673,4920107,3856390,2902452,4911818,6776793,1778152,4263043,6537918,8611062,5217151,7092026,2544792,1156098,9301774,6621986,5688687,6783109,2916327,1824900,7495085,2486855,8239399,6836463,8127619,8329127,9107675,9098974,7812411,7122435,5105997,6429479,6718380,968179,522961,5725568,7719870,5551713,8692636,3659492,4737975,4245825,5643685,635100,9033082,6178856,2638609,2021001,6547107,1234072,687720,8646612,4428619,4353361,1088026,8178124,8935464,9500738,8353294,2934356,7022658,4463087,7958618,2781428,8478249,3470861,3348984,4249264,9303467,2123351,3947552,6422474,9294760,3444028,4927565,6029035,7380717,7320060,7502179,5575184,9561616,951431,7013448,4916650,7573630,4041479,6409706,7195294,1773470,654471,8937002,4068734,3212543,929148,7053672,329129,7718874,3273357,2231282,9628067,1314190,652522,2354026,6352628,6274009,3557445,5902267,1086256,3470063,9169016,9372928,5896812,7621944,3872398,5623927,6728154,8154045,5623441,7481034,3851310,1199901,1078050,7409077,4266480,5865627,9216976,6239239,4735607,1437269,2796371,4946099,157944,8986674,5847323,2445436,9236795,4667390,1540885,814699,4171163,6838557,2548492,1744978,3522398,4998333,1194748,8013363,8452487,8261395,5919644,8064259,7408834,7362987,746296,3710726,4035995,1937776,5224640,9516043,9852169,786223,785848,6236388,209330,5055934,5447719,2318929,7693177,3793455,2998294,843854,2401768,3267281,5725930,909851,8865736,773034,2566886,3881663,2130883,6645176,6754699,8937185,2832132,8586990,2915529,2846941,2396152,2581405,918006,1819463,3986036,1594954,1780731,4353376,1287852,9578244,5231272,9778449,7226969,7767043,3978944,6965190,3540452,6686832,6586604,8975918,3934744,253404,8256411,6118689,3661276,1569027,8334686,4786512,4838445,9100348,7428528,8314986,6537792,5984580,8136924,4541,2684782,5233351,853382,100408,422414,5661169,2859995,3500235,2541349,5473814,2064187,3570897,6763952,9212770,9592591,8920617,4387740,4952329,5510398,6765186,5003648,6523668,1986911,9707582,4414196,7522027,4490557,5919729,5868621,4939482,9942635,1986352,8609533,517798,9208275,3173462,9509956,2353414,6846332,9171451,8749334,7954973,4317092,1754855,4790051,9429388,4524145,1581735,7462895,6023295,92891,4577834,6623624,7641606,6419434,6652852,4936889,7595671,8449315,866006,7601832,3558320,324009,5114679,5762595,3406124,9462842,1667806,4362080,5096724,6612597,869147,1830005,2673842,1945764,3786756,1310328,8055548,3534324,6946030,5308464,1694922,5549211,3917717,4658331,8342562,9425053,5445994,2215904,3111304,1017311,7988254,4149269,818214,2086695,5748582,8859906,204504,2438459,3044708,7577060,1917749,4271488,9455895,8631003,7264980,8292757,3373630,4309835,8415113,2246916,612551,7056440,4708405,19604,427453,1152003,106879,8452339,1401295,60881,2289891,4959355,138099,535687,6685466,4403960,3870254,3575281,3917853,4589215,2626733,1214804,6348409,4471516,6759168,2215447,9590264,5220373,656352,493,6223687,5698654,2501970,2365683,9562287,3412220,1753538,4024291,7028935,4330060,106042,741492,8729650,8772399,6254288,8468229,5716430,2722828,3514388,6334814,4463528,6681783,8350539,8738811,2085292,5546202,5445642,6122819,1382368,6286718,4441224,3327783,9027055,3133584,4209458,6289830,1290000,1716973,1430209,8005791,8997787,9985028,8012323,1180093,418889,8659618,8750521,2511944,3258438,3763681,2598477,6585436,1234465,7803908,3262661,6976268,4893293,8537499,5504476,2119900,8344615,1971395,4444362,4890757,8079822,5754796,5637038,276735,4455247,9596142,5926430,7769280,6782720,1722361,8927013,6716682,7143168,3811287,6952976,2830878,849239,7939311,4400816,4962322,4624290,300321,3784290,607305,9647240,5245395,6476926,1751567,8992512,9283554,8347861,4309646,8460864,4715564,5121768,824063,8436949,9334543,8281850,3624398,656212,8052162,5052010,9451711,1455639,1668992,9044262,8009179,9044711,1759872,1395517,4373160,8818671,6124695,6089260,6432979,6446526,1335983,1336052,6814034,5928574,4343872,3999465,6919830,2665630,2346296,8181784,6975412,3195570,7294481,6521207,8820432,2663577,6586332,9841122,8171761,1979032,7645303,9018827,4547591,7890953,3212119,6791016,6479924,3729190,3348347,171163,1652007,222167,892303,8365833,4640564,6124550,1458019,4747480,6628443,4195458,2730046,3797723,6435500,1462196,2568410,1966039,9943428,962497,2199197,6791677,9563138,2340746,3078961,680999,4046275,1741101,5715913,1136076,4183631,713754,3816820,7947752,1212154,6544404,1209857,9513642,1576277,5805201,7102991,922334,3558092,3842103,9461780,214644,5745359,5630931,1432703,5422687,1519873,5521394,8720968,9294013,4797395,7273698,9374296,8212638,8769822,5208532,8014247,8278107,8133114,2350276,7250428,8132595,3160224,9250967,9397545,5411241,7661016,5230918,8466905,5961821,7090183,1130717,4312210,2264414,4751344,2236314,5258263,1922138,7151140,4157954,9081139,7132008,8344766,2756820,3837505,5102267,2896738,5650233,390455,5228799,2699510,7682518,6751244,5442646,2531083,671279,2172290,2557958,4720568,5077645,8382011,7174258,6615497,5153580,9970438,8697272,86433,3491801,7230852,6229884,5737904,8555769,2586010,2563792,2121715,560821,1775917,2664722,9067781,4924501,6544261,6516341,7273241,4307982,3569674,4118403,6535925,2229348,2962937,581129,1085194,9762358,3743536,5744402,9262707,5540730,7348522,1950425,4546021,3119513,365555,2705763,2450563,5366362,6078940,9325318,3235459,7353936,2462311,8251130,1010983,6251719,9884913,2840311,49209,931696,5021893,2965354,5331954,3918669,166775,9800518,7775220,1976900,1301366,5409590,5525530,1202098,880266,1945392,9262791,5378179,2663601,8822573,4253750,1743380,2358444,6214169,6528188,1032003,2405751,7389602,1379786,5637075,3637327,9515098,2525727,5267312,3980831,5840552,7201148,5322993,2414600,1781195,3233081,1806412,4873293,23343,1240281,6139437,2123445,5953692,4595633,8301537,5419502,9169727,5227619,1565752,1561558,2992112,1724185,7910844,7026788,7717940,6327197,6609806,6655037,3384474,7167017,6961454,3731023,8261975,75895,7466370,3989761,5546740,5427944,6218728,7394614,1298933,54974,4160790,5939316,5843091,8005873,6035311,1224026,9051093,5965238,7430696,547622,5085155,930290,1417104,8063325,2286270,1020854,5362084,3249921,9065398,7523541,7322833,5130039,2207633,917579,8627112,6977948,9884392,3633479,9766524,1606369,8130587,2648979,6717368,3410400,3878367,3463247,4755126,6800381,1533468,1645968,7456349,3004787,99793,977640,1161788,5829756,921471,7715284,4936006,3649092,6585273,8986513,837950,5949990,1157645,4362500,7741783,4132230,1026012,3536652,5005854,2271760,4481307,5369209,2236087,1569700,8697569,8340426,5552936,4427173,5084719,7900346,8209600,1058732,2379314,8310057,3173291,2704602,9812422,5553174,9855377,4682173,5429727,1589828,9318531,7405092,2715801,883658,3742309,4906748,2352652,707819,9944539,7789101,1685842,1163427,4366221,4811529,9948427,7476687,8111244,6246863,9106085,7014175,4152706,8598129,8313413,7184619,2831816,3599498,4594589,2532464,3623634,9591607,636433,4305205,936646,2274888,4390532,8035450,6102575,1039292,4375710,5560718,3723044,8219959,8305254,1370167,7063208,8081430,3515260,7162360,2245411,8563720,1163488,2530546,8439549,9376949,5388663,5845287,3131850,938366,6912814,7659180,2261355,2295718,1174472,74464,1752822,3854115,6171522,6480102,1684069,9440746,4148073,2317126,2996031,9465614,9020881,148543,5479599,5591991,904563,7197874,4015090,1608683,8264269,7297233,3834828,9004448,3590936,7831079,3790658,1285817,5126493,4722351,6540347,1565686,3696910,8329174,9329168,4490554,6742108,5912692,5870084,6591445,6420811,2427874,5218431,8272245,3048173,5018577,3800256,1300548,7826525,2925918,6246099,8316684,3393068,3357685,423189,5309536,7418487,6955983,7947231,2019653,7043664,8505565,2880889,2597041,8503690,7803626,3319807,3123393,7881927,124660,9432222,3350343,1288786,958581,4376846,2670575,1864167,5566952,2386532,1997167,1566945,496772,7451775,4984231,1345465,7700055,8977386,9625116,4131949,8789067,3970941,370908,7311067,7959884,3666809,4257660,612737,5024230,6815394,405746,9394819,2514773,5403856,9477780,9368716,5343841,3402691,5476262,8831585,3220601,4635852,5524468,4506976,6505878,7820064,8907949,994571,4286909,6318135,6594090,7258580,930159,840723,2826588,5186113,8504692,6980708,9006692,7862297,8329991,8526199,7225964,3061250,8604112,8612168,7975850,8010452,2420291,50907,9217211,5956919,5507488,5956767,7666073,7478447,7747182,4310926,4361760,8977151,40555,8812780,6568212,3025972,8364300,8727665,7680000,906681,2132458,4688321,4014736,6182423,7442046,7117995,6760473,8453982,3848172,9706038,8516064,3351372,7420108,910398,2136542,7615560,8869964,6032207,3932860,2359211,5614769,9227017,758796,5537338,9399614,6626815,2917718,965339,130961,883418,8812683,701472,6114930,771036,5071871,1092601,7958227,2484257,7332012,2968793,6862910,1322210,2410644,9217338,7033904,2490996,502328,2580502,984412,4816769,6057278,5652427,5197066,3047000,4326846,6521905,2337685,3324233,2675634,437255,7439400,2945429,6483363,6722892,8656102,494518,2517137,1587336,9117582,4068408,3729132,1748155,7159029,2862490,928733,5728243,6427113,964942,811468,2225473,2620370,1825395,7820786,6674270,8329565,6190410,3049674,6449007,6923343,1886545,6132658,4707624,6746968,9809392,4365835,4363461,3370626,8516373,7205655,6115913,2507704,7524224,8388255,5585440,8514426,7511825,5760957,869944,5493706,6386640,8241212,6705379,3433574,7602381,7376625,1791895,2281435,1113893,5967583,6757948,5618557,6315586,9005791,39461,3145376,6617225,9216295,668643,927955,7214888,6470018,4762445,1211112,6430934,1940913,8268478,7349601,2396781,6279862,3624677,7840562,8064703,4741752,6638048,1826164,3984725,8201196,8046723,7587987,6691132,1203399,2706912,5769641,471237,1594838,7130289,7983661,7085389,6335460,6351932,1656791,2097137,8096731,4707586,2541021,8923340,3553575,7406967,8520920,5584774,2022327,7424441,6894260,6018788,8106430,2537225,3048520,1628428,8384386,9563089,2819125,7996855,9557116,3756187,9709633,8596777,3116697,2852839,7650045,2561974,5881098,6527729,2357684,3753434,708500,3433355,7406578,4190152,7697524,7005495,6828280,9199183,9195505,7227471,8310166,8077151,7349796,40914,2270774,1506109,4937087,9665368,9537893,3621776,2553321,4289359,8176516,8938835,8414786,3058240,5541999,666431,7787386,6222417,206998,9055056,5265470,675598,7223098,4217375,6165746,6503524,1803281,2147931,3101432,1770787,4025166,6829614,5813165,7751924,729519,4562341,7587775,2660427,9330357,2643656,9026566,4196307,8113740,5971200,7682142,8580540,2697273,5503256,2463310,9232322,6387458,6225568,2365154,7393305,9683639,4225484,7574913,1228927,1943790,3195549,5082216,7080236,9784231,535428,7068079,7478602,7667471,1123533,7673908,6598488,8129570,4637915,6234610,8166176,3894683,6327670,7841305,6093924,1166631,7339094,4888268,7061655,8482597,7918452,2377506,62892,2508065,8943429,7022199,6709865,1001569,3792276,8972309,3404463,1707124,9380548,6766213,7480398,31912,2110377,7243481,9462835,1600326,1018207,6034040,3397007,1328678,376355,4765818,1664980,470540,9992723,2556126,9500250,8132897,5177767,3028063,770353,1299895,7922421,6274859,2070002,3628699,9831448,9330723,4657864,1293006,8076599,7863585,4552383,643478,1298930,2364219,8620839,3727567,82886,4522433,6315272,1401865,2554054,2219876,7235889,567079,6442365,4793240,2554986,7744326,5930158,7441483,4451277,8551223,20218,3189813,3596117,8853273,8873717,6396367,7997221,5306289,7555116,3206198,704843,8216493,1453972,1610803,5183207,5903757,1711566,2755033,1804189,5195928,5475860,7489507,6427634,6485473,3583754,7146280,686480,3286728,6885713,1680895,4870515,6846166,3797076,5954574,5485122,9692239,9502556,4463118,822285,512141,6404480,6296109,203056,3818602,277884,3406614,5870882,5448791,1879273,8875684,2617061,7068717,4485151,5783010,9335627,3929840,2246303,5732729,4775493,5312970,944969,9252186,9563375,75400,1629089,9603676,1050730,2513774,878654,5154378,8565310,1647909,6147161,818302,3003407,6866022,4835546,6882047,2985256,3199526,4914018,2318456,1510501,4966912,8413965,9683138,5051697,6232917,5230598,1352676,6496931,933857,2668648,295772,6973140,3790615,6141718,8984757,5115427,8434853,2997351,8493768,4628434,8074806,1102101,4771448,1872082,1602395,4695951,2906692,7831471,3938813,2047467,3480081,8252119,680723,7005388,6657372,3747862,2963611,4828835,7707704,4215033,1162214,4779692,2190267,6824008,8358737,3670957,3661786,8761180,7087031,2340456,9698308,9958036,5539361,4782062,7384717,1410960,2355217,9779748,4769059,1550628,6086266,6583448,7172343,7102322,8482683,6584731,9616316,7837752,5809554,1773208,406556,6396004,6428986,5908135,9163045,6267932,2458712,5710487,9198928,2674219,4177385,8370698,5299244,9078010,9463645,2308893,4098503,1127101,6096234,3590483,1322689,3733392,9086578,4605848,4888384,505076,7873709,9082424,3309756,8530957,6847320,8529182,3064494,4797522,8134846,5805943,1783540,9138,2876229,6463941,1399914,6848518,4817276,8577619,1643721,9392911,623993,4544587,2691348,8810688,2442284,3095596,3306444,1110880,757812,9691904,6767908,145405,9600226,5764962,9044800,7114579,4934771,7174529,8575088,8454992,6959539,9012554,7081532,2572994,6628898,4694795,6906029,1040591,8559094,9142910,981674,8835338,5586681,9885421,2461074,7529384,6661552,2771298,2925913,9114763,4109204,2458203,3169223,4330262,6930017,2254282,1487947,9770343,2132113,5966392,9685674,4145089,3332371,4805582,421082,5608679,7042043,2052527,7105209,1290052,3550467,9178723,7440495,2076838,105598,5958462,6443159,7856715,2047353,4571652,2804672,9032207,9824198,9265201,8005634,469678,7449260,4324356,3807283,8224934,1066774,429857,5343469,2580967,4619427,1834917,3055817,8176623,3842109,5779829,8179574,7683620,8113421,5145186,3154724,4506424,6884483,1063066,6674312,7934510,6522199,1964478,8565032,3901631,7810783,1347193,1760291,7080386,7894724,3318118,3583408,4951164,2094238,8192367,9716890,2599876,8526794,2187152,3861219,3159342,4095248,2689813,7372525,3118820,9493212,325087,4752967,7944072,5153626,5584423,5896933,8619738,1668072,4892401,1403368,9831293,1211877,4295837,7740117,7084251,9759191,7759198,9717718,9439122,6831867,9452145,8985954,7009003,7844929,6878649,186075,5533628,2042259,1306232,8120164,9817459,4858269,8083217,1446925,5931969,7760970,5887457,4258546,8984290,1062356,7157309,4478213,8815569,8346056,9864535,8458014,7307185,5066470,1985123,1787605,3718852,4110447,673038,8017975,1129821,3546222,2736531,7013994,4767906,3295603,3287953,6443442,7774404,9413881,3285444,9721569,7327188,4200404,2098661,7074009,7033573,5776251,1300692,1161424,7647453,762686,7390706,9162443,2052411,953083,1073077,5852452,4958199,3194070,8257699,3126855,8365351,5654582,965203,9790867,3109177,98108,4662210,7933549,2439171,1823167,7159313,1212752,139800,4551694,7965262,3637503,9518165,3784371,5425808,635616,1504314,8568112,208934,249757,6109983,1284490,4735558,9886527,139237,1622817,382273,7005823,4718939,8646407,3971504,2173989,466563,1696089,2298134,9388161,1494500,7298097,9070536,8113787,2426501,1686221,277099,628970,6970281,5707603,9044481,66741,1460320,2387686,7943470,4952844,9464557,7604090,3901105,6419781,9660946,5607270,4652917,8312241,6409548,5577959,2298682,9767725,677205,2489132,1313546,9300992,4511526,7094812,8130901,5324348,2800568,4529658,5494545,8944726,1355271,618923,9633304,1223364,5639838,9446961,3707661,5527895,5618670,6254370,6607112,5263343,4487574,8459520,824320,5921937,4732419,9228770,1156198,3135560,9959343,6410581,7410631,3997447,5137491,7395932,1559505,6590787,9462171,3341596,8535818,3564754,6855576,8215020,8528372,3871188,5000922,1964086,470638,3268589,2612935,2350008,2127864,3326139,1484491,4448525,6592915,8163106,9538486,5389397,8621108,9370997,3606335,3138186,4897835,9140172,1570576,7876017,8415717,164057,8331009,4479830,4386475,4643917,3876520,3966789,953222,4625207,7299482,1958242,1758863,5808384,6302414,7899824,5874032,1812404,6661206,3783389,2032047,1949908,4604050,8061557,4400210,4238232,3394073,9526076,4261956,9273897,6528781,8527623,5783329,6706630,7267431,3083541,7194839,4405367,9245841,889504,7217829,6344109,3408303,7547648,9571259,3865329,4215735,6440645,1764398,6822898,7174241,3795005,7935530,2471407,4917584,9570238,1851284,5309262,3769134,1877132,2201194,4643241,6454067,8096211,5209093,2434144,7322633,8854344,845472,166836,4946901,8911673,3199176,7860173,9670657,4083076,9659081,2580684,7709103,104266,2389302,4508763,7093495,3643887,1067529,2272586,9172793,1921968,3240523,3211830,3413562,9000210,2060152,4958342,830641,3932843,1723241,4119774,6327719,5490337,8169268,4343800,2554895,5201652,9367562,4117017,5544621,1647734,6716637,1766333,7945711,2023357,5660227,3871041,15876,505133,4988561,6313428,6740843,3272060,7944495,6310988,143150,1442597,7916143,9134503,8112412,3194570,2563051,4916912,9914098,1307991,4625264,9438684,2944828,7537939,7689161,6480592,4399533,9418555,3779023,3542315,9680067,3402859,3194287,7830486,6525945,130309,1210905,4945675,2515912,3089754,6456963,6309348,2943942,3869826,1373055,2438408,4269735,69448,424745,9085100,2452651,1221066,8992882,2093247,6858147,9808652,45705,5613494,4409161,9547745,1402548,2857175,9196161,2011248,1904042,2391739,6531596,3820916,5447826,958799,3121138,8222883,9376647,405621,4369401,7178087,9976472,8472363,6815662,7995198,4478729,680549,3316238,8000040,2903881,2591081,512407,5143362,3551208,3169483,6125092,6832477,9290044,4307365,772867,1312343,7003162,8932673,7074078,3715941,2984594,5519187,1672562,6897191,4858767,4018554,8541992,5111281,7511422,5700446,151242,8217673,8208249,508002,9001086,7758573,7114277,4575163,6614245,3657793,5570263,6183122,9581778,2379790,4513955,9952923,7879809,9919387,6848808,1539262,8092108,8888674,928143,4860568,3249325,7435874,2145836,1822481,7007381,281312,3989144,3767096,6344995,203623,8059778,9645759,1707882,5127001,2244081,3952605,8643557,9095175,1552547,5102796,9081900,4864659,7990436,8938761,8604666,5632814,4906781,5164705,8921356,3703925,6850000,183892,9971107,352708,1293998,6274092,4290932,5513766,8710866,4483084,2148963,9475240,1852287,1680570,352752,9712030,5725287,745265,4134736,7024285,6303097,4485370,5882294,2523069,2626680,696340,7156741,7189890,8354869,4496225,9317108,7379081,6266394,4587292,3233760,9741847,656146,8403368,5549331,6897668,7946853,5904244,8431074,9887069,8341893,934471,4222125,9247761,1944384,1581436,7698507,2133527,3801876,6296354,7867702,9422969,7397704,2833141,8187838,6660644,5598326,7763740,1371545,4577070,1466964,6066480,6010651,6382843,993819,117617,6782951,4133751,5025270,3110856,3769078,1463189,3118741,4943973,6732677,317178,608356,7153360,7681506,5809615,3827602,2703141,9649350,5643753,4382319,5378000,4810420,894734,6752470,2577788,9748127,1027823,5978850,6525600,6420149,736776,7348065,5816566,4399777,8495422,966453,4403993,5758744,8001217,8695540,7255043,2042290,921667,8212056,7567669,8661102,6145700,1586289,1213162,3357441,2944387,2089352,741644,1713693,4203971,3702939,1493255,8337362,7701025,7635808,2560302,7674943,2820697,6661339,4170495,5113330,4386662,3974949,1879494,1054171,219557,3614200,5415680,6753724,9719099,7391363,9939636,7369344,3981709,7161694,4666885,5445792,9453385,6152933,1733927,2657114,331653,5649728,6730137,2266007,277968,7381321,2190644,1551748,2858483,9760885,9867035,2271198,1617107,6881868,3880276,336220,3551858,7302323,3312557,8958132,7215102,417379,2632134,864644,8272751,3333428,1804088,2015884,9818731,9022745,1354062,1146807,7634976,2964207,472715,586740,2785352,4911207,6789850,1207059,9326183,2945202,1407409,3351962,6402796,2840081,8895536,2453891,8444151,6332718,7104278,9244500,8943787,6982588,6789476,3394540,3619061,5614777,1936964,399691,4521095,3666746,8511755,9759143,8820568,7561554,795703,6323393,7916982,9142288,5089052,1405254,17197,104261,3170617,6446899,6437180,1193615,8008175,7650797,8132788,7995152,8965818,972367,7211279,7166814,910846,555698,8830409,9250745,398813,7234174,9914834,824588,9531178,1023419,6673228,8646420,1330540,8899973,4397092,1424368,4629844,8883563,4399070,1613496,9374876,7020295,9493759,8405908,586890,9561662,3861574,13331,2193745,5993957,1087018,9296346,2341574,7226892,8817978,5625841,8398438,4188534,4460190,5492053,8768266,1548203,6861666,5099046,6784108,4291592,5100572,5446517,23056,5035539,4036026,7967925,5614614,1166189,9388783,8192937,5489990,2938893,9669772,9300960,3606192,7514394,3447501,8620875,296446,3234982,9604879,373588,4630682,3090508,6492731,6810417,2554953,7637526,9105790,1481388,7667985,9449643,9246824,9658101,8175569,6779021,177634,8861346,7061803,316444,5827467,5002396,4295092,9882513,9764152,9930917,4617478,8510515,9999993,4998712,7640060,7511416,3977095,5567448,1790746,7899431,1111549,2935442,8006647,5725939,1385746,32629,246608,7439482,3540673,7028638,8372402,6706840,2428266,6634496,3847510,4523862,5120429,7578691,7903774,2882201,4704483,1394607,5451668,1544921,1758131,616902,5063359,1818712,976829,3307235,4488148,6525202,2313992,2610564,3263995,8237974,7727351,4369344,3357250,3866055,6681357,5164578,4652019,4599152,7749110,8536746,1907210,3278998,5152320,4714448,269109,8032371,4484722,2636962,704060,1620037,8477500,1031560,1568661,2217356,4700106,999378,7465353,5078542,5731193,404241,63806,7629999,8459150,7056920,1286699,1005861,9529455,9951441,8478097,1153449,3771258,3810803,4502885,7033567,4567099,1250831,3175384,5116459,5408634,7999358,2715969,4855266,2398578,4097293,8016730,9026737,9815395,6271859,736481,7423768,3604381,9544756,6462034,4624109,1245492,963266,6994113,2613922,2423501,2888963,5977990,166137,3397329,1423797,6130762,2996528,1525992,3220274,1493027,9647127,1257548,8224809,1769256,5380508,273282,4661928,5675549,3533805,2680488,241858,488573,9809170,4425087,3257836,1116040,6213189,1884583,3435237,2591480,8824578,3829522,2670406,5089422,1215453,9567595,5122356,4995741,9604211,4673495,8162612,6482197,2856486,8145113,2184462,2679179,6142138,4487140,3583455,9511697,8620039,9513332,3852345,3067884,4883391,7260060,7585849,1851648,2908085,9395508,1563404,4493413,3000281,6037459,4793281,8285722,6351081,9792574,6171444,3094813,8786866,6604221,1061968,326752,4796935,7159238,8262894,3871731,4059342,83276,5747739,4753087,3923407,430996,8930361,6569286,247667,220490,5031464,8017928,7543187,86566,8738444,4460175,4084742,8244794,4081541,392406,3371752,4923408,3131313,3160053,7633509,691942,3295011,1593381,6633235,9430202,2706971,3058654,2218758,192036,2107820,3970088,5812493,5670007,7984650,8490110,3633893,3276495,2706767,1897111,1779269,5868686,442511,1034688,871359,7985354,6567254,3614508,6400841,230140,3302013,1531175,3443383,3069454,961631,5066164,2167897,1811808,1960286,7719388,2520954,1433162,7446404,1673573,9936625,2506740,4929074,9645703,3098938,3672425,1993432,9466619,3781440,5313245,5710680,6082738,284209,9876964,7942915,3591407,4922629,5097831,7698596,885111,4810832,1584042,6172529,5458975,4706470,948967,5442884,7731187,2793707,641961,5543654,2293810,9639759,905303,7678785,6112686,7423885,5498875,5159698,2652969,6576616,9449739,4840207,4672671,8658050,6560134,991179,7767473,7316839,1770062,2738566,1669738,2546744,1802838,9308342,5406589,3178034,6705050,2434314,5664141,2588750,6465638,2681478,8687975,8244344,7736263,2205895,425644,2501846,6869351,3799650,7142955,9519133,6928462,1485887,2713008,4141743,3662723,894957,111302,1310927,12948,6709019,3211641,8560601,3244931,9517630,8771790,96807,6400873,3663529,3739752,5908306,7692735,9274320,937455,9867130,766426,4820582,648419,4643218,9837570,2080063,3189542,371799,1567901,6701125,3335491,5304228,4619498,755710,9726567,2467897,6016558,1388664,1252118,7726332,621717,666623,7883373,2772308,3267212,3795425,4284891,8067298,2640707,698961,925117,7087786,8992258,6597751,7666095,6627121,9337821,9691899,1725065,4381370,811079,2131879,4228220,1300634,3487246,4246298,6554028,398010,127764,765209,8848985,4332549,3089050,3770873,1815092,482065,5467873,2922352,6957505,4042178,4197211,2622984,8777172,6909968,4235838,6088504,1553318,9303175,9096729,3826147,500076,1916131,3293116,1166116,3734564,6345591,2257845,5354844,2000023,3756904,8709443,9196526,2042689,4227727,8691882,2035329,6706054,2193401,7036603,4007482,9277985,5139920,1975223,5456809,9368307,2084999,8007381,1478906,2339650,1323199,5903940,4850885,715555,9998140,9677672,2964879,7791447,985978,5991511,3863217,4712258,8680698,8596947,7389236,7608518,7902909,5009838,1833509,1621293,9066853,8583448,3787315,8231570,5185660,5241769,6933298,1282437,8409133,7248380,1985153,3278788,570773,5595376,8693921,6460783,8727558,3147266,2172590,1765480,3342648,8338040,1393452,4728416,3964266,4533482,148592,4241559,3832940,7808729,1356447,9019888,9024627,5815974,7978688,4037845,7917741,6095414,7767308,655097,3318279,8606337,6877170,5550659,2315696,2647252,7232332,5281766,4547598,9025486,2910907,9235160,7257886,8075880,7930529,8232282,639207,3365609,5275445,5221857,3491673,8775016,5197136,683950,4781650,1604049,2548274,4916309,1269508,2899438,6912446,5828518,1404738,9596028,226016,6166364,8985452,6133206,8329691,2805646,7219075,5418288,8639459,7846764,8864657,8303635,3033368,9928217,7202620,3066211,4681313,5278843,7636965,101774,1439579,9129749,8093570,6045020,5369070,2468936,5468021,9531608,3846736,8800133,9935569,9761120,3266981,4340468,6552892,7427535,5264109,6687110,1235571,6030349,1265876,7446415,2158483,7194164,557369,2784061,4217418,6066541,8507935,6415092,705699,9149511,7082316,3150406,3775271,2364950,6885523,7792493,4945829,8358982,9542869,1313003,9972708,5576240,6155065,1431071,6360559,7460687,7892830,6600511,8252278,5935196,3092583,7102481,4055427,5847028,7566830,903391,3409313,9967204,99184,582797,70437,5116126,4392493,227470,9286001,2173942,4538458,8023009,3682848,405355,4930682,4179761,9294088,4442545,4132886,9766218,3675448,2252130,3033843,8096226,8316948,9461823,5044353,3666794,8879857,9732033,5606187,8143420,6946539,1087842,3912561,7682103,6398463,5102146,9522366,2080778,1484501,9294621,1529272,7830950,48691,8968091,1273681,2051363,389528,2536734,1392472,1348234,2501645,5106725,1244575,2335040,7438253,9437912,6755470,725375,6377672,1913970,1465542,4492362,4021311,4200918,3741085,9054169,8144334,3587853,8124842,1549040,9104210,3013173,5883091,9616516,3126426,5356124,481632,1938775,7090325,4431335,317794,258181,1043475,3547486,3064389,8717654,8696869,4381594,56723,5682088,2161360,5822196,7508308,492429,9156561,2572277,1961862,2489538,1937756,5103970,4249952,9356419,6468745,1782544,8657935,955395,517712,4497582,8376325,6580838,5694258,1254769,5952484,9453227,8600737,1233452,7138956,964551,3175123,9166208,6795945,7578820,1211499,1042045,7651695,2728061,7756903,8961746,7910246,1984789,6014784,6835523,896588,9827511,1169626,9852930,2624317,9187518,5633431,6843384,1871838,828534,5174342,3434207,5860448,650250,5502072,6940485,7008353,7899780,3804106,9562824,3366463,5895545,7797325,5021822,5725873,3182390,3824616,5491534,2706955,3731383,6737831,9647179,3648823,749976,3245164,6257693,6013124,5989960,952154,3900569,929292,7794806,7763855,5996458,3353384,180452,9907177,5751163,2016858,8285980,6112873,7349789,5378883,4176672,1518523,2163967,2934224,8123275,8881495,1853186,504240,2196182,7279788,9972559,3511643,4907859,9054404,750985,1901592,7886313,981195,8608046,405110,5296143,7591300,1984811,6184470,2342462,1142579,8788077,9733739,2205822,417180,7159113,2735573,551559,9967056,7775674,4283640,8443812,9197459,6889414,8619833,5900592,5995729,6404683,5552485,2135336,5056891,829397,8231305,1573740,4623155,9207817,8671950,8900509,96676,3808589,3290691,4884121,875914,4114899,8769429,7054081,942994,2749729,5290245,5739382,1815293,7305491,5737591,7411001,2176408,879736,1281339,4067363,4995841,4131727,4509102,1557008,1086313,9760229,9236514,5207476,7231465,9389927,4041902,6228220,9665539,7544464,9697495,2832401,3467235,7916467,1547204,6727644,6336867,4288374,5582053,7609119,9975174,9387750,9521915,2565750,2756942,7991290,6743649,6916315,7379903,5610219,5965096,1393198,4149768,3479284,9583850,1396531,8135998,3934170,7225873,8704721,4139143,7049960,4243120,6531975,9039911,3771723,9170412,3439704,2366589,2124832,4279676,3307989,1810947,2647062,6522414,7523320,3232376,7175600,3537551,9203838,527788,6233359,4330375,6787513,9755597,8756646,1457163,860543,6694546,6163330,3664680,5500033,6209132,282415,3362225,45520,6471403,6125301,8772932,8130946,6304058,6458774,2890372,4210704,5529141,9108973,6698068,5005523,1131051,5148476,4566213,9794581,600285,3918824,2078744,2102531,353290,817859,7719135,7689528,6394985,6052061,5303810,2698542,9630468,4361931,147767,7264316,2641704,7372084,9592247,8120651,1862568,9260941,4946061,1002161,4990619,4671244,160348,9966711,7055319,9111992,851813,9281886,4839356,3285126,2840893,9921096,3874968,3348234,3130862,6077011,1053662,4778857,3791770,7079838,9016024,8111277,1171709,2716714,2040969,3870504,7648425,5451118,9513568,7711023,2773733,7620433,2850893,715294,669983,950995,5890910,5673172,8673637,9095598,6379787,5483957,8086004,9402359,8526757,89767,1480369,2967546,3685958,3099720,7435166,4745997,2986715,2311660,8208886,6011888,8689404,2571455,7897478,5038381,1580330,1501506,5629887,6028858,1154608,3082421,7593076,1975092,6875497,6165749,2005304,6639441,8118885,4250489,6088565,2034759,3273337,2372115,1409637,5455256,6153069,2028034,4500633,9072103,3635939,8257221,1526182,2297569,7484951,9931241,3745645,7441367,2594092,3123462,8605486,7013025,7827117,152974,5648839,3841781,6142381,9416924,9226199,6626892,1745698,1975929,1990609,4021008,8456991,1082366,9419213,1155723,2912515,79090,7215822,3589263,5809378,1126671,7014220,8575781,7900986,4586952,3688627,6238648,4429422,2298887,4482604,5217708,6304509,6020908,1400192,8949680,7900836,7743985,5153532,9244287,9967379,7629271,488874,6277411,5214013,598858,7168533,4467280,6561273,4298027,301176,3426846,8160816,3640557,6903159,3081719,9058233,9947828,1718425,5486838,1023728,425672,2455777,3174463,1889619,2023805,3739955,9917170,3852724,5448302,9007288,2873494,1243268,9616070,1002148,1759300,9380950,5634522,4222418,5334652,9301433,7324983,8306452,5248115,7289446,8215782,6093125,3769457,5413304,895377,3895714,9738334,8318531,2081619,364015,2765808,734519,3792484,5528421,4803842,3446792,4392100,3190900,3797277,4524937,4197911,3489925,5076062,1286097,9952003,1072173,9335320,9638223,6889474,6957712,6160378,2457418,5424209,9680017,6507617,998427,6454525,2999325,6807086,1077593,2369438,26205,8076708,8971304,766470,5353162,4499221,3131565,2016999,4540907,1043171,8252176,8003254,2580062,8157687,5541862,5681786,8339477,8844329,1066336,6133540,2121544,4166375,5719199,5021853,3860897,3561372,8214275,9110004,7567758,6980670,183168,9948796,7880161,8692790,6069919,1903615,6160158,8778799,4802344,8938410,6734271,6544767,7645863,1639296,4509121,2337362,5622851,2535448,2593395,3456568,1663337,9457053,3286874,7767086,7021758,946966,5124745,6396791,7329029,1269660,4342852,362152,8334095,3429575,2617111,3267901,4532438,8629659,3630366,624079,4091884,9398771,1349701,2653919,3387774,3446569,3727396,944391,4944329,9898182,7842642,4210497,3460525,9572907,8166372,4516976,3841202,1496421,3226601,8464638,1134582,5509134,6076605,8366532,338789,340922,1338486,4877672,3004609,2191597,3458044,4557446,1806695,7138923,7049524,4325589,9736307,9525381,7818280,7423774,4082878,3097306,2447253,1510272,8171955,3179828,7983647,7301469,1161249,2261878,7212363,3572177,2226191,4876789,4859969,5073186,3457914,7446112,7816368,1032333,809559,8834101,8146736,1052839,1843716,2600429,5623892,1552441,5207879,2373818,225992,4792836,745575,6141750,3834776,5132006,4466590,7055968,2833137,3383306,5066153,1620701,4549446,4387825,9298790,5575408,8678996,4875938,4772461,8621114,1457221,1273464,1922292,3490994,5561008,4585873,7389387,6840623,9329890,7577214,2743974,9536136,6026246,3047333,7301701,270514,4148096,9306579,2603475,9474992,1044624,6872241,9657574,5035872,4299231,2671577,7403406,1690931,5168534,1437879,7605623,8920205,2067046,955763,1173503,6797300,9247637,6063640,1549942,830080,4710754,4590638,6392780,373264,3368429,1507458,944830,1989923,2342096,6183372,1170949,6496725,5547670,5389952,177752,3458917,6267570,2784035,3656061,6848302,8245166,5809652,2655088,3467931,5225541,6451477,2124773,8323784,5857268,3625343,6125716,829729,2490853,1667825,1602668,4455087,9324864,4724870,7913480,9119172,1295345,2865385,8461416,3613771,5725896,5963384,3218641,6052936,633225,4310523,372104,5024115,2372469,3594538,1727497,5335788,5645021,1463657,6649155,9825145,6523527,4225760,9569457,6255458,4952432,7668618,5211952,698753,4474438,6174542,2518924,6262415,1685171,3069767,8690005,7111266,5681879,8767369,7721383,4046418,9242765,1746464,4063408,5175154,1918089,1172829,669632,388778,317961,6773987,485162,9930165,364580,6775262,4515133,1033186,6496766,9799191,2907686,9938346,9266604,9059656,4984807,1958460,9156908,3581330,4562209,4513150,8342819,8369789,6429847,2747372,8612118,900828,5447994,6572713,6493287,3525347,7810154,5718819,6863372,9334247,4259869,5329268,9545590,2781426,6189100,7274794,8748627,5981192,5394906,4225018,7573897,225380,2302920,9847602,1436460,6297901,9197987,6579462,713051,7782755,7280505,2203875,8159915,8129770,2550570,8021955,7197171,6849504,5145848,3536609,9583602,8508081,7830138,3672278,916495,6040159,1058424,7518814,1002640,4490869,9005726,5619322,2012644,8861819,8616455,78421,4756459,5526187,845768,9693695,1815193,6803903,3047899,4307348,6032959,8099374,2615231,9080088,2519653,6130478,4984368,5786722,1857897,4272112,3852565,5375952,4155944,197929,5033273,9066613,4360677,8775538,9176524,463273,2188098,9054743,1381246,8970888,6843134,778913,583478,1075663,3073406,1705785,6428929,1208296,1978123,6575607,9266899,4691182,8959204,1058808,2090924,6805771,5124038,3800745,9971053,7531151,8345562,4217358,6970871,4771751,5997427,942001,6964254,2911464,8440324,5571686,4469397,7806538,7261923,4964769,2379052,8993560,7296924,6341304,6385217,6933559,2446906,5834401,7743087,4527288,7569410,5877077,1286131,684675,9912231,9771678,6968055,1611409,6022069,4037997,199724,7778258,7733340,5788467,4795968,4909366,7427940,7937790,146577,5817257,8082287,3268413,966975,3522322,2278950,7143245,1828180,245385,7999658,9876051,8995912,4574515,2281889,7860567,7382346,7176591,76782,8726616,8521294,6118489,6694996,9648960,4233565,5226143,4523808,4081502,5973641,9406891,8845127,6672407,6955088,1481911,446850,9690096,1068859,810305,733523,4239370,4456873,6792392,5176585,8001966,8610448,6540466,8604017,7592233,4955566,1653396,9370880,494930,7440876,7122223,2896158,4745505,3814525,499164,6324428,5618473,1531650,6013619,4325310,3108323,6638614,7629085,3495021,309584,1522681,1426859,4538531,1484157,5277197,7450265,8206534,1694976,2177119,9132097,6041176,9408657,8109858,1505117,941487,4091622,6754902,5408622,928224,3981661,3169630,2627795,57351,9892149,2556458,8134722,8853301,977701,897700,7396036,2675273,8423649,4597743,6031283,8862198,9169362,970948,103182,2531970,4801797,5245913,3830268,1781622,7026402,6310712,1915509,8913855,264891,7902896,3259682,6419372,8921528,3926386,8325511,3279109,7502667,9038552,5693424,2536079,2892846,3814123,9813414,6922076,4983272,5224256,5589230,2592429,4260568,2134622,1015607,5393990,5078809,8787468,3751585,8080358,9265888,870624,5620446,2810568,3015631,3470857,962147,3459337,9391503,1175627,9768561,2047721,7724195,2679523,4791257,9054383,6445322,4653079,2214158,3678013,1685233,1875695,2166428,7686757,6162092,9889098,4935547,7118514,8728398,6429363,4608815,5173358,943189,6474017,3919706,5340446,4817824,8483346,1943687,1460646,9730882,532072,7396827,6298381,1784566,9689178,8872859,269378,8152562,5804079,6483384,6781869,116849,861940,9160362,6705188,2443439,4048810,2708856,219234,744966,2479825,7725202,683347,588056,7924591,3943391,5467801,3188498,5620235,8075261,8484563,8358766,9673374,1157228,8315513,2732104,3464904,4694050,4893281,7776293,6953657,7736804,2175332,411038,3598199,5674937,4952795,3806302,2074909,8626824,3072583,9568788,171637,5150213,3826494,8709905,8641493,4937996,1808297,1268705,2089064,514538,2337676,6372072,4048755,1834362,4013665,5636225,3698698,3130902,769449,6006987,9042561,1469105,9244470,432368,7003108,5521181,7450831,3996758,3426057,2498401,8640056,7424643,8198666,1681255,4040978,8899408,4145278,2800064,9477207,6882134,4579793,431967,7154699,9512129,2223138,9494374,5576160,5612644,3663447,4968393,946074,2424328,4929390,2854620,9186592,1956994,1716208,4568043,3902339,5668190,6799161,7564970,6760707,9472719,5196254,7991601,4801331,5386589,4215705,4507156,3521824,3866218,7765616,3456488,4065848,3278547,2521816,6480972,6570895,7812288,3294179,8920605,6538747,9913174,2235189,6280908,6253991,6246060,7259516,1678374,4704442,1575790,399647,6501592,8827675,4677366,8678348,1904707,7690197,284055,4836540'

PRINT '========== Sreenivas Chedde''s Method =========='
SET STATISTICS TIME ON
EXEC Util_ReadIdList @IdList=@s
SET STATISTICS TIME OFF

PRINT '========== Tally Table Method =========='
SET STATISTICS TIME ON
INSERT INTO #Id(N)
SELECT ElementValue = SUBSTRING(','+@s,t.N+1,CHARINDEX(',',@s+',',t.N)-t.N)
FROM dbo.Tally t
WHERE N <= LEN(+@s)+1
AND SUBSTRING(','+@s,t.N,1) = ','
SET STATISTICS TIME OFF

Of course, you'll need a nice Tally table to run that...

--===== Create and populate the Tally table on the fly
SELECT TOP 1000000
IDENTITY(INT,1,1) AS N
INTO dbo.Tally
FROM Master.dbo.SysColumns sc1
CROSS JOIN Master.dbo.SysColumns sc2

--===== Add a Primary Key to maximize performance
ALTER TABLE dbo.Tally
ADD CONSTRAINT PK_Tally_N
PRIMARY KEY CLUSTERED (N) WITH FILLFACTOR = 100

--===== Allow the general public to use it
GRANT SELECT ON dbo.Tally TO PUBLIC

... and here are the results I got on a 7 year old 1.8 GHz single cpu desktop box...
*** Be sure to scroll down to see all of the results ***
========== Sreenivas Chedde's Method ==========
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 2 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 5 ms.

SQL Server Execution Times:
CPU time = 47 ms, elapsed time = 42 ms.

SQL Server Execution Times:
CPU time = 125 ms, elapsed time = 770 ms.

SQL Server Execution Times:
CPU time = 969 ms, elapsed time = 962 ms.

SQL Server Execution Times:
CPU time = 1141 ms, elapsed time = 1782 ms.
========== Tally Table Method ==========

SQL Server Execution Times:
CPU time = 594 ms, elapsed time = 658 ms.

(10000 row(s) affected)


Of course, on your much faster machine, the times will be different but the Tally table method was much faster
than the XML method you use. If you add up all the times for your method, you get 3563 ms total elapsed time
where the Tally table did it in 658 total elapsed time. Like I said, the times will be different on your machine but
I suspect the Tally table will smoke the XML method on your machine, as well.

It's late and I'm going to go to bed... but in the words of a famous Governor... "I'll be back" with some more
testing results of some of these methods and a little surprise for those of you that have tested the WHILE LOOP
methods and think it beats the Tally Table method.


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #834844
Posted Wednesday, December 16, 2009 10:00 AM


SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Sunday, December 11, 2011 10:58 AM
Points: 49, Visits: 100
Nice article Amit. Will I use CTE for converting delimited lists into tables? Maybe not, but it is always fun to challenge yourself with new and interesting ways to solve old problems. On that note, the following is something i was playing with after reading your article.

DECLARE @string nvarchar(max) 
DECLARE @delimiter char(1)
SET @delimiter = ','
SET @string = '3903044,7569634,3947703,4397641,8304414,3889301,504543,5543592,2468890,644965,3343770,5383570'
SET @string = 'SELECT ''' + replace(@string,@delimiter, ''' [Item] UNION ALL SELECT ''') + ''''
EXEC sp_executesql @string

It is not how I would solve the problem, but is yet another fun and imaginative method that does not use loops and is ridiculously simple.... however, it failed due to memory issues with the 10,000 item list...maybe as a collaborative effort we can find a way to make this work with 10,000 or more items...

...of course if i had a list of 10,000 items, i would probably do something like this..which is VERY fast...if only we could pass a variable to BULK INSERT instead of a filepath :)
CREATE TABLE #TEMP (item varchar(20))
BULK INSERT #TEMP
FROM 'c:\shared\delimitedlist.txt'
WITH (ROWTERMINATOR = ',', FIELDTERMINATOR = ',')
SELECT * FROM #TEMP
DROP TABLE #TEMP


"VERY FAST" = 18 ms. to write to the #temp table and 185 to select from it...
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:
CPU time = 15 ms, elapsed time = 18 ms.

(10000 row(s) affected)

(10000 row(s) affected)

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 185 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.


-Jeremy
Post #835280
Posted Thursday, December 17, 2009 1:38 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Thursday, April 22, 2010 9:01 AM
Points: 1, Visits: 52
I used this function with data pasted from a column or data from excel. Short of some additional error checking it is a handy techique:

declare @str varchar(max)

select @str =
'line1
line2
line3
line4'

SELECT item FROM strToTable(@str,char(13))
Post #835967
Posted Thursday, December 17, 2009 7:07 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 1:03 AM
Points: 36,975, Visits: 31,492
dberra-831997 (12/17/2009)
I used this function with data pasted from a column or data from excel. Short of some additional error checking it is a handy techique:

declare @str varchar(max)

select @str =
'line1
line2
line3
line4'

SELECT item FROM strToTable(@str,char(13))


You really should reconsider if performance is important...

declare @s varchar(max)
set @s = '3903044,7569634,3947703,4397641,8304414,3889301,504543,5543592,2468890,644965,3343770,5383570,440012,7339719,76014,8040031,4997070,9773149,9855323,1071378,2103257,2649769,6426595,8047712,3137660,4099409,4409020,5162970,5318462,5744243,197552,8800966,9836688,8844548,252242,3689527,9050336,6954770,2563127,2645811,2301610,622241,9554859,4693127,2887526,7288011,827052,7415771,573242,4212591,3730887,5869489,2587206,8133311,456990,2814414,847007,9325588,6967504,8730656,8423033,5321137,2078707,7189305,2611477,3487223,9499821,3987795,7260462,7964035,3500057,7668520,4626210,7552756,72369,8898160,2626446,6611941,8111801,8330984,1008036,4341644,5742910,3559633,2568287,3597869,973692,1069671,1930909,534608,1120557,4802833,9855422,4124629,8359848,1736288,9388119,8612002,9434097,716768,7229868,3308143,4089950,5521363,3036967,6190484,1232180,3138889,5596365,9672451,975527,8101909,3173187,2841140,8295477,403603,9601512,1368634,7321256,8909479,4545336,5597565,7131675,603037,7954992,3495034,6178214,6763241,89887,9718642,1639225,5048694,5064772,9832967,9443072,6184168,5486712,3189834,4804407,7692191,154574,3482074,6363571,5051199,7191045,6258786,6472593,2755414,1384828,6831792,1092942,1819196,9151993,3003191,3582314,313050,454573,1690061,8940418,8711979,4063835,6678857,3147220,9195444,8309218,2512581,5336570,9253574,3711581,8879370,3921415,945061,9157117,8960209,9062053,8591031,1621002,2664810,2067312,41460,4667642,768797,9425827,3539023,4066081,4490449,8185852,7888049,4410916,3424255,4145447,659540,8047748,7344584,2447102,9911347,1054107,9685573,8793850,466863,7407541,8398934,9485452,1302328,6231869,4189109,2096463,3563419,1994241,3494678,4379846,9787663,7520622,4924337,4662584,3004150,3230358,8151441,3338672,3951778,342318,2306372,332518,9589774,7842336,5700428,9139865,6311551,1445427,435231,6243686,6301904,2939143,9781840,4951333,9787284,9243338,3926819,2681920,6148171,299009,2041045,8461143,3676388,802040,6237347,8069518,4576435,9556536,6164315,1701311,8424821,3947943,9257924,4630274,2317495,185990,9957539,3686458,1434313,6666013,8666791,4719290,119047,8825730,6835864,5913272,2310722,8546441,1951804,1989560,8240633,2377564,2310092,3510656,6690432,6155824,8857111,7330635,926813,5034339,2445286,657137,4739937,7882633,4374752,3865562,4637519,4221997,1365553,3868678,5315391,4105041,2314591,5216507,1359730,5489894,1245742,8184975,1337612,580877,791198,3734278,3954151,7654225,153127,7681184,8951458,1202030,6370054,330307,1016590,7000996,5630395,1693766,8095994,5815908,3126401,4533411,4088208,8606609,4373119,2505072,529827,5786272,2110902,1692427,7181013,2076552,9755709,5820278,1337908,6952791,9922382,324374,6321023,626033,2103802,6468010,1852102,1133856,3891923,8306407,9758834,2279366,546402,113785,4217563,3184284,1089475,2633285,8180856,3669180,4299036,4664852,1944223,5024879,1999667,1445464,6681879,1242087,9780251,5791787,5562559,4544979,7885452,3229578,9037472,95740,7458869,3243087,7085243,8499835,1087995,9483497,7555116,7429895,6740791,4749758,4083200,8879295,7272174,2101592,5795416,5086074,1025922,1968830,9026022,5936827,9483204,5195819,3768008,1986277,8873616,5297240,122612,4321571,1367593,6486201,6685311,2031391,8085709,7444096,4605912,371811,1129797,4794582,1233793,5218856,1009205,8897612,5587901,6352697,1378695,2139070,2593110,3049317,7243572,9971121,1363309,3794180,1577048,5284214,915450,7315400,2122118,656624,6979181,1690350,6930737,1682706,9416491,1627492,2343733,6612105,5768327,9978369,2705384,4837799,1029234,3811241,5328676,3894924,1335330,6001296,9382735,4978662,6315359,2603533,9450360,7608076,671975,269407,4706129,2458634,4593928,8076588,3014229,8218160,3896421,8025999,5155924,7838464,4415743,5129314,9551723,190115,2383959,6208398,65545,8500640,8106974,3868883,9231587,4509722,8760335,9049976,1307028,6889752,1228657,9236711,9101648,4216195,8133201,3498633,6515217,4285646,7772413,3956158,8974636,8863284,7783063,5275211,4601399,3067894,6227923,525325,1716196,8615238,4953621,936775,9336746,6389026,3233662,8798893,6785945,8049877,3321633,9840448,3717015,6393799,2788272,2935274,3851696,6487185,4063486,1879929,7426357,961561,7065835,4024126,5830919,2641772,2372612,8646357,4662344,8411087,9689443,9761294,9542425,4868520,479495,8732098,8403957,443689,7967854,1145426,6772476,7580395,960249,663483,3692101,3144617,4615801,5772030,1746987,6253963,3003998,9471752,6544951,3890753,725907,8619824,8677244,3908489,9382057,9000931,9223972,933671,7346234,7624164,1252848,1806424,5457563,6396066,4723491,836852,3315964,8161487,8953383,3124873,7612414,9616729,9047992,3902291,5681987,7082988,2438541,3625937,9849799,1507791,686231,6282926,4602692,6865508,6869073,627488,1606864,1388795,8737360,4546278,5978576,8986787,1947724,7466260,3636264,7354781,9076699,3127631,676194,3944978,3082598,1882695,7293273,8520569,7735315,4185543,2502803,9665272,2602038,200226,8478708,5744663,3027978,7745173,976246,1351527,534006,1911269,3161657,8400948,1915740,9246845,57841,7817542,9003992,9086432,4623137,605363,9004393,3068646,2627973,8770434,4968990,4127808,3179501,2309857,9306931,3412206,9531325,9136348,431078,2770827,2874073,6452144,4082649,8072520,9627120,2173053,2345611,8470124,284143,2034192,6702116,7087866,2831264,1297285,6506002,9496960,1896789,8697859,8385014,3008838,2000376,3780785,7186437,5584158,8973575,9810668,2794747,5278488,1609973,5871730,6693825,9220550,9009103,1422988,2109593,8528740,5249965,8568138,3560912,9404901,9123349,1189392,6175142,4159104,5138014,7752291,8414105,860261,9172781,132438,1953043,7353864,2962489,4758751,8565034,6017317,6256624,6129482,2519222,1497766,7136503,4124888,4710151,9029832,1083715,8395189,4331816,1782308,2259468,1037001,9486652,3955962,2078587,7403961,9460348,9999110,4229764,6415226,4575708,1819182,1631397,642748,5714404,6645924,3317845,8694568,796239,1776144,722718,3634666,5858629,5677771,5879081,760099,9152687,9818230,6564073,5429850,2086888,8275731,6530768,4092455,3649996,9728668,1796386,1515990,8929856,5913379,2105697,832679,9208876,5681664,836150,5194429,8770517,4213596,5802224,9217337,2475570,3598686,3743941,8763706,8884819,8279134,4210831,3737532,6517907,9920134,6462374,5684348,1297935,5824540,1860639,4873503,9039135,6053523,5840985,3220764,9340301,1333489,9291734,1463788,6733605,6966320,4153803,8564671,8142331,7397862,8214410,4952023,947870,9270471,6256104,3473295,5253439,2754748,1838711,4646720,4643970,5368493,7777085,9670217,6537962,1972770,7097566,7056076,8076587,833524,6610695,326284,6196106,3258780,9755958,1185229,5557271,5884023,8148710,9299139,4935582,6866539,2319143,6382396,2657435,8776437,2992426,1567081,7733507,5473212,9571462,7730434,7109598,355595,3988331,5324009,904461,8353599,6641606,1666684,375619,8636393,14953,2075742,7351381,8690148,2605731,116704,6953021,5384606,3636625,565615,5027977,2363070,6634438,8432526,5093247,7871165,1201601,172060,3410761,3989627,4803762,4930600,8351612,7597285,3006571,3557987,1626508,3719599,4465046,8637070,9920594,4438707,306814,4144159,3121815,3839367,4190879,3093158,8410684,4415075,1888048,341855,1924367,532859,3617862,4525943,9069202,6313585,2658113,5367864,2352512,528017,566151,153522,9520861,1641698,3459215,4891478,823729,4588961,9597380,8929630,4480039,2133844,6849612,4234439,7781892,1923071,8909956,7386333,6083574,2102516,8256311,1892104,8502882,5811370,8059020,9067069,5283464,2985884,1214889,27527,8703084,2651443,5160197,1603680,2114282,7109782,1188799,2579699,2510252,9234113,3815491,2493488,9942401,5022583,3729679,6740125,4225736,3088398,435098,4449899,9016373,1793554,4066075,4543087,8983438,5314108,3448052,5530503,9629983,7650595,5886385,5917542,1277359,9385162,9481032,6908056,9291437,6411754,92930,8811999,4490106,613639,5629985,9299370,4186574,9116976,8786984,8156747,4104686,2491948,4138445,7755974,5936549,3049722,6964687,4744846,831988,3672753,1244147,3898348,9741885,2248326,4827977,4537101,2714261,7681574,3402840,3850990,9280783,7673270,1236964,4477868,6423914,6482475,6942918,921842,8450245,7340673,3241190,5646803,9153096,5534976,6214372,4225443,1134980,6351141,6425051,2689439,7148610,4952926,4494198,7561001,5928289,9953736,1704299,1447800,1037989,3212785,4878764,2166820,1181228,99588,6055375,2028298,4752637,1223621,9705738,3120422,7819706,1594817,1240732,3467143,4090687,7155989,9796201,1982372,4302461,900449,6018123,6257265,742532,7760476,2278118,398367,2306553,1763301,2387674,3009690,4765013,7459381,2296279,92739,9271328,4105967,4428634,2894757,9036736,59008,2459891,8266019,6465493,6004643,8392916,4391705,6141417,4082793,7442436,7301762,1745197,6021661,3912289,7633513,856122,1571082,1031791,4120432,7481169,7949493,5376745,409076,7185217,4534280,8685499,6912700,884069,6737183,7575956,2892712,5861247,5971577,2516744,5903902,3223538,2045945,1942049,3629172,8311481,4217986,8466065,8036909,8121333,8752211,4759894,1969473,3430329,2368342,2650153,4838151,2129313,2564470,9620352,1329215,3968154,5712152,4555001,9241581,9257685,5741327,4482548,1501984,8042439,6006712,3128959,4629922,1105987,8942766,2174763,9529495,9384603,24155,7059445,1647960,3075573,9602441,7649886,3321733,8746528,447229,1301213,2673626,1377936,1802872,8352738,7282053,7284096,7305939,9419569,9454463,7513966,1935055,4662407,6366555,6504889,2936793,3649723,4152412,4934769,7339926,7731136,8980024,810298,2428367,7300747,4841109,8749372,1433099,5782622,3258166,8996360,9525558,1060253,7052166,6579174,9723938,2704459,2778558,3511355,7404380,5902597,7876424,1921530,4378618,9895271,1427637,261366,8469597,2993532,4905767,572645,5133537,4884401,3849325,7468441,4282474,3194111,9602919,188095,3343826,3491852,389665,95081,2335376,5905737,4798610,2705554,458295,6106682,9715433,3533094,5049305,4997682,6373602,9466298,3790953,5529615,7782618,7142241,1090835,7720635,7901045,9459463,6356141,8319501,6128207,5291328,8435496,8461510,1693988,945900,6451184,1949532,399041,3323444,9607433,8132366,8834998,8740961,8785920,3646578,712811,3448102,5708598,149544,7803190,6252762,4092603,6248838,258368,5654391,2538425,176386,1565525,9291471,4723313,4268036,5734249,2198024,1616266,2568494,8305692,4518918,1026923,9565732,9561954,5193325,4365118,2998256,9428061,519416,7564101,7993924,4745503,264630,333174,9839595,7220145,3042263,452406,2210628,9433273,795278,8067077,4358456,5328657,8014680,9805424,7904549,3020305,3038048,5818414,2250811,935199,6374234,8303397,4151434,3833808,1841413,487405,2425799,2684210,7724461,6996957,3147963,8717902,197866,9358940,852539,2778629,510644,2702529,8869722,3986013,401109,2005206,7056813,4263469,3049029,826211,198361,7243188,1668477,7572537,6308679,6630174,9791283,5306318,8284267,5462919,6671500,6997617,4563783,4196364,8128494,7896299,4664005,3178610,2968292,7918212,9938561,6073086,5255681,3966273,6926741,5942207,1360081,274729,5786854,873830,2369394,2163957,4124710,2688323,6467152,1708849,2369275,2641253,9799530,2547828,2021530,7790642,7707217,9541301,7751692,5250372,3351669,9025527,8091730,3208686,7948992,1329806,9046642,4445764,6057590,2462964,2436955,8783768,4109475,5097767,2382785,325784,9936867,5167006,5229572,8786557,335598,5302830,1791622,3627484,4000061,3171475,8231747,6782812,9080148,3253632,9912763,2738614,3054398,7369595,5979606,4921521,2925405,1744391,8482332,1346997,1902332,7440534,9933825,3076079,6546011,1845379,6390218,930655,8479229,9694888,1555806,9824593,684773,9092165,1815560,6941919,9543651,6680427,5309635,9911006,926912,6376574,3843108,2164553,6153624,6846715,1213524,5379366,5712369,5146604,35282,6113394,2896753,6495017,3919035,9622688,6009302,3610702,4964522,182035,9173945,6960476,8262729,4111544,7792430,6934805,283139,6307794,7985767,8813902,4891239,1450884,9094965,5335337,9603013,6091689,6180683,3689163,1673249,4123052,407872,2103570,5634048,4748093,1693442,186938,4206939,7217712,133941,5577871,8604133,4227529,37927,7943486,4277558,4597774,9771679,6938738,15480,2796240,5877317,7706032,6029469,8539695,4526005,2813802,1330999,2393988,2031969,1132044,7710854,1795957,4747962,6819104,1528747,676989,3386239,7592374,5091720,848569,159748,8704382,1929742,3102577,3104485,4961246,8409534,4031411,4687353,4835030,573707,8747208,3506832,7230222,1340456,7123951,1181893,9273428,2132227,4897021,9166709,553698,5019947,4801802,4311857,5127388,9168428,2917498,2360950,3133926,8917331,2485665,9169439,492635,6984103,1799492,4096346,4475213,6720159,2760606,1276706,6532466,6310418,3124436,6338775,3933970,421077,6685870,9481612,529798,6756405,2334462,2657658,3330460,83166,2892847,9478995,9567390,690828,7519134,8648225,5776116,5788678,8172778,3854642,6928483,8597906,3368597,6601396,6382192,7422199,7601845,8780301,3596651,7893824,5751829,9963951,6812319,2607249,95141,4997985,9065779,2581900,3611107,1831620,4878963,5695005,7000876,8109768,9589326,3716509,2075994,238341,8645879,4374429,3779305,3703324,6980956,2175949,5929327,2229639,9884782,6763817,2506521,2744515,7562437,7259315,7073751,1780453,951533,9414290,3466619,3107388,3036007,9847800,7814700,1490487,7356416,2689020,7025654,6811771,5718810,7227962,5244312,4121564,2917193,6989494,8749266,5312293,9719569,7598900,8933705,5288357,7321846,7107594,8293579,1974118,4802616,8543568,4451715,1326399,2983879,5621599,6903808,1223561,4547845,6323566,5106991,7948295,5094283,1832487,232697,4108296,1080648,1097694,6833353,215561,3537477,7921907,5348568,2454420,1921075,6029167,2395759,5454304,3173990,6536205,5615705,7555545,9927843,7457908,3439781,8753970,9077626,8681095,4489792,3357419,7035606,7030520,449367,4914547,3905190,2467790,1869709,1110440,5664686,3529944,8273908,2171798,123043,1374021,7317928,4410233,3944124,7897686,2290642,9324895,7308385,6292343,734005,6161951,1965992,1508851,7390900,5549071,9131252,6086808,5595230,4948834,3618398,7340392,1166980,5695641,5663317,5271151,5830847,1098305,2279565,4987893,1035003,6988353,5744476,7096402,1775837,2213115,9256684,8467907,1776921,1282162,610665,671930,9709607,2007768,1147480,6804283,9923676,4974037,2890131,8372589,3231213,6164449,4045908,4468760,4073361,5318622,1037187,2875871,6251485,5788322,7115390,6989676,9088492,2024705,3739200,8523973,2202057,4687255,3389709,6193444,427265,1370237,7065250,7465828,2181322,3697175,7236083,2039783,1067248,6524045,8109897,8854249,3852570,2365683,4952883,9248423,7050572,9374644,328967,6211691,9192321,4122858,6899393,5485592,5206349,6974926,5372342,499265,1497575,1287332,8814073,4758331,31574,5146933,5387720,608274,876936,2658038,8434938,685922,9290485,7582080,3368414,4383094,1284136,2705980,3488280,8348998,90755,2031330,6458637,3876515,5670394,4018916,4735901,9445739,6392718,3674280,6240860,4817243,2566884,2038864,7414446,9806251,1881806,1705732,3573602,9895371,5512371,7683072,8947598,2023011,6760756,1529437,519012,4937244,9084274,8591540,1505219,6234357,888451,2715880,6317806,9417688,2560150,743000,6824184,8490202,9961827,6341094,8998383,3513504,1878608,5603777,7610893,1664704,6427969,7684538,7656662,3560438,1368240,2742047,5243149,2368472,5285542,5513558,5890282,6436425,5884175,3593275,8650609,3890872,40867,8697282,8448636,4939950,6987169,4636863,1170783,1473731,6485576,6069968,1868438,2686996,2456369,6795394,8919544,2922454,5215735,6790574,3757435,4811606,3985385,2386013,8609578,1998925,620969,8268896,1488910,5585931,8378146,9558979,7867143,762851,9261817,4943424,4164026,6875397,3937752,7857252,3765634,8571507,4628110,4742450,2329519,5654008,5580932,8858223,70980,5774123,2313847,1845104,8723591,5648696,3905297,8489905,8098229,7016567,7857347,7783914,8931733,2160866,89965,6684505,6018194,6067966,7682044,4206476,4699208,6253060,383344,9248541,413186,866311,6955589,9189187,6679132,2994266,5746955,9637222,5408128,7825140,4768604,4094056,4262484,8292318,6099568,3231344,7573512,4038265,4721686,2983507,4818412,5956688,4757948,2586859,7501615,1313113,7294681,2013740,2548708,1835525,8872394,9435850,568517,4277287,1975097,5369711,4128574,3361747,8129607,105250,3839221,6820501,1071560,1293566,549643,9981369,9019636,6651385,1564471,8214716,1916688,8984265,5421097,7092654,6606759,8534591,4420396,3319458,9578714,4126236,5522115,4368915,8880023,7924868,2341611,6741846,6994919,602402,5036977,1400519,1817537,2953945,8833541,7196582,7085344,8498239,9347399,9835546,8683527,4780188,8799876,8277363,3637984,744239,3858640,9656539,1973388,6296302,7237944,9684508,6940751,3636038,5339921,7992946,2726285,9392228,9027608,9020489,438558,7358566,7904154,4606591,1127406,7582427,3587245,7892296,4841602,3171631,4397582,2905927,4200214,199239,6155791,3203511,3585470,4252475,2253242,1422291,7365006,5056316,6178530,6067870,5842043,8610325,170051,1433824,4843113,9730967,8002368,291715,1499172,9284763,305709,7910625,6898857,7927625,8947800,9980032,3990786,444589,6198595,9366087,3660269,6217125,8988619,7505939,7454100,8936125,9577386,4755370,4425954,4531924,462303,7586995,4864524,8465121,921243,9995053,9160410,179542,6559995,4680327,2732455,8924344,1053438,3224823,7833960,7737013,1433806,6850169,4914804,9691443,3285781,3586812,650606,7962014,1102880,6364691,3788248,971009,6310627,3215951,6868456,4726179,7885991,7787432,3811098,4732273,8930245,6584544,1348744,6750316,9092865,8839684,1481011,9605695,456746,2498681,8144522,7272809,7573692,9595772,2165045,2522963,4502671,4246204,2384663,2296235,5834863,2672151,8688056,6849383,1016104,5545360,3379888,4359747,1165457,7486746,7756514,5312416,1479442,9123063,3246442,8758146,7752201,3075921,8757925,1449518,3721854,9101134,8645671,9058635,7809246,7646702,5608425,7779435,7537552,7352037,2824870,35248,5065718,2665870,4130632,700197,7965781,6047265,2652843,8943680,682322,5254672,6344354,9103565,9349192,4912910,9859977,4612505,7755247,5895122,8705519,6788384,1910941,582408,5917553,5372588,202887,9069803,6422264,7286347,1499311,1362764,6887502,8924281,1751150,8102049,7628810,4213522,3747316,1795681,8647760,9713479,7910794,5373417,9374510,2071514,1686774,1152850,566254,1686057,3470121,5409946,5841661,9512059,2757105,3058302,8556627,1858360,1403448,2385210,4514323,128596,1760712,7804940,5417498,1383032,42290,7846772,8868423,8001404,3671120,5190006,2609846,6028053,2214073,2472008,878757,5390320,9872892,7392042,1635901,1941020,2179790,207991,5357542,6117405,5879798,8461458,27026,9833283,2342591,6803917,7385654,8096659,8254105,9203558,3235347,9827956,3402336,4158721,7212410,7852847,1132880,1244216,8962215,1817219,818458,6053613,4776576,2080660,6195495,3154891,510647,784311,8747783,3729822,3814812,6025760,2277007,1908719,9009745,8025703,7032252,4948161,4559977,9877645,68127,7694807,5346155,7691967,1019265,3406656,2178231,3455297,1402369,7483082,3817442,1438858,5051551,9206675,9883298,9159446,6320700,512517,9744949,5398587,7646317,6848811,6249890,2780749,1446110,1687700,2312239,8186303,5050371,848447,6251716,9261059,4166237,3569596,7626245,6297350,3969098,8620245,5630623,7793786,1837190,492155,6591216,3471494,7977997,2021656,7588102,6420009,7708865,4370313,9360057,1154866,6678222,7090460,5542054,9862824,6504046,7377126,6613478,3965853,1281132,833677,2053656,5947812,7245111,5996464,3692974,9530008,6441405,6100524,9666912,9859908,2321492,6078486,6153096,7709435,4679203,7457965,4405161,1838338,9216536,8024137,5659705,5539229,5626752,1526570,7621132,3072386,6134054,2611137,2245494,745512,5051685,7252841,4306710,3066382,6390987,1729248,5801211,6256459,5343003,706058,6993062,4235003,590846,5502497,1668248,2203459,9518482,1011540,8274970,2899489,3639180,6231316,4758495,4062568,8948679,4664996,3222440,9132970,8491865,7534394,1261556,9906844,7701337,1710114,2895270,2594530,7876116,1788003,4586287,6406322,9159778,7184119,6268808,6657783,6575725,4190499,6722492,3326227,1939125,3193828,1827618,840799,1643514,208712,2312093,9067023,9633405,1752503,7858594,9818081,1105173,2145204,4681648,4740684,2937677,5374430,1163624,3574325,9199213,2210710,3495600,2155964,9585040,2421263,6991126,938255,8765320,3220549,7954037,6564285,1508698,5984001,5552385,5942408,4413689,6787559,3935710,5916613,7865921,38158,9480236,9368025,2255644,2793544,9403792,6519170,2303978,4326914,7543520,7647612,5485559,4501997,505578,7297093,6368799,1883026,5468603,1244497,3138119,3317823,7190703,2702640,858847,8375135,6441050,6921003,4572131,1136039,9286729,6603537,9009751,3825863,9139220,4615508,2229063,869101,7939760,4357919,5278151,4917501,6208347,8066526,2738525,7823354,9720274,8114095,8255868,7590213,3590753,8536849,1679540,5233779,6339300,6429365,8205304,7790439,3545521,510572,2196265,381546,8142864,115552,8724756,6207007,3255271,6496391,9739858,6581609,501542,2496079,1853425,6758718,2978531,4865518,1575157,4090627,526740,5470466,4304610,8612723,1048349,4747217,7245996,2648478,5149624,8816039,8670635,3376875,2336653,1715167,1603085,3253494,186153,5128320,8435180,6416290,6757088,1074574,6055149,8417507,7578533,4751870,9459102,5767916,3343595,4160970,2200724,7195916,7077476,341367,989913,9421031,7039910,8751752,3297139,1288767,7649435,9982307,5285572,6461147,5789520,9645916,9085393,6727358,8719250,9956470,9807587,9054706,7973972,8550049,881875,8626528,4422675,1317724,4701040,8520243,8210923,4652265,7567290,3148310,2505613,3715271,2135396,4260997,5383299,4093741,7978916,5853051,9639981,1087039,4814565,9409073,3288540,5990171,7058653,9980078,6141454,4234302,9412059,9488553,4668042,2374887,3601936,850202,6849491,4353371,8506345,8891740,6983982,1258982,2453787,4528071,1838256,5333884,5709708,3994080,8865527,8798978,8100832,9959005,7651888,4650475,2463941,1554404,2160082,2240148,4259491,6933142,9503638,3600690,4640763,173244,7109385,5978658,6663387,9511991,6589664,2790084,4271264,8577307,2276795,440666,6658713,7079436,597541,7022347,5037867,7269082,3613710,9648550,5080035,1758488,2116274,1255587,2284611,2942109,6812388,4827259,8659432,7705849,5241381,2964893,3679193,3368282,8136176,3594849,2512677,6154045,4121184,9460465,2469856,353707,7362618,1082467,1839206,9329821,342304,4219162,6002467,9501820,1330795,4941475,40518,4885573,4164801,5154087,4081322,9578154,1164860,5370518,484626,4207632,7173741,4103172,5556814,3441781,5848317,899935,7249251,588285,3418635,8373529,5064057,4435109,3052518,414947,2805809,3702322,7891379,4549460,4109670,3470606,4014310,5087936,2982669,4687684,2697335,7339039,3839085,1516084,8049793,480413,1620016,8662583,7919371,580182,732497,9965067,994738,8060903,1122220,8818016,2710625,869199,8210243,6465745,5450862,2169513,8651570,1101532,252793,5157435,7715327,2134709,4978789,4624268,2728037,2396878,3022013,173367,6390983,9722672,2262318,7661753,5538333,6776629,4738972,3515421,3554322,349518,9898588,2444790,746688,4636704,2044048,6007379,4327335,5085425,3764638,568875,3160864,3233417,7649938,993752,2165999,2103390,8038383,5673974,726352,4067325,8791138,3179050,613085,5550861,6639559,3022815,4666753,3250752,7371985,5589908,3701021,4204936,9989931,9212857,9915359,6957265,856966,9510386,7019950,3415348,611234,7663928,9351538,8679840,3220877,5350805,5161675,1757186,6822054,419559,3137630,8213685,8316413,8659203,2922678,184058,5936093,5251557,6328098,2685598,6103991,3548121,7366064,2590762,8842471,8991513,750933,7195535,676882,1358378,5961265,5402414,1578117,5801176,3553413,497157,4854815,7194349,9829327,679627,7183946,5778208,6169398,3832596,6827163,4264038,8986378,2781432,2354005,6736562,1762182,3756233,6807029,9956004,88583,24431,4587833,3052801,2055723,3522595,1091029,7482922,251279,8928631,4361009,1824412,792685,7797958,1119491,7969507,9449510,1027846,5295602,8878765,5813794,6612247,333056,2393471,3981538,5691844,8676249,5534119,2977277,5109630,5600848,1027456,585124,5163628,5358899,7097787,3021203,4119372,3284275,442810,656140,1062462,7385178,9297614,744599,5634482,7304558,5487765,8301745,7036503,2781171,8430346,7310628,6324642,7723323,572860,625933,3931742,2070133,9819822,592848,3975603,734358,4133732,4143223,4795644,4659016,8005407,6302884,2357157,6948682,5535285,6511607,998010,3111617,6416445,7486027,5823176,8944258,7218721,7621225,3529714,9436881,1653326,8927082,9519829,5631539,9976170,32565,1493212,1495264,5352777,5571107,5314674,33611,1722672,6491703,9825698,819184,9778232,7617800,8617227,3923355,8502578,856120,1474724,9894301,9818390,4502852,6100069,6708084,9911108,7636687,6264115,326321,5129844,8753236,8529230,3225444,8398962,9065609,6832790,9170504,2348815,2662189,5901957,6358495,1526392,661666,3743044,1003436,7651391,542422,4596586,924933,1245611,4460179,2519670,1148567,7058880,1114838,1799772,5244372,3802518,4601555,1482043,9885599,3384009,4205374,2083764,7056940,1681907,4852602,7088768,5630095,2828425,1006489,9076351,4234959,7478290,8423559,5335846,7346380,7581775,1110196,531816,3674486,8212552,6688074,8251902,1620857,4041693,1380133,3536851,5522397,2361334,3097191,6968431,3450205,9217730,7196974,8877859,645525,3429146,1377990,3243027,4998728,252642,9270543,8743942,2863231,9549647,3093386,6260378,6963595,1440545,9696021,1056634,9964841,9073479,4518108,3930670,1835250,8363349,1316722,5357987,5144833,80289,4437260,9487423,193586,4208325,2038387,8259977,2636668,8374951,2092518,2966218,3940495,7071465,7080183,1196490,8992235,7683934,2041599,1402828,6438197,9258506,5501352,5143011,8713380,6396197,5651507,1548356,721114,7008269,2387023,9048868,6714702,6666833,3386762,3715424,7419970,9941964,6899689,8470716,6246492,6310119,2116127,3360542,754781,3752972,8559068,2381399,1999893,6557791,7003121,3075123,9841842,8494188,608767,6990318,6676947,4979888,6588074,8212287,6722481,5021355,698540,7068708,7827476,8196157,2525064,3983519,5177467,3023406,7863092,1642964,4059357,8953050,1264843,4910114,9997366,1846902,5831118,2056749,4211688,3458007,4898659,5698339,5570069,5895583,4651590,3961519,1612127,4475811,3180969,9682753,2380155,2269749,8536545,418912,2476342,9452311,2267866,9202690,38869,9150436,9941384,674724,9600936,9786328,3236300,1285382,4373831,1248953,5037581,33139,7454864,8202560,3367866,8396586,5563391,1864796,1348185,1375194,4212310,3087389,96597,2303120,7260682,3851207,5326005,4021110,2995874,5892608,184973,228093,1273154,6986783,4287531,5785517,1698681,205368,9219374,5783281,2608440,5708958,7464190,1256802,3539114,6983651,9440657,3772527,4724032,1940103,1821312,5975451,5893785,9292136,2933170,6161525,9931900,2975358,655609,8903196,4061614,4770952,5709351,1808052,4433347,3117021,1349782,712375,2837957,3960359,4007811,1578102,7178134,670905,7633013,5298558,8736042,8593840,9629390,4832958,4389509,8651451,1456623,2633784,9373914,2089835,5826524,8850224,3360074,3828876,3318857,4046303,8244462,4997936,9572957,535680,6989839,6803469,9518508,2058425,220906,6643303,1196025,1775695,9786094,619025,372742,4296546,8719491,1329489,3562548,3182679,9718246,3417614,8108059,2340194,1665193,9681608,3866952,5213980,8207137,1292806,904766,8528906,7391017,8304802,4134668,5655719,5896332,8121629,2946908,2185414,4332301,4982844,2741265,6119969,5600395,1612056,5299362,2660780,3163559,77576,5497128,3780542,6559557,7282377,6861246,8109706,6468170,9724697,329007,2750617,9183700,4564819,4787419,1896527,5111348,2828240,9277092,8890050,9804708,3990500,4243537,4606147,3176524,7680855,4137380,5275404,5974453,3569397,9050535,3953487,5706085,9637651,9250019,3475584,6472274,9350700,8819442,7697090,6466136,9926389,7190615,6134186,6992202,4889550,1474344,1609609,4701441,1379100,7325732,2722572,571014,5999453,677648,4398440,8079671,780744,112339,9216698,1648723,6440073,1969415,9309181,7010717,4493610,8440864,9619480,9062489,3437351,9527938,6836409,347116,4946789,8585381,5032843,7420633,2866670,6250936,2901321,9540351,4680021,3730385,3012870,4143153,5078873,5031802,9686123,3700563,5031983,2304652,1420095,2004817,5479346,8676013,2943449,1533228,2975569,2774645,4599334,3958517,6616681,8207108,9278852,2247016,2273798,3487873,8249518,7244438,3372462,3215386,7673488,4021883,6693262,2943803,5816234,4827434,72087,8083047,3042788,8375657,3186207,9703686,6684652,868083,4586403,5069351,3828479,3630669,3275824,5335646,7456494,2294323,6856013,2446766,6085285,3786501,2124599,1681220,4143282,8221581,5210482,7383406,6651478,7691822,9251769,3933812,9417115,4805419,5773270,8725673,8452580,363404,9975350,3749293,271340,3736409,9638590,4122033,9042110,720499,6254540,220457,1987602,7306184,963410,3240679,3398237,63095,1219210,5620403,5664636,8574400,5783220,9071129,4175313,1032673,4280046,6927606,4981857,4413465,487832,1512650,7836546,2722790,7636292,1656689,2595944,59094,9240115,7834821,315670,90011,5381104,5601304,4593337,8901665,4424200,5382076,8098245,5017117,4255194,4661825,5046809,686437,6509493,7838273,4266162,5110343,4446262,1209697,5212299,9902103,8705503,9961369,2894781,4636664,4871303,2504100,3776460,7967941,2158766,8874165,807492,1455730,720523,4486980,5690133,9664031,4119204,9721220,4070380,7690227,3875374,4096806,8809277,2969116,6063471,2443582,4355547,153915,4383999,9825552,3296223,498481,580132,8343169,8766939,697058,8148009,6687626,3084266,1495353,7451994,382260,7736623,7516064,4046109,7417719,9973186,9729391,98004,8757638,8114748,8844571,2990439,3199938,2120787,3215585,5781969,1633874,5583124,8245707,3982781,7660689,3027570,4042354,665780,3443581,926346,9732825,7307106,2948828,384892,7773637,4330201,1736696,6129298,4830985,4859654,3638969,9423735,589083,7571278,3115892,6250769,6672103,2979328,1142373,3147657,3192041,3426010,2104258,6755681,3092933,1332695,9402049,6017001,9821694,5172709,6194481,2774913,7489531,5311490,7142773,5910437,8172011,9751445,7007364,296307,4280080,3845677,4815402,3254959,5917439,7536849,4663803,2485859,7066422,9178151,9326104,3357986,3033419,1658633,2073589,7446930,1652071,3558122,2140139,6013625,6996612,6054335,4626332,921058,9756686,7621696,3818617,4078540,4144519,1962604,8781252,1658594,4219218,4746169,9437180,9560253,808823,7763051,9598740,2820523,9975641,3467256,7554291,644721,5021719,7271347,2812291,1438271,1139794,2136388,7496575,481449,6455745,7115161,5471474,7591199,8027197,5165673,9154694,3185413,6397134,5245812,7529421,4372526,653491,622797,9938206,4311332,3637990,7764484,2511597,8733515,802429,9693690,2065370,4277815,4392340,7571890,6886701,8608932,9687765,6972586,4435744,4427384,3001312,2956937,8654277,8824562,5597797,7944907,7509331,7177965,6036168,1763701,4648200,6953177,9576504,6868520,7715000,9764762,9469496,8197050,6721491,9959193,8319312,3635107,38197,2931039,378675,9694450,1532014,5100299,818642,3946570,663514,7937688,4346849,5690970,3006872,3136466,5126006,8389431,744553,9676104,8852436,7539275,2769420,5673365,6643507,7996081,5791690,2434091,8069646,4000325,8099914,1373815,7995864,8052158,2241803,7752574,2832890,481394,3689343,3751507,3256479,241943,582862,2200127,3913190,9095007,5040102,1520079,7492021,8728498,3861693,5692513,2256515,7262685,8028171,8390773,9925608,3965438,29045,523740,3846430,2376087,9581042,7129321,8368715,511266,4752419,9763299,8336719,969893,3698999,19599,4440783,2555987,3073247,4603178,6993436,8874887,8795565,2659795,9571825,5831892,3569326,2456215,4814369,2231348,4068299,7725254,9521904,3177420,232089,3168445,7466871,7609387,2987260,5368570,9962171,6658630,2570589,3255453,4866262,2270352,9918284,7365714,6446913,1815357,4833725,7059552,742179,2438470,8530053,7164022,2052341,8614317,5567574,1404803,1348304,4137710,1642545,9584473,3934709,4465152,5936026,8328421,1509740,6656043,938569,5305114,9239324,5809637,7841922,4199527,7282907,2477610,9439996,9695922,2539780,7070666,2977161,1945674,6589632,7534503,7362831,120448,5340578,630073,7819829,3959544,893102,8770659,6399164,1060729,5568859,39113,1021678,1536338,9003477,5051201,7631406,6041056,5252991,2050899,2656506,6543060,6422391,2386484,453207,6646156,8971645,2387981,5258943,3292215,3652041,6634096,4878644,2921491,7752402,6987802,9947833,641445,3228646,9238939,8356771,2052095,6369336,8008937,2709423,2478475,9236933,2791437,5462559,5343609,1624905,3798844,1632762,9403009,7348334,4727627,1026442,9357741,7154921,4077816,8800744,6681590,4273938,8088445,6806412,5438879,3199509,5316111,2275625,5223410,592248,3012845,2948279,9889030,9849071,4029217,5112140,5459267,1605686,9865882,4761635,4834458,3765536,3080220,5447853,1405803,5750792,1561919,7246843,4020414,7494322,4608176,2773109,3709888,2683984,5190274,6136315,4483220,2855737,4652585,3063982,5631713,4819326,2880204,6718444,9743050,8605404,4662054,8427112,3858526,6604954,6367208,2959336,1034337,3326365,2734408,7669657,9203728,3583073,5011240,2964178,7575048,5391554,7865927,6385546,3785355,8395427,3825556,655041,3523602,4017980,1149016,2382197,2353498,7151082,4013808,1052113,2642773,1595972,7817807,9695281,2987874,9517366,9713989,7830834,311665,7180230,3868050,9634378,6864510,4004750,2514040,9375625,8769058,8208274,9181032,7145904,7295903,4716524,7855693,623215,8900517,6000487,2101034,7835656,1737632,5250232,5915833,7960478,8535891,8390213,3120900,9159646,2349998,163079,2409796,4868611,6368379,8665216,4996531,7955172,5330710,1728945,2238101,2015781,5893395,8556747,5449834,2891088,1222816,6958765,7259217,3629642,1179123,546044,177610,9474277,8432315,3801777,9350941,6214342,49083,569584,5231721,990356,1165582,8413430,9531019,2684776,6527383,7508485,7042932,7617766,2189207,5362675,9943480,7599281,1377529,7924339,2827573,7632603,5830439,8611747,1753270,7951498,8481179,3557507,9198662,1708744,237241,6268405,5963885,7533106,3467809,8421265,1697234,9921687,7010064,8895808,4330976,6258408,1906133,579417,9779299,1182191,4150928,9737748,8011210,2551799,5287632,7074356,494868,6320889,3266837,1954171,3898904,4757426,8579595,9463490,5467872,9323130,1089748,5298838,1036765,9456277,4363127,6980451,6592068,4870570,6576428,1089664,1188422,563703,951779,1131364,8722896,9946089,6349167,864795,218927,7868047,3820562,6830348,6592992,9909318,5643721,7280943,9859458,2664293,4772407,809254,7637165,1964742,3492690,4204740,5570913,1614060,4247954,4984573,5900653,5613539,8844825,3051224,9252510,5709374,957503,1550522,3301851,1388535,2792033,1239734,3955205,9219616,5954531,7270,284961,6425026,7017780,2297593,3986968,5624388,7832931,9775315,8772809,7007397,1039180,5982651,9088217,7381418,2137895,1123798,9415539,462423,7089497,9281304,3743177,1676711,4665229,1761967,5193466,1796179,5704630,7287413,8937849,4390274,9582213,6405324,9918662,1332563,6119557,8510308,153972,2787321,8736211,7572358,5090065,3796040,3681178,1670699,765201,7658710,3280527,8911896,6286147,9168069,6927920,2601018,1451948,8572009,6887773,4751307,4132723,2869918,629888,4355767,3568707,6929473,9713707,1043795,7650355,3459379,9404963,2709825,3964571,4360054,9774628,6112072,1473470,4536441,9424581,9991910,5299262,8832038,550059,8751461,7998223,5073469,9284975,7187670,4315433,8660663,5492920,1630260,9952351,2513093,2507414,9882251,8905963,9592923,9572052,4514826,9385134,8810484,3303235,5289209,1379163,686825,1207353,7390975,6051583,5860846,1551214,3050962,3501951,9932705,7487390,7793294,5335839,47086,2924521,1959186,7531163,5500516,7592834,1147967,4802178,9046981,7809613,140325,538499,9384946,1343411,7937069,6210072,5000523,7688961,7967813,4228016,548742,8306738,5916067,927565,4139191,9457947,4690959,9932905,7046138,2763229,3301275,4449229,537351,2846799,4329236,5301384,2864534,9796765,2715515,1520740,5747017,3444372,5506339,2574328,216415,3476980,9520548,9942040,4439740,280024,6289355,9714284,2282121,7948312,3110500,6014657,1014529,8268549,5927181,6271422,5698329,7052073,6550872,1867370,3182994,9623602,9241429,1828698,4121447,7968007,5168324,9391460,1107755,8142998,388573,6041468,1042557,739126,9969191,5713784,1514897,1191926,4622924,8011527,4890451,7397026,5543491,4386472,7322649,2137761,8705492,7910524,9419311,1907051,4550106,4438824,685877,3443588,6038175,4961919,4812653,5758550,800909,4069145,6909405,1572438,7973028,8151391,3704438,3876007,697387,1593370,5822845,6033536,3221536,8076229,4050952,788201,1452505,7823886,983623,7281939,429369,8720781,6738055,8164344,8356674,8499227,9714836,1501787,258488,9891410,2716565,6353867,2715096,7347821,3187879,6437394,7161183,3656086,8520899,8860984,867304,4331799,4003804,4533738,3224576,124185,8139881,7157812,5408605,1166142,4336227,9213941,8801432,2276381,1960095,2741599,2672431,8949368,9160593,5158144,8726025,6111869,187732,7499592,2504243,1384842,4701210,7414033,6866430,9859139,56123,6488824,6432277,5210035,4266509,7015126,4129298,9121694,863923,5683513,3960695,9338922,2873453,3576762,8089554,2674635,3070617,5720203,7450104,8622877,6578943,2353835,6333801,1268353,9008965,7163173,8646289,456147,9259661,1590862,6614240,9878138,3296616,9435194,6019494,1006217,3878668,4486708,1742401,8133165,9921476,4763373,1668974,6575465,3652464,9275965,9935637,2119161,7284560,7650031,8000129,7499517,5748781,2446188,3641452,8916242,7381197,3173510,379652,1714400,8834943,6149807,5979312,7922796,6451861,4705096,8070241,5153228,2573897,2618366,3562530,3405522,7083502,3242192,9293174,7597941,1218708,3328485,1822793,4224513,5084422,2413029,2655945,9605696,2896124,7939249,9311035,7232910,5793245,3053891,6784106,2697667,8680748,3099967,3805562,943459,678179,8221108,6627063,7341072,9807902,6931139,7371914,986628,4271909,1733230,5781418,428959,4602457,2151564,9667854,1762471,5757270,6378649,5138636,7725880,5379686,4666196,288123,9828186,4698624,9113892,5689021,3392179,3962481,4637421,2966982,4138003,7874516,1881094,7002419,2453888,1576736,2208874,9683140,890858,9636919,37768,5288961,6144019,457800,8846332,2716474,9867650,7573442,2124938,8649734,4452397,4326628,5098346,942921,4044614,8311745,4383889,2590609,8251512,2943290,535199,221143,4668892,5393113,5168771,8882804,1184041,5807839,4637685,8223827,404158,5318924,2902351,9560393,687753,3364985,4190561,7480404,523665,2883580,5155142,64182,8332874,4747955,4609157,4180030,1117859,9122196,2869588,8657211,7538212,8626316,309393,534630,9221077,1230233,4600155,3949216,2710972,7573047,2664909,2235510,900759,5183943,2609905,8298384,498410,6864033,3330630,3139153,2194451,1581053,6670332,3934687,8594913,5906191,539424,4159836,581298,9437910,3275624,7514775,3614216,6201635,4123244,5199986,9719646,2220568,1141179,7405361,6524359,107039,4981036,8509140,444124,6663142,7533027,8207016,3350544,2084680,1417679,1866979,5596344,847751,6677741,9382549,7840411,7348196,7438993,11307,3925671,1447279,3259683,9358356,7446786,5795885,6500329,5167665,6275053,3097965,4081503,602618,9328148,7112518,9977186,9552331,3039373,6365693,4187377,2385548,8220932,154583,5129032,4846952,207982,2851622,7732955,4994921,9356417,364386,8434305,1417980,1773960,2688419,9639892,9342572,5678821,4275260,9932334,9646336,4606884,993800,155596,1921075,3931585,2056678,9527096,21585,9277782,5754191,1185200,4172,2665225,9459423,8280951,1751255,8915500,8202795,4440378,5646297,3349884,6553060,9556000,6599415,2290263,6465100,9057774,2828777,1350137,4087072,5044578,1787822,8449630,7836700,9119899,1692844,803833,2691804,2635688,7516979,4529079,9997848,3043936,7143769,9095129,5934764,2390292,7980713,6321302,8462895,3801045,555328,9468922,9043564,8766168,6021435,1654250,9942777,1369154,5558086,7079684,4844645,8674682,2868755,2558750,389664,4227138,5711649,8282882,5753193,6686741,1733634,1961307,6638021,7978157,6910994,4233632,7195013,533398,8350551,1130385,5171597,1446801,4361588,2818154,7246162,431274,8422957,6615746,1550812,3336839,1441433,9092076,6761466,2782559,617300,924351,367217,984814,1099402,7888469,5911778,1762378,3579753,8047672,632410,1159568,8293499,7843799,3829392,7883327,2307155,1569578,8023846,2078918,9042097,6502401,3699011,696809,9053265,6944382,6792361,6523825,8479516,8966937,6021206,4232035,5615646,7457977,9924782,7766372,4848469,1641806,2826758,46217,6922804,1145393,3607891,4730191,5746394,9325452,6815558,2036994,134,4615738,4394928,7007856,1082669,1247264,2834099,779631,9995535,9929252,8135769,341325,2762422,1860518,7587816,5678950,1467715,6113563,613833,9567918,8552403,5944586,2017618,9985585,6681914,1092929,6656533,6876322,8810368,2202057,8836613,6579276,7031040,9611119,4992143,4500293,7945383,4351427,4377258,263295,1518056,1228292,6822236,5296152,3986311,8934244,6543589,2920463,7282464,7835341,9529707,4670880,310416,7962387,3946231,4249940,2676209,2673967,5250453,6962447,6642240,8741464,8769575,9852590,2412073,5125766,797473,333353,7144588,4633836,3517751,5313472,6185286,4943619,7055760,7713712,8751620,8759933,2696388,8163377,173250,5066817,4842755,7598881,9699428,2905095,1045206,2918295,5138327,2028880,3527317,4314519,546064,5380270,164045,6741962,1307734,5625018,9111964,7625695,203977,1091599,5891007,3532771,7620550,3807421,5032023,4096131,8513361,9855064,5048771,7003870,5778081,4709920,1064780,5429505,5169727,5424649,8792201,4341643,1963640,483859,7445092,9119309,2174746,7322553,3244661,2706716,5356420,3367752,8803731,1013809,4249065,159818,9906316,5350823,8697040,426791,7128503,234827,3493676,2407869,3232192,4046223,233798,6348775,5412722,1599304,7435977,9145901,3249824,2154217,2539342,885302,3744888,4561843,1383503,798948,525770,2461032,4618577,4894003,5021780,2468178,7436200,333981,7554754,3798518,9124250,292064,7248394,5878346,410432,9631260,4400182,1176051,7863858,7220979,7556223,658367,5873010,7013358,226770,1924986,5737413,1290925,5294424,8405437,4845892,9484695,4845399,9924293,7687707,848045,2888811,4454075,5482814,1627432,3942144,1959332,7296544,6359199,1357859,2668336,499955,590251,5211697,8704134,2775749,4820487,7437204,355246,6329717,1387320,8712215,2947933,4983505,9169980,5034507,6179251,6784381,7231904,646580,3867038,1786509,6255494,1316063,1330457,5162059,3559842,351679,704965,448389,7487381,8687206,6614118,8469176,5452366,8834323,9294017,5606306,7649222,3145459,5571621,1136291,9385266,2592105,5399149,7775640,7330646,2541253,5950490,3440230,6597769,5642341,2715744,8322061,280392,4042728,3745426,9618674,4093001,1650028,771984,1550071,4759505,4395975,4141025,3991205,1083375,9066280,7203178,7922797,7928443,7549267,7276103,4514717,5512478,9982674,1543498,3384648,682727,8770111,4696152,3402238,9946479,3033124,1872647,5349524,3716116,9901043,5580445,5018226,8830956,4231000,3697406,2368521,2149509,7416828,6741722,188912,3676835,5233891,3944146,5872330,8230882,1537269,3447042,5584860,759730,668548,6052093,5173639,4969459,4117633,7477372,4352776,6887783,7104822,5086710,2229034,8433025,7359096,1899342,4702123,1844232,5605342,5410248,3140660,2865132,9023926,4164922,9393164,7251588,988470,1290156,3474363,3393768,8989653,4257039,9234354,5768403,6132384,7812656,3788241,3781924,5387855,4978406,8375198,3020631,2931364,5224820,9241228,9116737,8633934,8338375,1063076,9781780,788161,8764083,424158,580098,2564706,3198529,510936,8321558,4735986,8927961,6883984,4412,8838641,7123857,3937960,2292371,1657169,1370412,4202539,676711,8675399,7476331,6882573,8851913,7331731,4041403,7926680,9874039,3937165,2309066,4718943,7294746,7150587,3924648,4284986,6464363,9856373,8529754,5687592,2929891,2651872,5178555,8537141,3686398,8714262,234343,7222756,2337964,98839,2364111,8372637,5036278,3050759,8112730,3132341,2959582,4423172,4338899,5496930,3988787,9351598,6521042,568356,4057064,7722547,4791641,5816820,5027566,7331031,8400861,9502807,9494894,9053721,5920305,9037226,6565097,6135330,6075645,7367522,1495616,6120182,5322197,3912254,5338218,4513044,6013312,2948644,9409234,1643171,6803613,7046992,550812,9400620,8434707,834036,9169673,4920107,3856390,2902452,4911818,6776793,1778152,4263043,6537918,8611062,5217151,7092026,2544792,1156098,9301774,6621986,5688687,6783109,2916327,1824900,7495085,2486855,8239399,6836463,8127619,8329127,9107675,9098974,7812411,7122435,5105997,6429479,6718380,968179,522961,5725568,7719870,5551713,8692636,3659492,4737975,4245825,5643685,635100,9033082,6178856,2638609,2021001,6547107,1234072,687720,8646612,4428619,4353361,1088026,8178124,8935464,9500738,8353294,2934356,7022658,4463087,7958618,2781428,8478249,3470861,3348984,4249264,9303467,2123351,3947552,6422474,9294760,3444028,4927565,6029035,7380717,7320060,7502179,5575184,9561616,951431,7013448,4916650,7573630,4041479,6409706,7195294,1773470,654471,8937002,4068734,3212543,929148,7053672,329129,7718874,3273357,2231282,9628067,1314190,652522,2354026,6352628,6274009,3557445,5902267,1086256,3470063,9169016,9372928,5896812,7621944,3872398,5623927,6728154,8154045,5623441,7481034,3851310,1199901,1078050,7409077,4266480,5865627,9216976,6239239,4735607,1437269,2796371,4946099,157944,8986674,5847323,2445436,9236795,4667390,1540885,814699,4171163,6838557,2548492,1744978,3522398,4998333,1194748,8013363,8452487,8261395,5919644,8064259,7408834,7362987,746296,3710726,4035995,1937776,5224640,9516043,9852169,786223,785848,6236388,209330,5055934,5447719,2318929,7693177,3793455,2998294,843854,2401768,3267281,5725930,909851,8865736,773034,2566886,3881663,2130883,6645176,6754699,8937185,2832132,8586990,2915529,2846941,2396152,2581405,918006,1819463,3986036,1594954,1780731,4353376,1287852,9578244,5231272,9778449,7226969,7767043,3978944,6965190,3540452,6686832,6586604,8975918,3934744,253404,8256411,6118689,3661276,1569027,8334686,4786512,4838445,9100348,7428528,8314986,6537792,5984580,8136924,4541,2684782,5233351,853382,100408,422414,5661169,2859995,3500235,2541349,5473814,2064187,3570897,6763952,9212770,9592591,8920617,4387740,4952329,5510398,6765186,5003648,6523668,1986911,9707582,4414196,7522027,4490557,5919729,5868621,4939482,9942635,1986352,8609533,517798,9208275,3173462,9509956,2353414,6846332,9171451,8749334,7954973,4317092,1754855,4790051,9429388,4524145,1581735,7462895,6023295,92891,4577834,6623624,7641606,6419434,6652852,4936889,7595671,8449315,866006,7601832,3558320,324009,5114679,5762595,3406124,9462842,1667806,4362080,5096724,6612597,869147,1830005,2673842,1945764,3786756,1310328,8055548,3534324,6946030,5308464,1694922,5549211,3917717,4658331,8342562,9425053,5445994,2215904,3111304,1017311,7988254,4149269,818214,2086695,5748582,8859906,204504,2438459,3044708,7577060,1917749,4271488,9455895,8631003,7264980,8292757,3373630,4309835,8415113,2246916,612551,7056440,4708405,19604,427453,1152003,106879,8452339,1401295,60881,2289891,4959355,138099,535687,6685466,4403960,3870254,3575281,3917853,4589215,2626733,1214804,6348409,4471516,6759168,2215447,9590264,5220373,656352,493,6223687,5698654,2501970,2365683,9562287,3412220,1753538,4024291,7028935,4330060,106042,741492,8729650,8772399,6254288,8468229,5716430,2722828,3514388,6334814,4463528,6681783,8350539,8738811,2085292,5546202,5445642,6122819,1382368,6286718,4441224,3327783,9027055,3133584,4209458,6289830,1290000,1716973,1430209,8005791,8997787,9985028,8012323,1180093,418889,8659618,8750521,2511944,3258438,3763681,2598477,6585436,1234465,7803908,3262661,6976268,4893293,8537499,5504476,2119900,8344615,1971395,4444362,4890757,8079822,5754796,5637038,276735,4455247,9596142,5926430,7769280,6782720,1722361,8927013,6716682,7143168,3811287,6952976,2830878,849239,7939311,4400816,4962322,4624290,300321,3784290,607305,9647240,5245395,6476926,1751567,8992512,9283554,8347861,4309646,8460864,4715564,5121768,824063,8436949,9334543,8281850,3624398,656212,8052162,5052010,9451711,1455639,1668992,9044262,8009179,9044711,1759872,1395517,4373160,8818671,6124695,6089260,6432979,6446526,1335983,1336052,6814034,5928574,4343872,3999465,6919830,2665630,2346296,8181784,6975412,3195570,7294481,6521207,8820432,2663577,6586332,9841122,8171761,1979032,7645303,9018827,4547591,7890953,3212119,6791016,6479924,3729190,3348347,171163,1652007,222167,892303,8365833,4640564,6124550,1458019,4747480,6628443,4195458,2730046,3797723,6435500,1462196,2568410,1966039,9943428,962497,2199197,6791677,9563138,2340746,3078961,680999,4046275,1741101,5715913,1136076,4183631,713754,3816820,7947752,1212154,6544404,1209857,9513642,1576277,5805201,7102991,922334,3558092,3842103,9461780,214644,5745359,5630931,1432703,5422687,1519873,5521394,8720968,9294013,4797395,7273698,9374296,8212638,8769822,5208532,8014247,8278107,8133114,2350276,7250428,8132595,3160224,9250967,9397545,5411241,7661016,5230918,8466905,5961821,7090183,1130717,4312210,2264414,4751344,2236314,5258263,1922138,7151140,4157954,9081139,7132008,8344766,2756820,3837505,5102267,2896738,5650233,390455,5228799,2699510,7682518,6751244,5442646,2531083,671279,2172290,2557958,4720568,5077645,8382011,7174258,6615497,5153580,9970438,8697272,86433,3491801,7230852,6229884,5737904,8555769,2586010,2563792,2121715,560821,1775917,2664722,9067781,4924501,6544261,6516341,7273241,4307982,3569674,4118403,6535925,2229348,2962937,581129,1085194,9762358,3743536,5744402,9262707,5540730,7348522,1950425,4546021,3119513,365555,2705763,2450563,5366362,6078940,9325318,3235459,7353936,2462311,8251130,1010983,6251719,9884913,2840311,49209,931696,5021893,2965354,5331954,3918669,166775,9800518,7775220,1976900,1301366,5409590,5525530,1202098,880266,1945392,9262791,5378179,2663601,8822573,4253750,1743380,2358444,6214169,6528188,1032003,2405751,7389602,1379786,5637075,3637327,9515098,2525727,5267312,3980831,5840552,7201148,5322993,2414600,1781195,3233081,1806412,4873293,23343,1240281,6139437,2123445,5953692,4595633,8301537,5419502,9169727,5227619,1565752,1561558,2992112,1724185,7910844,7026788,7717940,6327197,6609806,6655037,3384474,7167017,6961454,3731023,8261975,75895,7466370,3989761,5546740,5427944,6218728,7394614,1298933,54974,4160790,5939316,5843091,8005873,6035311,1224026,9051093,5965238,7430696,547622,5085155,930290,1417104,8063325,2286270,1020854,5362084,3249921,9065398,7523541,7322833,5130039,2207633,917579,8627112,6977948,9884392,3633479,9766524,1606369,8130587,2648979,6717368,3410400,3878367,3463247,4755126,6800381,1533468,1645968,7456349,3004787,99793,977640,1161788,5829756,921471,7715284,4936006,3649092,6585273,8986513,837950,5949990,1157645,4362500,7741783,4132230,1026012,3536652,5005854,2271760,4481307,5369209,2236087,1569700,8697569,8340426,5552936,4427173,5084719,7900346,8209600,1058732,2379314,8310057,3173291,2704602,9812422,5553174,9855377,4682173,5429727,1589828,9318531,7405092,2715801,883658,3742309,4906748,2352652,707819,9944539,7789101,1685842,1163427,4366221,4811529,9948427,7476687,8111244,6246863,9106085,7014175,4152706,8598129,8313413,7184619,2831816,3599498,4594589,2532464,3623634,9591607,636433,4305205,936646,2274888,4390532,8035450,6102575,1039292,4375710,5560718,3723044,8219959,8305254,1370167,7063208,8081430,3515260,7162360,2245411,8563720,1163488,2530546,8439549,9376949,5388663,5845287,3131850,938366,6912814,7659180,2261355,2295718,1174472,74464,1752822,3854115,6171522,6480102,1684069,9440746,4148073,2317126,2996031,9465614,9020881,148543,5479599,5591991,904563,7197874,4015090,1608683,8264269,7297233,3834828,9004448,3590936,7831079,3790658,1285817,5126493,4722351,6540347,1565686,3696910,8329174,9329168,4490554,6742108,5912692,5870084,6591445,6420811,2427874,5218431,8272245,3048173,5018577,3800256,1300548,7826525,2925918,6246099,8316684,3393068,3357685,423189,5309536,7418487,6955983,7947231,2019653,7043664,8505565,2880889,2597041,8503690,7803626,3319807,3123393,7881927,124660,9432222,3350343,1288786,958581,4376846,2670575,1864167,5566952,2386532,1997167,1566945,496772,7451775,4984231,1345465,7700055,8977386,9625116,4131949,8789067,3970941,370908,7311067,7959884,3666809,4257660,612737,5024230,6815394,405746,9394819,2514773,5403856,9477780,9368716,5343841,3402691,5476262,8831585,3220601,4635852,5524468,4506976,6505878,7820064,8907949,994571,4286909,6318135,6594090,7258580,930159,840723,2826588,5186113,8504692,6980708,9006692,7862297,8329991,8526199,7225964,3061250,8604112,8612168,7975850,8010452,2420291,50907,9217211,5956919,5507488,5956767,7666073,7478447,7747182,4310926,4361760,8977151,40555,8812780,6568212,3025972,8364300,8727665,7680000,906681,2132458,4688321,4014736,6182423,7442046,7117995,6760473,8453982,3848172,9706038,8516064,3351372,7420108,910398,2136542,7615560,8869964,6032207,3932860,2359211,5614769,9227017,758796,5537338,9399614,6626815,2917718,965339,130961,883418,8812683,701472,6114930,771036,5071871,1092601,7958227,2484257,7332012,2968793,6862910,1322210,2410644,9217338,7033904,2490996,502328,2580502,984412,4816769,6057278,5652427,5197066,3047000,4326846,6521905,2337685,3324233,2675634,437255,7439400,2945429,6483363,6722892,8656102,494518,2517137,1587336,9117582,4068408,3729132,1748155,7159029,2862490,928733,5728243,6427113,964942,811468,2225473,2620370,1825395,7820786,6674270,8329565,6190410,3049674,6449007,6923343,1886545,6132658,4707624,6746968,9809392,4365835,4363461,3370626,8516373,7205655,6115913,2507704,7524224,8388255,5585440,8514426,7511825,5760957,869944,5493706,6386640,8241212,6705379,3433574,7602381,7376625,1791895,2281435,1113893,5967583,6757948,5618557,6315586,9005791,39461,3145376,6617225,9216295,668643,927955,7214888,6470018,4762445,1211112,6430934,1940913,8268478,7349601,2396781,6279862,3624677,7840562,8064703,4741752,6638048,1826164,3984725,8201196,8046723,7587987,6691132,1203399,2706912,5769641,471237,1594838,7130289,7983661,7085389,6335460,6351932,1656791,2097137,8096731,4707586,2541021,8923340,3553575,7406967,8520920,5584774,2022327,7424441,6894260,6018788,8106430,2537225,3048520,1628428,8384386,9563089,2819125,7996855,9557116,3756187,9709633,8596777,3116697,2852839,7650045,2561974,5881098,6527729,2357684,3753434,708500,3433355,7406578,4190152,7697524,7005495,6828280,9199183,9195505,7227471,8310166,8077151,7349796,40914,2270774,1506109,4937087,9665368,9537893,3621776,2553321,4289359,8176516,8938835,8414786,3058240,5541999,666431,7787386,6222417,206998,9055056,5265470,675598,7223098,4217375,6165746,6503524,1803281,2147931,3101432,1770787,4025166,6829614,5813165,7751924,729519,4562341,7587775,2660427,9330357,2643656,9026566,4196307,8113740,5971200,7682142,8580540,2697273,5503256,2463310,9232322,6387458,6225568,2365154,7393305,9683639,4225484,7574913,1228927,1943790,3195549,5082216,7080236,9784231,535428,7068079,7478602,7667471,1123533,7673908,6598488,8129570,4637915,6234610,8166176,3894683,6327670,7841305,6093924,1166631,7339094,4888268,7061655,8482597,7918452,2377506,62892,2508065,8943429,7022199,6709865,1001569,3792276,8972309,3404463,1707124,9380548,6766213,7480398,31912,2110377,7243481,9462835,1600326,1018207,6034040,3397007,1328678,376355,4765818,1664980,470540,9992723,2556126,9500250,8132897,5177767,3028063,770353,1299895,7922421,6274859,2070002,3628699,9831448,9330723,4657864,1293006,8076599,7863585,4552383,643478,1298930,2364219,8620839,3727567,82886,4522433,6315272,1401865,2554054,2219876,7235889,567079,6442365,4793240,2554986,7744326,5930158,7441483,4451277,8551223,20218,3189813,3596117,8853273,8873717,6396367,7997221,5306289,7555116,3206198,704843,8216493,1453972,1610803,5183207,5903757,1711566,2755033,1804189,5195928,5475860,7489507,6427634,6485473,3583754,7146280,686480,3286728,6885713,1680895,4870515,6846166,3797076,5954574,5485122,9692239,9502556,4463118,822285,512141,6404480,6296109,203056,3818602,277884,3406614,5870882,5448791,1879273,8875684,2617061,7068717,4485151,5783010,9335627,3929840,2246303,5732729,4775493,5312970,944969,9252186,9563375,75400,1629089,9603676,1050730,2513774,878654,5154378,8565310,1647909,6147161,818302,3003407,6866022,4835546,6882047,2985256,3199526,4914018,2318456,1510501,4966912,8413965,9683138,5051697,6232917,5230598,1352676,6496931,933857,2668648,295772,6973140,3790615,6141718,8984757,5115427,8434853,2997351,8493768,4628434,8074806,1102101,4771448,1872082,1602395,4695951,2906692,7831471,3938813,2047467,3480081,8252119,680723,7005388,6657372,3747862,2963611,4828835,7707704,4215033,1162214,4779692,2190267,6824008,8358737,3670957,3661786,8761180,7087031,2340456,9698308,9958036,5539361,4782062,7384717,1410960,2355217,9779748,4769059,1550628,6086266,6583448,7172343,7102322,8482683,6584731,9616316,7837752,5809554,1773208,406556,6396004,6428986,5908135,9163045,6267932,2458712,5710487,9198928,2674219,4177385,8370698,5299244,9078010,9463645,2308893,4098503,1127101,6096234,3590483,1322689,3733392,9086578,4605848,4888384,505076,7873709,9082424,3309756,8530957,6847320,8529182,3064494,4797522,8134846,5805943,1783540,9138,2876229,6463941,1399914,6848518,4817276,8577619,1643721,9392911,623993,4544587,2691348,8810688,2442284,3095596,3306444,1110880,757812,9691904,6767908,145405,9600226,5764962,9044800,7114579,4934771,7174529,8575088,8454992,6959539,9012554,7081532,2572994,6628898,4694795,6906029,1040591,8559094,9142910,981674,8835338,5586681,9885421,2461074,7529384,6661552,2771298,2925913,9114763,4109204,2458203,3169223,4330262,6930017,2254282,1487947,9770343,2132113,5966392,9685674,4145089,3332371,4805582,421082,5608679,7042043,2052527,7105209,1290052,3550467,9178723,7440495,2076838,105598,5958462,6443159,7856715,2047353,4571652,2804672,9032207,9824198,9265201,8005634,469678,7449260,4324356,3807283,8224934,1066774,429857,5343469,2580967,4619427,1834917,3055817,8176623,3842109,5779829,8179574,7683620,8113421,5145186,3154724,4506424,6884483,1063066,6674312,7934510,6522199,1964478,8565032,3901631,7810783,1347193,1760291,7080386,7894724,3318118,3583408,4951164,2094238,8192367,9716890,2599876,8526794,2187152,3861219,3159342,4095248,2689813,7372525,3118820,9493212,325087,4752967,7944072,5153626,5584423,5896933,8619738,1668072,4892401,1403368,9831293,1211877,4295837,7740117,7084251,9759191,7759198,9717718,9439122,6831867,9452145,8985954,7009003,7844929,6878649,186075,5533628,2042259,1306232,8120164,9817459,4858269,8083217,1446925,5931969,7760970,5887457,4258546,8984290,1062356,7157309,4478213,8815569,8346056,9864535,8458014,7307185,5066470,1985123,1787605,3718852,4110447,673038,8017975,1129821,3546222,2736531,7013994,4767906,3295603,3287953,6443442,7774404,9413881,3285444,9721569,7327188,4200404,2098661,7074009,7033573,5776251,1300692,1161424,7647453,762686,7390706,9162443,2052411,953083,1073077,5852452,4958199,3194070,8257699,3126855,8365351,5654582,965203,9790867,3109177,98108,4662210,7933549,2439171,1823167,7159313,1212752,139800,4551694,7965262,3637503,9518165,3784371,5425808,635616,1504314,8568112,208934,249757,6109983,1284490,4735558,9886527,139237,1622817,382273,7005823,4718939,8646407,3971504,2173989,466563,1696089,2298134,9388161,1494500,7298097,9070536,8113787,2426501,1686221,277099,628970,6970281,5707603,9044481,66741,1460320,2387686,7943470,4952844,9464557,7604090,3901105,6419781,9660946,5607270,4652917,8312241,6409548,5577959,2298682,9767725,677205,2489132,1313546,9300992,4511526,7094812,8130901,5324348,2800568,4529658,5494545,8944726,1355271,618923,9633304,1223364,5639838,9446961,3707661,5527895,5618670,6254370,6607112,5263343,4487574,8459520,824320,5921937,4732419,9228770,1156198,3135560,9959343,6410581,7410631,3997447,5137491,7395932,1559505,6590787,9462171,3341596,8535818,3564754,6855576,8215020,8528372,3871188,5000922,1964086,470638,3268589,2612935,2350008,2127864,3326139,1484491,4448525,6592915,8163106,9538486,5389397,8621108,9370997,3606335,3138186,4897835,9140172,1570576,7876017,8415717,164057,8331009,4479830,4386475,4643917,3876520,3966789,953222,4625207,7299482,1958242,1758863,5808384,6302414,7899824,5874032,1812404,6661206,3783389,2032047,1949908,4604050,8061557,4400210,4238232,3394073,9526076,4261956,9273897,6528781,8527623,5783329,6706630,7267431,3083541,7194839,4405367,9245841,889504,7217829,6344109,3408303,7547648,9571259,3865329,4215735,6440645,1764398,6822898,7174241,3795005,7935530,2471407,4917584,9570238,1851284,5309262,3769134,1877132,2201194,4643241,6454067,8096211,5209093,2434144,7322633,8854344,845472,166836,4946901,8911673,3199176,7860173,9670657,4083076,9659081,2580684,7709103,104266,2389302,4508763,7093495,3643887,1067529,2272586,9172793,1921968,3240523,3211830,3413562,9000210,2060152,4958342,830641,3932843,1723241,4119774,6327719,5490337,8169268,4343800,2554895,5201652,9367562,4117017,5544621,1647734,6716637,1766333,7945711,2023357,5660227,3871041,15876,505133,4988561,6313428,6740843,3272060,7944495,6310988,143150,1442597,7916143,9134503,8112412,3194570,2563051,4916912,9914098,1307991,4625264,9438684,2944828,7537939,7689161,6480592,4399533,9418555,3779023,3542315,9680067,3402859,3194287,7830486,6525945,130309,1210905,4945675,2515912,3089754,6456963,6309348,2943942,3869826,1373055,2438408,4269735,69448,424745,9085100,2452651,1221066,8992882,2093247,6858147,9808652,45705,5613494,4409161,9547745,1402548,2857175,9196161,2011248,1904042,2391739,6531596,3820916,5447826,958799,3121138,8222883,9376647,405621,4369401,7178087,9976472,8472363,6815662,7995198,4478729,680549,3316238,8000040,2903881,2591081,512407,5143362,3551208,3169483,6125092,6832477,9290044,4307365,772867,1312343,7003162,8932673,7074078,3715941,2984594,5519187,1672562,6897191,4858767,4018554,8541992,5111281,7511422,5700446,151242,8217673,8208249,508002,9001086,7758573,7114277,4575163,6614245,3657793,5570263,6183122,9581778,2379790,4513955,9952923,7879809,9919387,6848808,1539262,8092108,8888674,928143,4860568,3249325,7435874,2145836,1822481,7007381,281312,3989144,3767096,6344995,203623,8059778,9645759,1707882,5127001,2244081,3952605,8643557,9095175,1552547,5102796,9081900,4864659,7990436,8938761,8604666,5632814,4906781,5164705,8921356,3703925,6850000,183892,9971107,352708,1293998,6274092,4290932,5513766,8710866,4483084,2148963,9475240,1852287,1680570,352752,9712030,5725287,745265,4134736,7024285,6303097,4485370,5882294,2523069,2626680,696340,7156741,7189890,8354869,4496225,9317108,7379081,6266394,4587292,3233760,9741847,656146,8403368,5549331,6897668,7946853,5904244,8431074,9887069,8341893,934471,4222125,9247761,1944384,1581436,7698507,2133527,3801876,6296354,7867702,9422969,7397704,2833141,8187838,6660644,5598326,7763740,1371545,4577070,1466964,6066480,6010651,6382843,993819,117617,6782951,4133751,5025270,3110856,3769078,1463189,3118741,4943973,6732677,317178,608356,7153360,7681506,5809615,3827602,2703141,9649350,5643753,4382319,5378000,4810420,894734,6752470,2577788,9748127,1027823,5978850,6525600,6420149,736776,7348065,5816566,4399777,8495422,966453,4403993,5758744,8001217,8695540,7255043,2042290,921667,8212056,7567669,8661102,6145700,1586289,1213162,3357441,2944387,2089352,741644,1713693,4203971,3702939,1493255,8337362,7701025,7635808,2560302,7674943,2820697,6661339,4170495,5113330,4386662,3974949,1879494,1054171,219557,3614200,5415680,6753724,9719099,7391363,9939636,7369344,3981709,7161694,4666885,5445792,9453385,6152933,1733927,2657114,331653,5649728,6730137,2266007,277968,7381321,2190644,1551748,2858483,9760885,9867035,2271198,1617107,6881868,3880276,336220,3551858,7302323,3312557,8958132,7215102,417379,2632134,864644,8272751,3333428,1804088,2015884,9818731,9022745,1354062,1146807,7634976,2964207,472715,586740,2785352,4911207,6789850,1207059,9326183,2945202,1407409,3351962,6402796,2840081,8895536,2453891,8444151,6332718,7104278,9244500,8943787,6982588,6789476,3394540,3619061,5614777,1936964,399691,4521095,3666746,8511755,9759143,8820568,7561554,795703,6323393,7916982,9142288,5089052,1405254,17197,104261,3170617,6446899,6437180,1193615,8008175,7650797,8132788,7995152,8965818,972367,7211279,7166814,910846,555698,8830409,9250745,398813,7234174,9914834,824588,9531178,1023419,6673228,8646420,1330540,8899973,4397092,1424368,4629844,8883563,4399070,1613496,9374876,7020295,9493759,8405908,586890,9561662,3861574,13331,2193745,5993957,1087018,9296346,2341574,7226892,8817978,5625841,8398438,4188534,4460190,5492053,8768266,1548203,6861666,5099046,6784108,4291592,5100572,5446517,23056,5035539,4036026,7967925,5614614,1166189,9388783,8192937,5489990,2938893,9669772,9300960,3606192,7514394,3447501,8620875,296446,3234982,9604879,373588,4630682,3090508,6492731,6810417,2554953,7637526,9105790,1481388,7667985,9449643,9246824,9658101,8175569,6779021,177634,8861346,7061803,316444,5827467,5002396,4295092,9882513,9764152,9930917,4617478,8510515,9999993,4998712,7640060,7511416,3977095,5567448,1790746,7899431,1111549,2935442,8006647,5725939,1385746,32629,246608,7439482,3540673,7028638,8372402,6706840,2428266,6634496,3847510,4523862,5120429,7578691,7903774,2882201,4704483,1394607,5451668,1544921,1758131,616902,5063359,1818712,976829,3307235,4488148,6525202,2313992,2610564,3263995,8237974,7727351,4369344,3357250,3866055,6681357,5164578,4652019,4599152,7749110,8536746,1907210,3278998,5152320,4714448,269109,8032371,4484722,2636962,704060,1620037,8477500,1031560,1568661,2217356,4700106,999378,7465353,5078542,5731193,404241,63806,7629999,8459150,7056920,1286699,1005861,9529455,9951441,8478097,1153449,3771258,3810803,4502885,7033567,4567099,1250831,3175384,5116459,5408634,7999358,2715969,4855266,2398578,4097293,8016730,9026737,9815395,6271859,736481,7423768,3604381,9544756,6462034,4624109,1245492,963266,6994113,2613922,2423501,2888963,5977990,166137,3397329,1423797,6130762,2996528,1525992,3220274,1493027,9647127,1257548,8224809,1769256,5380508,273282,4661928,5675549,3533805,2680488,241858,488573,9809170,4425087,3257836,1116040,6213189,1884583,3435237,2591480,8824578,3829522,2670406,5089422,1215453,9567595,5122356,4995741,9604211,4673495,8162612,6482197,2856486,8145113,2184462,2679179,6142138,4487140,3583455,9511697,8620039,9513332,3852345,3067884,4883391,7260060,7585849,1851648,2908085,9395508,1563404,4493413,3000281,6037459,4793281,8285722,6351081,9792574,6171444,3094813,8786866,6604221,1061968,326752,4796935,7159238,8262894,3871731,4059342,83276,5747739,4753087,3923407,430996,8930361,6569286,247667,220490,5031464,8017928,7543187,86566,8738444,4460175,4084742,8244794,4081541,392406,3371752,4923408,3131313,3160053,7633509,691942,3295011,1593381,6633235,9430202,2706971,3058654,2218758,192036,2107820,3970088,5812493,5670007,7984650,8490110,3633893,3276495,2706767,1897111,1779269,5868686,442511,1034688,871359,7985354,6567254,3614508,6400841,230140,3302013,1531175,3443383,3069454,961631,5066164,2167897,1811808,1960286,7719388,2520954,1433162,7446404,1673573,9936625,2506740,4929074,9645703,3098938,3672425,1993432,9466619,3781440,5313245,5710680,6082738,284209,9876964,7942915,3591407,4922629,5097831,7698596,885111,4810832,1584042,6172529,5458975,4706470,948967,5442884,7731187,2793707,641961,5543654,2293810,9639759,905303,7678785,6112686,7423885,5498875,5159698,2652969,6576616,9449739,4840207,4672671,8658050,6560134,991179,7767473,7316839,1770062,2738566,1669738,2546744,1802838,9308342,5406589,3178034,6705050,2434314,5664141,2588750,6465638,2681478,8687975,8244344,7736263,2205895,425644,2501846,6869351,3799650,7142955,9519133,6928462,1485887,2713008,4141743,3662723,894957,111302,1310927,12948,6709019,3211641,8560601,3244931,9517630,8771790,96807,6400873,3663529,3739752,5908306,7692735,9274320,937455,9867130,766426,4820582,648419,4643218,9837570,2080063,3189542,371799,1567901,6701125,3335491,5304228,4619498,755710,9726567,2467897,6016558,1388664,1252118,7726332,621717,666623,7883373,2772308,3267212,3795425,4284891,8067298,2640707,698961,925117,7087786,8992258,6597751,7666095,6627121,9337821,9691899,1725065,4381370,811079,2131879,4228220,1300634,3487246,4246298,6554028,398010,127764,765209,8848985,4332549,3089050,3770873,1815092,482065,5467873,2922352,6957505,4042178,4197211,2622984,8777172,6909968,4235838,6088504,1553318,9303175,9096729,3826147,500076,1916131,3293116,1166116,3734564,6345591,2257845,5354844,2000023,3756904,8709443,9196526,2042689,4227727,8691882,2035329,6706054,2193401,7036603,4007482,9277985,5139920,1975223,5456809,9368307,2084999,8007381,1478906,2339650,1323199,5903940,4850885,715555,9998140,9677672,2964879,7791447,985978,5991511,3863217,4712258,8680698,8596947,7389236,7608518,7902909,5009838,1833509,1621293,9066853,8583448,3787315,8231570,5185660,5241769,6933298,1282437,8409133,7248380,1985153,3278788,570773,5595376,8693921,6460783,8727558,3147266,2172590,1765480,3342648,8338040,1393452,4728416,3964266,4533482,148592,4241559,3832940,7808729,1356447,9019888,9024627,5815974,7978688,4037845,7917741,6095414,7767308,655097,3318279,8606337,6877170,5550659,2315696,2647252,7232332,5281766,4547598,9025486,2910907,9235160,7257886,8075880,7930529,8232282,639207,3365609,5275445,5221857,3491673,8775016,5197136,683950,4781650,1604049,2548274,4916309,1269508,2899438,6912446,5828518,1404738,9596028,226016,6166364,8985452,6133206,8329691,2805646,7219075,5418288,8639459,7846764,8864657,8303635,3033368,9928217,7202620,3066211,4681313,5278843,7636965,101774,1439579,9129749,8093570,6045020,5369070,2468936,5468021,9531608,3846736,8800133,9935569,9761120,3266981,4340468,6552892,7427535,5264109,6687110,1235571,6030349,1265876,7446415,2158483,7194164,557369,2784061,4217418,6066541,8507935,6415092,705699,9149511,7082316,3150406,3775271,2364950,6885523,7792493,4945829,8358982,9542869,1313003,9972708,5576240,6155065,1431071,6360559,7460687,7892830,6600511,8252278,5935196,3092583,7102481,4055427,5847028,7566830,903391,3409313,9967204,99184,582797,70437,5116126,4392493,227470,9286001,2173942,4538458,8023009,3682848,405355,4930682,4179761,9294088,4442545,4132886,9766218,3675448,2252130,3033843,8096226,8316948,9461823,5044353,3666794,8879857,9732033,5606187,8143420,6946539,1087842,3912561,7682103,6398463,5102146,9522366,2080778,1484501,9294621,1529272,7830950,48691,8968091,1273681,2051363,389528,2536734,1392472,1348234,2501645,5106725,1244575,2335040,7438253,9437912,6755470,725375,6377672,1913970,1465542,4492362,4021311,4200918,3741085,9054169,8144334,3587853,8124842,1549040,9104210,3013173,5883091,9616516,3126426,5356124,481632,1938775,7090325,4431335,317794,258181,1043475,3547486,3064389,8717654,8696869,4381594,56723,5682088,2161360,5822196,7508308,492429,9156561,2572277,1961862,2489538,1937756,5103970,4249952,9356419,6468745,1782544,8657935,955395,517712,4497582,8376325,6580838,5694258,1254769,5952484,9453227,8600737,1233452,7138956,964551,3175123,9166208,6795945,7578820,1211499,1042045,7651695,2728061,7756903,8961746,7910246,1984789,6014784,6835523,896588,9827511,1169626,9852930,2624317,9187518,5633431,6843384,1871838,828534,5174342,3434207,5860448,650250,5502072,6940485,7008353,7899780,3804106,9562824,3366463,5895545,7797325,5021822,5725873,3182390,3824616,5491534,2706955,3731383,6737831,9647179,3648823,749976,3245164,6257693,6013124,5989960,952154,3900569,929292,7794806,7763855,5996458,3353384,180452,9907177,5751163,2016858,8285980,6112873,7349789,5378883,4176672,1518523,2163967,2934224,8123275,8881495,1853186,504240,2196182,7279788,9972559,3511643,4907859,9054404,750985,1901592,7886313,981195,8608046,405110,5296143,7591300,1984811,6184470,2342462,1142579,8788077,9733739,2205822,417180,7159113,2735573,551559,9967056,7775674,4283640,8443812,9197459,6889414,8619833,5900592,5995729,6404683,5552485,2135336,5056891,829397,8231305,1573740,4623155,9207817,8671950,8900509,96676,3808589,3290691,4884121,875914,4114899,8769429,7054081,942994,2749729,5290245,5739382,1815293,7305491,5737591,7411001,2176408,879736,1281339,4067363,4995841,4131727,4509102,1557008,1086313,9760229,9236514,5207476,7231465,9389927,4041902,6228220,9665539,7544464,9697495,2832401,3467235,7916467,1547204,6727644,6336867,4288374,5582053,7609119,9975174,9387750,9521915,2565750,2756942,7991290,6743649,6916315,7379903,5610219,5965096,1393198,4149768,3479284,9583850,1396531,8135998,3934170,7225873,8704721,4139143,7049960,4243120,6531975,9039911,3771723,9170412,3439704,2366589,2124832,4279676,3307989,1810947,2647062,6522414,7523320,3232376,7175600,3537551,9203838,527788,6233359,4330375,6787513,9755597,8756646,1457163,860543,6694546,6163330,3664680,5500033,6209132,282415,3362225,45520,6471403,6125301,8772932,8130946,6304058,6458774,2890372,4210704,5529141,9108973,6698068,5005523,1131051,5148476,4566213,9794581,600285,3918824,2078744,2102531,353290,817859,7719135,7689528,6394985,6052061,5303810,2698542,9630468,4361931,147767,7264316,2641704,7372084,9592247,8120651,1862568,9260941,4946061,1002161,4990619,4671244,160348,9966711,7055319,9111992,851813,9281886,4839356,3285126,2840893,9921096,3874968,3348234,3130862,6077011,1053662,4778857,3791770,7079838,9016024,8111277,1171709,2716714,2040969,3870504,7648425,5451118,9513568,7711023,2773733,7620433,2850893,715294,669983,950995,5890910,5673172,8673637,9095598,6379787,5483957,8086004,9402359,8526757,89767,1480369,2967546,3685958,3099720,7435166,4745997,2986715,2311660,8208886,6011888,8689404,2571455,7897478,5038381,1580330,1501506,5629887,6028858,1154608,3082421,7593076,1975092,6875497,6165749,2005304,6639441,8118885,4250489,6088565,2034759,3273337,2372115,1409637,5455256,6153069,2028034,4500633,9072103,3635939,8257221,1526182,2297569,7484951,9931241,3745645,7441367,2594092,3123462,8605486,7013025,7827117,152974,5648839,3841781,6142381,9416924,9226199,6626892,1745698,1975929,1990609,4021008,8456991,1082366,9419213,1155723,2912515,79090,7215822,3589263,5809378,1126671,7014220,8575781,7900986,4586952,3688627,6238648,4429422,2298887,4482604,5217708,6304509,6020908,1400192,8949680,7900836,7743985,5153532,9244287,9967379,7629271,488874,6277411,5214013,598858,7168533,4467280,6561273,4298027,301176,3426846,8160816,3640557,6903159,3081719,9058233,9947828,1718425,5486838,1023728,425672,2455777,3174463,1889619,2023805,3739955,9917170,3852724,5448302,9007288,2873494,1243268,9616070,1002148,1759300,9380950,5634522,4222418,5334652,9301433,7324983,8306452,5248115,7289446,8215782,6093125,3769457,5413304,895377,3895714,9738334,8318531,2081619,364015,2765808,734519,3792484,5528421,4803842,3446792,4392100,3190900,3797277,4524937,4197911,3489925,5076062,1286097,9952003,1072173,9335320,9638223,6889474,6957712,6160378,2457418,5424209,9680017,6507617,998427,6454525,2999325,6807086,1077593,2369438,26205,8076708,8971304,766470,5353162,4499221,3131565,2016999,4540907,1043171,8252176,8003254,2580062,8157687,5541862,5681786,8339477,8844329,1066336,6133540,2121544,4166375,5719199,5021853,3860897,3561372,8214275,9110004,7567758,6980670,183168,9948796,7880161,8692790,6069919,1903615,6160158,8778799,4802344,8938410,6734271,6544767,7645863,1639296,4509121,2337362,5622851,2535448,2593395,3456568,1663337,9457053,3286874,7767086,7021758,946966,5124745,6396791,7329029,1269660,4342852,362152,8334095,3429575,2617111,3267901,4532438,8629659,3630366,624079,4091884,9398771,1349701,2653919,3387774,3446569,3727396,944391,4944329,9898182,7842642,4210497,3460525,9572907,8166372,4516976,3841202,1496421,3226601,8464638,1134582,5509134,6076605,8366532,338789,340922,1338486,4877672,3004609,2191597,3458044,4557446,1806695,7138923,7049524,4325589,9736307,9525381,7818280,7423774,4082878,3097306,2447253,1510272,8171955,3179828,7983647,7301469,1161249,2261878,7212363,3572177,2226191,4876789,4859969,5073186,3457914,7446112,7816368,1032333,809559,8834101,8146736,1052839,1843716,2600429,5623892,1552441,5207879,2373818,225992,4792836,745575,6141750,3834776,5132006,4466590,7055968,2833137,3383306,5066153,1620701,4549446,4387825,9298790,5575408,8678996,4875938,4772461,8621114,1457221,1273464,1922292,3490994,5561008,4585873,7389387,6840623,9329890,7577214,2743974,9536136,6026246,3047333,7301701,270514,4148096,9306579,2603475,9474992,1044624,6872241,9657574,5035872,4299231,2671577,7403406,1690931,5168534,1437879,7605623,8920205,2067046,955763,1173503,6797300,9247637,6063640,1549942,830080,4710754,4590638,6392780,373264,3368429,1507458,944830,1989923,2342096,6183372,1170949,6496725,5547670,5389952,177752,3458917,6267570,2784035,3656061,6848302,8245166,5809652,2655088,3467931,5225541,6451477,2124773,8323784,5857268,3625343,6125716,829729,2490853,1667825,1602668,4455087,9324864,4724870,7913480,9119172,1295345,2865385,8461416,3613771,5725896,5963384,3218641,6052936,633225,4310523,372104,5024115,2372469,3594538,1727497,5335788,5645021,1463657,6649155,9825145,6523527,4225760,9569457,6255458,4952432,7668618,5211952,698753,4474438,6174542,2518924,6262415,1685171,3069767,8690005,7111266,5681879,8767369,7721383,4046418,9242765,1746464,4063408,5175154,1918089,1172829,669632,388778,317961,6773987,485162,9930165,364580,6775262,4515133,1033186,6496766,9799191,2907686,9938346,9266604,9059656,4984807,1958460,9156908,3581330,4562209,4513150,8342819,8369789,6429847,2747372,8612118,900828,5447994,6572713,6493287,3525347,7810154,5718819,6863372,9334247,4259869,5329268,9545590,2781426,6189100,7274794,8748627,5981192,5394906,4225018,7573897,225380,2302920,9847602,1436460,6297901,9197987,6579462,713051,7782755,7280505,2203875,8159915,8129770,2550570,8021955,7197171,6849504,5145848,3536609,9583602,8508081,7830138,3672278,916495,6040159,1058424,7518814,1002640,4490869,9005726,5619322,2012644,8861819,8616455,78421,4756459,5526187,845768,9693695,1815193,6803903,3047899,4307348,6032959,8099374,2615231,9080088,2519653,6130478,4984368,5786722,1857897,4272112,3852565,5375952,4155944,197929,5033273,9066613,4360677,8775538,9176524,463273,2188098,9054743,1381246,8970888,6843134,778913,583478,1075663,3073406,1705785,6428929,1208296,1978123,6575607,9266899,4691182,8959204,1058808,2090924,6805771,5124038,3800745,9971053,7531151,8345562,4217358,6970871,4771751,5997427,942001,6964254,2911464,8440324,5571686,4469397,7806538,7261923,4964769,2379052,8993560,7296924,6341304,6385217,6933559,2446906,5834401,7743087,4527288,7569410,5877077,1286131,684675,9912231,9771678,6968055,1611409,6022069,4037997,199724,7778258,7733340,5788467,4795968,4909366,7427940,7937790,146577,5817257,8082287,3268413,966975,3522322,2278950,7143245,1828180,245385,7999658,9876051,8995912,4574515,2281889,7860567,7382346,7176591,76782,8726616,8521294,6118489,6694996,9648960,4233565,5226143,4523808,4081502,5973641,9406891,8845127,6672407,6955088,1481911,446850,9690096,1068859,810305,733523,4239370,4456873,6792392,5176585,8001966,8610448,6540466,8604017,7592233,4955566,1653396,9370880,494930,7440876,7122223,2896158,4745505,3814525,499164,6324428,5618473,1531650,6013619,4325310,3108323,6638614,7629085,3495021,309584,1522681,1426859,4538531,1484157,5277197,7450265,8206534,1694976,2177119,9132097,6041176,9408657,8109858,1505117,941487,4091622,6754902,5408622,928224,3981661,3169630,2627795,57351,9892149,2556458,8134722,8853301,977701,897700,7396036,2675273,8423649,4597743,6031283,8862198,9169362,970948,103182,2531970,4801797,5245913,3830268,1781622,7026402,6310712,1915509,8913855,264891,7902896,3259682,6419372,8921528,3926386,8325511,3279109,7502667,9038552,5693424,2536079,2892846,3814123,9813414,6922076,4983272,5224256,5589230,2592429,4260568,2134622,1015607,5393990,5078809,8787468,3751585,8080358,9265888,870624,5620446,2810568,3015631,3470857,962147,3459337,9391503,1175627,9768561,2047721,7724195,2679523,4791257,9054383,6445322,4653079,2214158,3678013,1685233,1875695,2166428,7686757,6162092,9889098,4935547,7118514,8728398,6429363,4608815,5173358,943189,6474017,3919706,5340446,4817824,8483346,1943687,1460646,9730882,532072,7396827,6298381,1784566,9689178,8872859,269378,8152562,5804079,6483384,6781869,116849,861940,9160362,6705188,2443439,4048810,2708856,219234,744966,2479825,7725202,683347,588056,7924591,3943391,5467801,3188498,5620235,8075261,8484563,8358766,9673374,1157228,8315513,2732104,3464904,4694050,4893281,7776293,6953657,7736804,2175332,411038,3598199,5674937,4952795,3806302,2074909,8626824,3072583,9568788,171637,5150213,3826494,8709905,8641493,4937996,1808297,1268705,2089064,514538,2337676,6372072,4048755,1834362,4013665,5636225,3698698,3130902,769449,6006987,9042561,1469105,9244470,432368,7003108,5521181,7450831,3996758,3426057,2498401,8640056,7424643,8198666,1681255,4040978,8899408,4145278,2800064,9477207,6882134,4579793,431967,7154699,9512129,2223138,9494374,5576160,5612644,3663447,4968393,946074,2424328,4929390,2854620,9186592,1956994,1716208,4568043,3902339,5668190,6799161,7564970,6760707,9472719,5196254,7991601,4801331,5386589,4215705,4507156,3521824,3866218,7765616,3456488,4065848,3278547,2521816,6480972,6570895,7812288,3294179,8920605,6538747,9913174,2235189,6280908,6253991,6246060,7259516,1678374,4704442,1575790,399647,6501592,8827675,4677366,8678348,1904707,7690197,284055,4836540'

PRINT '========== Sreenivas Chedde''s Method =========='
SET STATISTICS TIME ON
EXEC Util_ReadIdList @IdList=@s
SET STATISTICS TIME OFF

PRINT '========== Tally Table Method =========='
SET STATISTICS TIME ON
INSERT INTO #Id(N)
SELECT ElementValue = SUBSTRING(','+@s,t.N+1,CHARINDEX(',',@s+',',t.N)-t.N)
FROM dbo.Tally t
WHERE N <= LEN(+@s)+1
AND SUBSTRING(','+@s,t.N,1) = ','
SET STATISTICS TIME OFF

PRINT '========== Method from Article =========='
SET STATISTICS TIME ON
INSERT INTO #ID(N)
SELECT Item FROM strToTable(@S,',')
OPTION (MAXRECURSION 0)
SET STATISTICS TIME OFF

PLEASE SCROLL DOWN TO SEE THE RESULTS FROM strToTable

SQL Server parse and compile time:
CPU time = 47 ms, elapsed time = 111 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.
========== Sreenivas Chedde's Method ==========

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 5 ms.

SQL Server Execution Times:
CPU time = 47 ms, elapsed time = 229 ms.

SQL Server Execution Times:
CPU time = 188 ms, elapsed time = 548 ms.

SQL Server Execution Times:
CPU time = 1046 ms, elapsed time = 1132 ms.

SQL Server Execution Times:
CPU time = 1281 ms, elapsed time = 1916 ms.
========== Tally Table Method ==========

SQL Server Execution Times:
CPU time = 641 ms, elapsed time = 633 ms.

(10000 row(s) affected)
========== Method from Article ==========

SQL Server Execution Times:
CPU time = 13813 ms, elapsed time = 47080 ms.

(10000 row(s) affected)




--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #836087
Posted Friday, December 25, 2009 6:35 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Friday, January 15, 2010 7:41 AM
Points: 1, Visits: 18
MAXRECURSION cannot be used on UDFs. This is limited by the default MAXRECURSION value of 100 as it was mentioned above.
The WHILE methods are not the best performers either, using a table of numbers is. Find some examples here: http://stackoverflow.com/questions/753582/implementing-and-applying-a-string-split-in-t-sql
Post #839176
Posted Friday, December 25, 2009 9:08 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 1:03 AM
Points: 36,975, Visits: 31,492
Ulises Telcontar (12/25/2009)
MAXRECURSION cannot be used on UDFs.


I beg to differ...
 CREATE FUNCTION dbo.MaxRecursionTest ()
RETURNS INT
AS
BEGIN
DECLARE @Return INT
SELECT TOP 1 @Return = 1 FROM Sys.Objects OPTION (MAXRECURSION 0)
RETURN @Return
END

The WHILE methods are not the best performers either, using a table of numbers is. Find
some examples here: http://stackoverflow.com/questions/753582/implementing-and-
applying-a-string-split-in-t-sql


There are normally two problems with links like that one... First, they never explain how a
Numbers table works. Second, they use a bloody While loop to build it... not a real
confidence builder that the author really knows anything about set based programming.

Here's about the only article I've ever seen that explains not only how to build one and
what it can be used for, it also explains how it actually works to replace certain forms of
loops. This particular author (I know him fairly well ) also shows how to build one
using a While loop but only to show how slow a While loop is and why it should be
avoided even for one-off code. Here's the link...

http://www.sqlservercentral.com/articles/T-SQL/62867/


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #839186
Posted Friday, December 25, 2009 9:23 PM


SSC-Insane

SSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-Insane

Group: General Forum Members
Last Login: Today @ 6:43 AM
Points: 23,270, Visits: 31,986
Ulises Telcontar (12/25/2009)
MAXRECURSION cannot be used on UDFs. This is limited by the default MAXRECURSION value of 100 as it was mentioned above.
The WHILE methods are not the best performers either, using a table of numbers is. Find some examples here: http://stackoverflow.com/questions/753582/implementing-and-applying-a-string-split-in-t-sql


If you take the time to review the entire thread, you'd see that RECURSION was already knocked for being slow as were WHILE loop methods. A Tally table version was posted as an alternative.

In addition to that an extensive forum thread here on SSC was also cited as well, and deserves mention again, Performance issue with tally solution.

And a search of SSC will show that this topic has been mentioned several times and several good examples of code have been shown in those threads as well.



Lynn Pettis

For better assistance in answering your questions, click here
For tips to get better help with Performance Problems, click here
For Running Totals and its variations, click here or when working with partitioned tables
For more about Tally Tables, click here
For more about Cross Tabs and Pivots, click here and here
Managing Transaction Logs

SQL Musings from the Desert Fountain Valley SQL (My Mirror Blog)
Post #839190
« Prev Topic | Next Topic »

Add to briefcase «««45678»»

Permissions Expand / Collapse