n=943;
time=[1462719, 2319019, 4485756, 5731858, 6957595, 8375780, 8524146, 11309332, 11340170, 11527472, 12222787, 15419539, 16953680, 17449213, 17834172, 17904137, 20246956, 21287586, 21324108, 21794409, 23686823, 29735044, 29926796, 30089378, 30999398, 31558240, 31686055, 32897575, 33848040, 34285213, 35311640, 36236807, 36977098, 38258084, 41115536, 41134218, 41303493, 42367010, 42596933, 44261704, 44660756, 48298011, 48871433, 49983397, 52121355, 52979496, 53857950, 54104435, 55376599, 55900616, 58031920, 58867771, 60842908, 61432541, 61823240, 62003836, 62720393, 62995967, 63183275, 63460104, 63716432, 64203869, 64228199, 67277270, 68213910, 68743915, 68968936, 69229648, 70189832, 71479791, 73582909, 73643295, 73714366, 74697012, 74933872, 75319655, 76138945, 77703307, 79704202, 83041409, 86133966, 86147838, 86398826, 86545712, 87724582, 89002386, 89601315, 90804979, 91727295, 91956987, 94053784, 94586668, 95800702, 96068883, 96240008, 96349854, 97171065, 98438838, 99180926, 99754074, 104610487, 108075225, 108297398, 110098575, 110518831, 111243592, 113230029, 113649986, 114076173, 115190646, 115221776, 117315374, 118386764, 118411121, 119270128, 120192343, 121003413, 121243695, 121408840, 123277745, 123800277, 124724167, 125315454, 125424430, 127717956, 130243950, 130448417, 130675759, 131179585, 132709032, 133941381, 134443477, 134721445, 135317844, 136497998, 137081482, 140052071, 140525882, 142496899, 142748700, 142864067, 143533726, 143920489, 144325350, 147019256, 147369123, 147703319, 148142028, 150177843, 150357856, 150421928, 150485934, 150615547, 150850460, 150857121, 152442759, 153547334, 154891991, 155024124, 155285604, 158242420, 158294561, 158771872, 160463878, 160859938, 161333662, 162918162, 163603880, 164782952, 168529555, 168553589, 168763475, 169250211, 173590707, 174057362, 174092485, 174458718, 176391985, 176690770, 177696948, 178774144, 180717648, 182646243, 183796314, 185546343, 188625288, 190255307, 191077407, 192963518, 193581711, 194096231, 197583485, 197853587, 198194188, 199040647, 200049992, 200808302, 201304613, 202421478, 203135752, 208077549, 210965156, 212751125, 213629201, 213631405, 216978738, 217113501, 217370483, 218790051, 220348738, 220617394, 220693217, 221910020, 222425846, 222676124, 223219569, 223355643, 223417069, 223605075, 224789184, 225961959, 231410682, 231823372, 232634380, 236105541, 238390321, 239091700, 240325683, 240838997, 241188630, 241385581, 244006607, 245567950, 245685246, 247103930, 249946130, 250511601, 251486850, 251721950, 252544299, 255171652, 255928449, 259155994, 259368650, 260686738, 260744956, 262385145, 265171273, 266109827, 266611409, 267678580, 267943807, 270712978, 274175148, 275526840, 276670588, 276855586, 278725216, 280757618, 281413162, 282169090, 283048432, 283556129, 285072359, 285265762, 285824378, 287709098, 288821124, 289364256, 290035116, 291758345, 292271008, 292415993, 292721158, 293506373, 294162687, 296127198, 296944603, 298589286, 298984741, 300176855, 300518581, 300578168, 300787096, 301289830, 301584017, 301591621, 301595125, 303157048, 303177410, 303345625, 305975641, 309724701, 310136891, 311849471, 312034068, 312055827, 313346057, 315688031, 315952231, 317539009, 317635648, 319842428, 320382116, 320664512, 320780283, 321954087, 322792130, 325687103, 326323103, 327340552, 329074701, 330585157, 332614053, 332810518, 333824654, 334574830, 334935307, 336059736, 337315020, 339271649, 342782062, 343006124, 343133945, 343716684, 346288357, 346626008, 348973020, 350477566, 351683734, 355468434, 357641717, 357776003, 358102348, 360013721, 361937942, 361956180, 362541399, 363140002, 364002195, 364743865, 364896975, 366532228, 367536658, 369130936, 369354361, 369388332, 369832572, 370650061, 371580668, 372827706, 373407566, 375290045, 377112403, 378098087, 379553565, 379901303, 380183325, 380231196, 381057947, 382373651, 382975917, 384983983, 386064414, 386356235, 387043714, 387176649, 388260123, 388814595, 388831438, 389264272, 389714125, 390867340, 390961998, 392026028, 394272862, 395573655, 396240309, 396751797, 397836396, 398686737, 398751081, 398862452, 401137647, 401354269, 402141127, 402514699, 403246014, 405052191, 405401595, 407569958, 408332509, 410776315, 411381556, 413169472, 414919723, 415513325, 418106492, 418342161, 418351906, 418442573, 418924221, 419395544, 420861964, 422002601, 422899070, 424426361, 424514341, 424717254, 424804564, 425133104, 425931724, 427737924, 431180841, 431916832, 432937412, 434558747, 435989410, 439301507, 441513981, 441922449, 442672144, 443061819, 443435686, 443803343, 445376568, 446763794, 447817577, 448780031, 450331379, 450535526, 450872556, 450884062, 451477602, 452370788, 453640756, 453963081, 454603583, 454945180, 455261857, 455369371, 458063279, 459092477, 459190050, 460334243, 461177372, 462153686, 464405532, 465680662, 466717379, 467838270, 469543166, 471891070, 472448842, 476383200, 478721387, 478973505, 480995147, 481265833, 481439049, 481694002, 481820550, 482828720, 486178471, 486561004, 489732815, 490299415, 490469873, 491614247, 492584213, 492600188, 492612531, 492671775, 493044760, 493418952, 493509333, 493564602, 497054910, 497814162, 497820407, 498561336, 499249231, 501080716, 502868649, 503277544, 503467285, 503929500, 508358930, 508374171, 508568334, 510191963, 514921672, 515406257, 516808499, 518455890, 519590239, 522757413, 522837486, 522916517, 523991523, 524151360, 524421313, 525259322, 525536820, 526563074, 526851259, 527371321, 531161892, 531540643, 532017448, 532393504, 533602104, 536039671, 536086220, 536845424, 538677359, 541514357, 542446715, 542916420, 544063169, 544574356, 547994060, 548616550, 548990388, 549050368, 551802246, 553719292, 556538030, 558312072, 563070727, 563871663, 563981797, 564728627, 565100980, 565591074, 565718313, 565951043, 566053831, 566418970, 566567024, 568435180, 568874326, 569515028, 571202447, 572185883, 572952014, 575312734, 577080661, 578798363, 579204164, 579643920, 581316555, 582214555, 583093375, 584254272, 585183586, 586697141, 586962123, 587097316, 587167556, 588899474, 588937359, 589733329, 593072321, 594963604, 597199653, 597498675, 598901859, 600838279, 601033171, 601687716, 602373414, 604826505, 605207250, 606737021, 607043560, 609233707, 610167726, 611100894, 612724419, 614205472, 617356934, 617511088, 618065755, 618396121, 618408082, 620153122, 620435737, 621228648, 621671796, 623105976, 624956260, 625047965, 625267058, 627209205, 628943079, 629128160, 631103894, 631877585, 633701938, 633839511, 634253436, 634734991, 635361714, 635674224, 637183972, 637879340, 640659195, 640786557, 640787185, 640790840, 642892551, 643154680, 644423074, 646268510, 646507862, 648964758, 649661662, 650398110, 651185198, 653381923, 653801685, 653867715, 654574603, 654868964, 654928957, 655095514, 656909621, 657080996, 662157873, 663738352, 663763153, 664059397, 664588498, 666131919, 666268256, 666467549, 666928588, 667304671, 667378507, 667938658, 668576054, 670031873, 671260658, 671816286, 673104756, 674690554, 675085946, 676223403, 676421704, 676824232, 677352660, 677629862, 678593702, 681108882, 681466355, 681783062, 682065385, 682556259, 682708617, 686470452, 687094361, 687774906, 687943336, 688924044, 689053263, 690046851, 693269658, 693501882, 694288272, 695914228, 696468576, 698607904, 701913928, 702248848, 702498107, 704683633, 706423408, 707234992, 707562170, 707791333, 708177207, 708226185, 710143195, 711444124, 711753237, 711869187, 713361505, 714506486, 714682396, 714716022, 714855441, 715137399, 715558037, 716482930, 716803038, 717965586, 718414424, 721112282, 722744261, 728093659, 729127548, 732070277, 733107239, 733269179, 733469047, 733833147, 734389953, 735661637, 737045607, 737340134, 739841899, 742005385, 742121174, 743089758, 744249555, 744900648, 745475268, 746191899, 746566694, 746590641, 747528275, 749114164, 749394642, 750528162, 753161817, 754601833, 755488668, 756880859, 757063259, 757115702, 757453510, 759783652, 760673323, 762260395, 762723235, 762923908, 765679532, 768900146, 769710364, 770926632, 771194723, 771558922, 771726640, 771822675, 772279354, 773585206, 774154384, 774782734, 774983155, 775045115, 775673401, 776229950, 778708007, 779633060, 779903426, 783095987, 784233484, 785259524, 786424110, 786909795, 787579148, 788310846, 788394257, 788458994, 789658045, 790584878, 790793761, 791321827, 791715040, 792073099, 793355153, 793383997, 793587858, 793590434, 794923619, 797171353, 797927010, 797946211, 798188161, 798475561, 799001154, 800448049, 800954626, 802060245, 803334909, 805975282, 806328876, 808225281, 809748077, 810294366, 811939603, 814722996, 816786016, 817614591, 819343997, 823478100, 825248027, 830424081, 833017459, 833062709, 836579443, 837161251, 840475726, 843695842, 844730144, 844764499, 846469658, 847774697, 848153394, 849337113, 850791143, 850961603, 851668461, 852282101, 852837329, 855111546, 855310729, 855429213, 855670111, 855778899, 855812328, 858128837, 860787739, 861539929, 862879011, 863654965, 867292032, 868279379, 868397285, 869340231, 869554859, 869996336, 870391956, 872796623, 873302608, 873554598, 873972287, 874217692, 874341373, 874740124, 874750170, 876301476, 879055609, 881139746, 881737901, 881981108, 883230109, 885855371, 888562168, 888964233, 891748655, 891757729, 893094214, 893251691, 893878532, 895185838, 895630166, 896146944, 896228949, 896326677, 896461999, 898263562, 899293663, 900550262, 901946302, 902802279, 902829453, 903628545, 904869526, 905375806, 906931030, 908148226, 908400957, 908460928, 910480947, 910653614, 912519961, 913571631, 915693573, 917943588, 919595576, 921407251, 922094453, 922415555, 924826834, 926950984, 928690943, 932423972, 933367076, 934578394, 935713083, 936592176, 939715031, 942035625, 943599125, 943796109, 945101598, 946279821, 947389624, 948932029, 953590060, 955711438, 956206525, 958808985, 960597587, 961546539, 971164447, 971485466, 971693528, 973460861, 973826891, 973926632, 974148973, 976255270, 976727727, 977967510, 977977549, 978975318, 979080989, 979448836, 980803356, 981514790, 981873553, 987153075, 987353468, 988895807, 989435716, 989472367, 989788427, 990082581, 990961255, 992355138, 992478965, 992957313, 994208567, 994230245, 995351680, 995625178, 997126531, 998501946, 998930052, 999307715];
passenger=[4, 1, 2, 4, 3, 2, 6, 5, 3, 6, 4, 3, 2, 2, 3, 1, 3, 3, 2, 2, 1, 4, 2, 3, 2, 3, 2, 5, 3, 5, 3, 3, 3, 1, 2, 8, 2, 3, 2, 1, 2, 2, 3, 1, 4, 5, 3, 3, 3, 1, 1, 1, 5, 3, 2, 3, 2, 1, 2, 7, 2, 2, 3, 4, 7, 2, 3, 6, 2, 1, 5, 2, 2, 2, 1, 3, 5, 4, 2, 3, 1, 1, 2, 4, 2, 3, 1, 4, 4, 4, 3, 1, 4, 3, 3, 3, 3, 1, 4, 4, 3, 2, 5, 3, 5, 1, 6, 5, 4, 3, 4, 6, 1, 2, 4, 2, 4, 8, 2, 1, 5, 5, 3, 2, 1, 2, 1, 3, 4, 1, 4, 2, 7, 6, 1, 1, 4, 2, 2, 2, 4, 4, 7, 3, 3, 3, 5, 2, 4, 3, 2, 5, 2, 4, 4, 6, 6, 3, 3, 3, 7, 4, 2, 6, 4, 4, 4, 5, 3, 1, 5, 4, 3, 4, 2, 4, 3, 2, 2, 4, 4, 5, 4, 3, 3, 2, 8, 6, 5, 2, 3, 3, 2, 2, 3, 5, 4, 3, 3, 1, 3, 1, 9, 1, 3, 2, 2, 4, 3, 4, 6, 5, 3, 2, 1, 2, 3, 3, 3, 4, 3, 2, 3, 2, 4, 3, 2, 4, 2, 4, 1, 5, 5, 4, 4, 5, 7, 4, 5, 4, 1, 5, 2, 3, 3, 6, 4, 6, 4, 2, 3, 5, 3, 3, 1, 3, 1, 5, 3, 4, 8, 2, 9, 3, 2, 4, 4, 2, 4, 1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 3, 3, 1, 2, 4, 3, 3, 1, 3, 6, 1, 4, 4, 4, 3, 2, 6, 3, 6, 3, 2, 1, 2, 3, 4, 1, 2, 4, 3, 1, 1, 3, 3, 5, 3, 4, 4, 2, 4, 2, 5, 2, 4, 2, 6, 1, 2, 2, 2, 2, 5, 1, 2, 4, 5, 2, 4, 4, 4, 1, 1, 5, 1, 2, 5, 1, 4, 1, 4, 4, 2, 6, 4, 1, 3, 2, 7, 4, 3, 5, 1, 3, 5, 2, 4, 2, 2, 2, 4, 4, 2, 3, 4, 2, 1, 2, 2, 5, 3, 6, 4, 1, 4, 3, 2, 2, 1, 4, 4, 5, 2, 3, 3, 1, 2, 3, 5, 3, 1, 4, 5, 3, 1, 2, 7, 3, 1, 6, 1, 5, 4, 2, 2, 2, 1, 1, 2, 2, 3, 7, 3, 2, 4, 3, 2, 4, 2, 2, 1, 6, 5, 3, 4, 1, 1, 3, 1, 5, 4, 4, 3, 5, 3, 4, 3, 3, 1, 4, 1, 6, 2, 2, 3, 4, 4, 4, 4, 3, 2, 3, 2, 1, 1, 4, 6, 6, 3, 4, 3, 1, 3, 2, 2, 3, 2, 2, 1, 4, 4, 8, 3, 2, 2, 2, 8, 2, 4, 2, 2, 1, 3, 4, 3, 4, 6, 5, 5, 5, 1, 5, 3, 5, 2, 2, 6, 2, 1, 4, 2, 2, 2, 4, 4, 1, 3, 4, 1, 3, 4, 5, 1, 1, 1, 2, 6, 2, 3, 2, 1, 1, 3, 3, 5, 4, 1, 2, 4, 3, 6, 3, 6, 2, 3, 6, 4, 1, 4, 1, 1, 4, 3, 2, 4, 4, 2, 2, 3, 2, 2, 1, 8, 2, 6, 3, 5, 3, 1, 4, 3, 1, 1, 3, 2, 6, 3, 6, 3, 4, 6, 3, 1, 6, 6, 5, 6, 1, 1, 4, 2, 4, 2, 4, 5, 2, 5, 3, 2, 3, 2, 4, 7, 3, 4, 1, 6, 3, 2, 1, 2, 3, 3, 1, 2, 3, 2, 3, 2, 3, 3, 7, 3, 3, 6, 3, 5, 3, 2, 1, 1, 2, 3, 5, 3, 2, 3, 1, 5, 4, 11, 4, 8, 4, 6, 6, 5, 3, 1, 1, 2, 2, 2, 6, 4, 4, 6, 2, 1, 2, 3, 1, 3, 4, 4, 2, 3, 1, 4, 1, 3, 6, 4, 2, 4, 4, 3, 3, 4, 3, 1, 2, 3, 1, 3, 3, 4, 2, 2, 3, 6, 5, 2, 5, 4, 5, 4, 3, 4, 5, 9, 5, 2, 3, 3, 4, 3, 2, 1, 3, 3, 7, 2, 1, 1, 7, 5, 3, 1, 2, 3, 5, 3, 5, 2, 4, 5, 1, 1, 3, 3, 6, 1, 1, 1, 4, 5, 3, 5, 4, 4, 2, 5, 2, 1, 5, 2, 3, 2, 3, 5, 5, 4, 6, 3, 4, 1, 2, 4, 2, 2, 4, 2, 2, 4, 1, 7, 1, 2, 3, 3, 1, 1, 8, 1, 3, 3, 2, 3, 1, 2, 2, 3, 3, 2, 4, 4, 1, 4, 2, 2, 5, 2, 3, 4, 1, 4, 3, 3, 1, 2, 3, 5, 4, 4, 3, 3, 3, 4, 4, 4, 6, 1, 9, 6, 4, 2, 3, 2, 3, 4, 2, 2, 5, 4, 3, 4, 2, 2, 2, 1, 1, 3, 2, 4, 2, 4, 2, 2, 2, 6, 1, 3, 2, 3, 5, 7, 3, 5, 2, 4, 1, 2, 5, 3, 4, 3, 3, 4, 4, 3, 9, 1, 2, 1, 1, 2, 5, 1, 1, 4, 3, 4, 4, 4, 2, 5, 2, 3, 1, 2, 3, 2, 2, 2, 4, 2, 2, 5, 3, 5, 5, 5, 2, 4, 5, 4, 3, 2, 1, 4, 5, 2, 3, 3, 6, 4, 5, 4, 8, 1, 3, 7, 2, 2, 5, 4, 2, 4, 6, 5, 2, 6, 4, 2, 3, 4, 2, 2, 3, 2, 2, 3, 4, 2, 1, 5, 2, 5, 3, 1, 1, 3, 3, 3, 5];
country=[{45,750,799,268},{558},{34,993},{178,853,22,767},{63,94,432},{865,657},{620,889,903,444,890,313},{168,294,450,683,893},{309,384,233},{474,89,210,533,929,227},{259,80,41,218},{249,486,988},{872,582},{564,794},{529,419,625},{382},{789,873,261},{14,309,511},{820,353},{701,122},{486},{175,276,246,502},{667,483},{869,711,358},{528,294},{960,357,747},{520,419},{770,137,932,949,263},{805,423,960},{653,315,899,434,447},{377,87,979},{26,302,857},{107,523,362},{841},{556,254},{975,694,4,680,735,105,824,280},{811,969},{565,382,827},{254,367},{509},{349,811},{203,689},{194,966,960},{369},{833,31,995,642},{62,266,992,122,49},{516,107,533},{820,925,406},{497,356,198},{175},{295},{811},{14,526,194,301,566},{732,619,449},{805,957},{598,343,730},{663,94},{265},{469,995},{56,566,267,439,995,416,461},{734,604},{295,443},{143,572,666},{862,546,731,202},{153,493,432,659,393,546,165},{561,13},{225,111,485},{714,966,794,480,412,360},{100,33},{264},{942,748,821,708,619},{785,981},{172,156},{696,648},{766},{3,723,621},{780,539,18,539,47},{157,255,664,834},{354,98},{274,163,523},{761},{552},{312,245},{791,394,138,753},{403,208},{774,994,514},{760},{893,552,813,841},{819,343,17,638},{704,744,276,747},{464,333,775},{493},{107,740,775,359},{711,520,805},{946,668,52},{697,632,221},{597,704,218},{886},{775,820,126,909},{839,516,249,215},{219,155,354},{292,953},{579,711,148,896,483},{843,705,315},{574,682,938,289,404},{946},{785,851,696,552,357,280},{344,521,96,69,444},{751,156,397,386},{781,755,284},{811,760,856,586},{516,662,412,3,838,280},{546},{531,189},{546,838,278,726},{894,800},{621,523,56,478},{640,523,935,993,805,127,765,624},{148,285},{45},{788,918,846,659,16},{354,695,208,727,92},{309,465,990},{988,454},{549},{986,579},{770},{798,54,198},{417,558,514,992},{439},{945,582,464,517},{511,935},{946,596,57,960,511,862,834},{62,657,673,345,708,438},{234},{288},{695,186,737,758},{159,868},{520,528},{21,811},{914,799,122,76},{194,51,632,149},{452,621,625,611,157,481,186},{338,910,470},{653,385,26},{848,267,418},{763,891,640,932,320},{409,190},{815,724,797,537},{732,662,328},{302,191},{259,341,276,761,104},{722,161},{349,270,805,620},{273,792,307,784},{475,207,794,620,815,131},{815,143,640,532,919,234},{432,195,65},{483,266,14},{327,37,140},{229,723,757,838,386,715,309},{567,682,354,261},{789,723},{653,590,710,7,224,545},{897,224,992,841},{793,256,653,660},{113,896,33,648},{467,558,417,855,546},{910,713,938},{257},{904,219,26,496,491},{251,705,172,219},{882,486,955},{529,610,454,953},{56,523},{380,942,578,842},{408,45,66},{662,324},{61,827},{471,318,274,322},{344,413,834,200},{517,147,516,981,439},{372,249,369,277},{168,372,302},{122,621,910},{839,186},{878,715,100,376,834,991,358,611},{353,508,376,780,620,720},{425,815,269,860,372},{970,202},{647,468,605},{353,386,331},{353,423},{737,520},{919,322,514},{815,189,931,172,201},{944,704,214,219},{835,578,732},{909,993,224},{632},{144,591,47},{285},{84,549,766,572,248,736,432,369,835},{373},{28,899,928},{13,800},{311,748},{760,708,338,445},{953,318,876},{367,662,588,280},{857,556,538,899,653,249},{28,846,682,338,4},{497,224,489},{711,746},{26},{757,489},{391,395,486},{789,102,953},{717,234,896},{896,670,76,720},{51,984,598},{412,791},{242,275,152},{535,846},{566,439,520,66},{630,49,788},{606,1000},{811,161,208,80},{368,129},{497,932,968,233},{280},{468,163,218,464,165},{149,611,851,607,625},{687,373,578,233},{234,766,993,517},{136,174,583,191,942},{815,992,78,552,318,846,157},{13,464,486,793},{992,560,3,265,621},{267,757,688,878},{909},{601,297,950,359,63},{723,569},{3,880,659},{202,909,919},{240,31,152,598,778,254},{486,3,821,14},{299,490,207,135,611,775},{824,659,773,384},{78,377},{6,219,917},{655,639,226,646,988},{164,611,805},{468,1,551},{4},{824,872,358},{417},{740,847,744,767,96},{361,931,48},{528,468,163,202},{272,520,173,766,904,71,354,280},{194,539},{540,841,760,540,156,372,151,358,190},{944,511,63},{915,492},{552,4,985,305},{368,477,768,53},{202,343},{444,280,31,884},{597},{815,359},{367,163,595,203},{956,253,959},{915,514,190,31,156},{856},{877},{406,682},{224,307},{15,522,379,594},{241,480,989},{727,962,25},{86},{832,206},{21,246,415,489},{56,208,295},{871,128,816},{673},{193,349,65},{789,688,512,367,368,782},{69},{820,941,827,56},{775,190,155,723},{80,2,49,556},{274,546,789},{468,190},{858,723,625,621,603,434},{349,485,439},{301,938,225,113,465,327},{541,564,808},{218,200},{475},{713,902},{313,361,418},{827,880,235,974},{966},{733,315},{259,687,20,33},{813,788,942},{573},{554},{757,653,328},{820,324,732},{347,766,917,224,984},{72,74,30},{191,623,388,791},{789,371,289,998},{126,394},{218,977,789,665},{640,226},{135,549,63,945,72},{374,18},{811,891,690,568},{122,664},{707,704,531,417,277,827},{946},{147,820},{246,696},{255,662},{566,763},{917,797,709,31,872},{51},{386,662},{63,710,491,693},{577,983,391,235,824},{841,434},{839,309,63,686},{758,312,51,143},{953,847,989,13},{511},{56},{464,884,898,179,694},{657},{854,281},{531,14,494,140,301},{682},{940,347,140,585},{994},{767,904,414,659},{601,294,552,960},{620,909},{224,157,962,254,44,33},{711,204,32,811},{76},{529,903,149},{525,720},{489,735,846,235,3,558,546},{388,492,732,642},{176,607,243},{359,131,617,4,268},{133},{38,546,463},{299,761,329,791,983},{839,944},{679,985,749,412},{259,143},{254,321},{440,122},{695,772,832,704},{761,313,558,726},{369,574},{702,214,368},{462,363,95,156},{314,176},{483},{702,195},{949,261},{295,65,356,841,203},{813,248,774},{715,249,582,234,914,768},{229,983,138,861},{299},{520,288,541,628},{381,597,689},{103,420},{756,161},{382},{95,368,369,775},{541,819,664,620},{620,190,296,235,324},{252,511},{202,792,1},{489,702,58},{263},{625,933},{316,827,556},{847,480,540,497,696},{439,495,51},{900},{520,948,628,803},{478,264,438,708,467},{393,341,957},{393},{735,639},{219,298,256,671,308,775,218},{432,919,301},{780},{420,228,767,938,138,479},{789},{147,126,201,432,634},{84,648,813,767},{829,209},{734,329},{249,465},{523},{977},{131,690},{486,471},{992,691,259},{886,447,975,29,946,684,131},{838,434,94},{331,800},{131,889,813,324},{316,157,349},{355,379},{317,261,511,376},{583,424},{827,890},{470},{734,816,894,80,617,87},{363,757,24,550,999},{111,938,662},{219,900,494,560},{873},{989},{393,418,621},{597},{805,362,163,102,820},{991,301,139,227},{203,235,4,549},{798,805,481},{341,843,540,715,236},{315,480,415},{56,769,430,358},{361,322,256},{524,28,569},{312},{648,657,977,22},{521},{390,354,122,793,851,175},{493,540},{349,520},{331,301,159},{948,950,447,522},{979,165,846,546},{952,615,277,520},{176,611,937,341},{620,903,42},{472,87},{808,910,301},{372,49},{938},{282},{91,367,827,662},{81,98,163,311,716,756},{596,297,919,601,637,724},{816,896,513},{772,423,82,567},{622,304,332},{219},{994,189,618},{62,313},{912,696},{434,259,143},{604,129},{689,100},{711},{341,170,118,569},{554,469,86,141},{245,317,663,662,47,76,294,74},{436,208,166},{30,819},{770,449},{671,302},{664,810,628,857,789,653,221,122},{682,439},{225,751,507,221},{362,386},{420,486},{138},{856,714,409},{661,712,157,198},{548,642,833},{389,539,73,71},{732,161,946,354,33,434},{432,827,720,381,280},{628,69,637,14,966},{980,979,813,69,884},{502},{783,338,702,653,70},{680,308,854},{281,668,157,418,782},{632,147},{142,111},{944,558,65,11,69,611},{50,912},{477},{259,892,678,509},{669,180},{143,511},{962,847},{621,474,425,904},{979,433,707,992},{294},{30,33,441},{345,72,270,432},{143},{389,513,513},{227,421,952,613},{758,279,738,892,253},{314},{420},{301},{807,354},{138,511,834,731,321,613},{598,805},{463,615,195},{343,632},{883},{977},{784,773,598},{904,277,761},{642,573,483,711,870},{221,805,839,572},{403},{48,322},{195,486,695,605},{866,812,198},{665,190,274,317,720,469},{772,756,224},{912,186,368,78,558,628},{198,899},{791,123,352},{952,601,592,344,532,359},{158,190,266,682},{259},{823,338,6,329},{791},{835},{801,20,270,222},{51,453,369},{891,538},{473,536,294,20},{324,485,551,662},{547,580},{883,490},{789,105,198},{240,659},{155,202},{625},{216,711,830,408,707,303,718,506},{321,126},{319,80,33,235,91,315},{627,135,246},{978,546,804,909,808},{163,969,324},{234},{295,974,789,827},{901,595,608},{894},{362},{748,970,213},{390,485},{547,558,835,636,723,657},{909,723,497},{469,56,573,625,974,598},{114,780,621},{855,28,159,295},{295,481,938,693,367,53},{219,508,971},{950},{776,82,977,813,852,710},{165,720,138,843,573,10},{535,779,517,746,302},{222,340,540,704,729,619},{240},{589},{31,409,756,266},{943,921},{147,415,312,689},{396,156},{835,929,601,880},{53,29,32,838,324},{465,284},{673,79,820,296,756},{981,280,822},{776,43},{977,78,592},{846,152},{246,780,708,542},{799,704,235,58,324,122,702},{464,858,876},{458,916,12,218},{197},{194,312,235,310,242,195},{929,358,994},{33,917},{704},{726,813},{657,175,248},{578,312,896},{834},{653,798},{734,709,995},{558,231},{987,157,646},{357,445},{808,367,673},{194,221,797},{324,727,326,49,869,966,721},{857,892,202},{511,21,345},{578,707,288,689,752,481},{66,1000,598},{846,820,161,806,135},{324,3,480},{523,224},{480},{723},{158,382},{362,498,997},{277,14,866,713,104},{668,349,252},{221,334},{467,233,789},{979},{588,268,995,532,240},{846,824,51,488},{443,163,15,123,720,312,936,575,143,497,784},{729,546,833,791},{316,48,682,695,161,156,240,561},{152,521,330,459},{122,302,520,416,254,77},{135,381,880,611,141,657},{111,944,467,735,876},{198,195,441},{702},{628},{904,767},{925,846},{513,382},{793,432,529,611,579,285},{494,559,938,131},{69,292,766,16},{640,551,408,149,844,757},{981,295},{839},{313,221},{673,376,486},{989},{757,12,208},{377,793,611,884},{632,984,834,72},{692,494},{478,229,168},{859},{868,381,853,857},{61},{718,750,4},{197,148,578,444,345,168},{614,835,487,368},{22,805},{309,578,147,82},{486,410,328,605},{218,107,659},{160,340,953},{368,312,919,714},{13,516,692},{423},{348,640},{810,835,497},{344},{528,255,638},{343,934,516},{643,761,73,539},{946,403},{95,47},{720,513,115},{289,333,720,767,808,315},{475,204,630,25,62},{391,805},{977,872,423,895,541},{29,138,167,947},{147,132,640,659,382},{415,161,497,979},{952,266,62},{14,753,62,758},{210,95,805,445,899},{403,766,195,892,888,377,80,951,621},{625,158,909,13,480},{267,384},{996,141,668},{846,528,915},{267,76,977,746},{12,95,981},{998,489},{270},{977,611,928},{777,793,981},{44,176,66,494,66,259,441},{944,202},{732},{421},{309,16,185,507,991,774,380},{261,367,566,838,314},{511,611,903},{993},{566,857},{226,994,500},{328,267,995,203,900},{58,905,186},{573,857,751,625,176},{291,15},{715,640,673,447},{690,400,971,757,551},{21},{921},{632,295,33},{929,851,51},{694,761,56,322,359,485},{193},{789},{626},{501,190,445,994},{587,198,689,797,129},{598,153,946},{107,767,718,322,21},{789,799,815,221},{402,672,664,653},{158,215},{438,367,203,894,412},{423,527},{144},{579,834,775,843,45},{834,544},{61,412,527},{7,455},{785,126,4},{884,483,263,932,386},{597,210,489,551,317},{522,369,441,357},{494,76,483,856,756,669},{95,944,481},{775,988,628,349},{543},{475,530},{359,380,3,688},{663,889},{382,315},{309,66,533,225},{608,917},{952,315},{715,520,418,302},{644},{846,691,72,533,157,908,773},{292},{367,582},{767,122,690},{540,141,980},{186},{533},{979,65,884,791,447,966,465,417},{953},{673,381,266},{407,932,752},{324,438},{344,311,702},{195},{987,633},{767,932},{285,465,960},{494,156,189},{948,238},{21,662,468,700},{917,552,354,916},{195},{793,995,259,621},{863,163},{673,910},{545,816,981,619,522},{707,681},{872,412,107},{678,234,540,138},{42},{738,820,441,159},{211,587,816},{676,715,657},{117},{517,131},{48,549,190},{733,267,784,358,208},{583,297,43,579},{156,318,879,808},{364,955,511},{77,274,276},{333,578,511},{241,851,994,229},{730,66,812,247},{899,126,10,970},{907,307,210,778,539,125},{344},{468,259,341,958,280,775,49,603,621},{645,405,735,66,601,671},{439,511,514,111},{267,651},{249,358,947},{190,76},{682,507,625},{72,186,984,149},{176,789},{811,553},{135,56,896,131,348},{811,131,531,981},{159,573,80},{797,927,122,643},{987,658},{197,409},{562,57},{8},{851},{82,970,333},{653,557},{65,802,439,295},{838,378},{784,712,328,105},{896,525},{749,192},{14,473},{80,767,49,442,236,905},{770},{741,723,47},{151,315},{929,368,72},{274,155,393,63,911},{126,500,811,841,734,557,909},{412,648,802},{981,566,16,789,572},{818,305},{465,612,141,98},{61},{312,600},{582,309,516,110,861},{157,194,945},{952,465,54,529},{945,480,486},{56,976,804},{933,344,799,465},{485,797,421,889},{14,770,45},{605,478,433,874,380,737,539,215,808},{170},{386,789},{82},{944},{302,163},{18,33,159,11,266},{529},{485},{250,691,910,408},{439,467,109},{132,117,651,683},{748,924,467,400},{27,381,748,416},{295,485},{468,311,188,679,970},{539,52},{63,968,870},{978},{839,270},{63,994,676},{920,44},{727,577},{315,471},{907,4,481,747},{995,343},{310,399},{63,850,851,189,423},{31,962,816},{127,219,909,249,141},{199,454,879,851,619},{202,125,527,933,256},{811,305},{800,137,80,539},{412,910,671,688,892},{757,566,519,441},{95,439,513},{198,238},{688},{702,593,196,811},{122,540,592,107,340},{625,44},{511,191,126},{673,610,600},{942,31,380,519,306,12},{792,889,190,946},{194,904,281,26,378},{971,567,675,790},{51,756,884,169,62,540,161,711},{546},{713,737,713},{209,822,538,797,789,183,380},{533,89},{737,817},{857,966,21,916,892},{560,529,784,341},{56,834},{373,155,773,539},{301,518,208,218,393,168},{922,766,161,481,946},{892,671},{980,988,439,8,992,678},{854,13,507,867},{280,902},{218,315,597},{336,896,661,628},{229,593},{304,233},{987,479,766},{886,915},{266,467},{925,557,352},{76,256,63,702},{727,163},{76},{6,713,224,354,285},{219,738},{813,703,552,410,912},{214,368,306},{287},{319},{103,26,1000},{739,638,909},{240,161,230},{135,235,53,523,82}]