n=946;
time=[1822906, 2497173, 2630211, 5238763, 7454877, 9085393, 10235738, 10560918, 11814409, 12325800, 13109376, 13319943, 14045743, 15049953, 15164519, 16162881, 17120637, 19428967, 20654271, 20837475, 22901484, 23419596, 24284486, 26131210, 26413794, 26817490, 26859974, 33077074, 33218678, 33243410, 33754610, 34153132, 34415864, 34641955, 35950212, 36317172, 36372493, 38208113, 38378245, 39653723, 40400667, 40701634, 40981114, 42290559, 43195910, 45714834, 47774817, 49392991, 52599079, 53121991, 53309873, 53704474, 54296998, 55372851, 56071532, 56323955, 59544518, 60993152, 61210030, 61940144, 62380605, 62714902, 62729317, 64613829, 66037401, 66069757, 66727217, 68638732, 69015675, 69350265, 73848223, 75549345, 76153091, 77974484, 80185924, 80200344, 80410601, 81910140, 82096912, 83971632, 85921943, 86038742, 86667868, 87692134, 88561150, 89576167, 90224481, 92824400, 93413275, 93986377, 95919982, 96850105, 96989324, 98748155, 98992814, 99002982, 101999862, 102387291, 102553521, 103183819, 104066393, 106713036, 106752858, 107332813, 107994025, 110336185, 110625118, 111219606, 113234088, 114996548, 116035145, 116650598, 117139256, 118943770, 121013120, 121523127, 123887620, 125740123, 126425496, 127375326, 128184707, 130974390, 133844213, 134574898, 135264567, 135945598, 137017648, 137141974, 137858423, 138341328, 138539052, 139708626, 141083587, 142547096, 142551172, 143208076, 143282958, 143416959, 145826820, 152267939, 152561876, 152563302, 153101413, 153460900, 155363317, 158130811, 158878290, 160228429, 161756620, 161796575, 161970948, 164212817, 164480974, 165181296, 167345355, 167443329, 169506416, 170049297, 170724548, 171281993, 171560833, 172828950, 173162008, 175291940, 175363335, 176696064, 176845757, 182133305, 182594906, 183540010, 184290009, 184541276, 185044502, 187591004, 188083333, 189585036, 191705846, 193208694, 193612375, 196600922, 198343947, 198616668, 199421010, 200963622, 202271757, 202350993, 202836938, 203033142, 204167565, 204925907, 205513372, 206466531, 208534706, 208665281, 209139084, 209221607, 209941378, 210804537, 212565962, 214585765, 215532679, 215890775, 216023571, 216867009, 217143206, 217221727, 218412736, 218933688, 219044745, 221428949, 226084222, 226172753, 229604740, 230260711, 230685860, 231715025, 234026729, 234629119, 234745694, 234929269, 236803487, 237527129, 237923113, 237952976, 239031433, 242239153, 244654344, 244789718, 246407270, 246622204, 248576585, 248844320, 249176275, 249760284, 250348328, 250368828, 251525684, 254360523, 255562920, 259681263, 259891568, 260673935, 263232053, 263286233, 266196638, 268845042, 270526243, 270835298, 271708361, 271959214, 277896615, 278555872, 278558292, 278573240, 278633400, 279407235, 279827969, 280225497, 280703088, 280806807, 281374053, 285259766, 285568689, 285713589, 286164590, 286246231, 287013065, 287625749, 287965835, 287985722, 288142155, 291968829, 293330175, 295140202, 295378967, 296192361, 296927513, 299980688, 300223212, 300378485, 301621979, 302434578, 305045849, 306463290, 309406706, 309968110, 311145937, 312635916, 315104613, 315470233, 316839475, 318221374, 318986599, 319711671, 320520994, 321984934, 322250267, 322356584, 322753167, 325763239, 327321637, 327354039, 328061990, 328076438, 328627837, 330957442, 331014619, 335165031, 336104753, 336435691, 338170448, 340941678, 343224372, 344750121, 344927632, 345706822, 346670515, 350012157, 350191889, 353560030, 356213855, 357803323, 359648259, 360281586, 361102206, 362921278, 363743847, 363912530, 364086746, 364774065, 368272311, 370227999, 370543969, 372245408, 373865339, 375906667, 377763559, 378656766, 380530505, 380602587, 381697237, 381781604, 382171894, 382486385, 382700807, 383357559, 384989806, 386832406, 387748275, 389077124, 390899972, 391717512, 391821893, 394006754, 394153090, 394630927, 394646431, 395383679, 395578855, 396118043, 397593257, 398881372, 400727098, 402689408, 403211971, 403832781, 405938256, 407613110, 408307664, 409250228, 411530389, 412031293, 413787343, 414541551, 415389343, 415414622, 415626232, 415952901, 416134222, 417732772, 418579066, 419007441, 419731743, 424083514, 424270143, 426897107, 427624712, 427792920, 429205813, 430267119, 430580975, 431160100, 433619575, 433652411, 435822278, 436234320, 436459465, 437883528, 438798603, 439214831, 439941996, 440348997, 441213404, 441528822, 441535257, 441894999, 442301305, 443875840, 444486815, 444622907, 445445297, 446366594, 447520656, 448813062, 449191916, 449728763, 450036898, 450805535, 451383193, 451847515, 454747572, 455041527, 455124935, 456382480, 456418657, 456835340, 457794920, 458526399, 459517925, 460756437, 462133768, 462297424, 465968362, 466795221, 467035398, 468330443, 468334950, 469425437, 469902953, 470109082, 475442546, 477391233, 477408365, 482742559, 488251420, 488514214, 488910246, 491770476, 493943064, 494269050, 494551297, 494567829, 497924983, 498046165, 502018065, 505467165, 506747342, 507200026, 510390665, 510854094, 511965372, 512154524, 513756344, 514545211, 515308899, 515820170, 516531056, 516957478, 519107974, 519399018, 519758468, 525680552, 526624783, 527743241, 528294867, 528612400, 528853748, 529817029, 529838323, 530133833, 530339107, 531510859, 533683245, 533722508, 536924478, 537431675, 537683777, 538733942, 540619868, 540821569, 540908715, 541474089, 542286436, 542335586, 543927742, 544307986, 544525933, 545664047, 545666588, 550215390, 553443661, 559152011, 559236066, 559728561, 562506434, 564975462, 566268397, 568549114, 571479352, 572388546, 572518450, 578056922, 578360100, 580042771, 582252394, 582451153, 582989880, 583243614, 584635008, 585086290, 585526026, 585535350, 585909995, 587186185, 587252078, 588318432, 588645968, 588760354, 591588687, 591907313, 593772599, 594605455, 595800558, 596190646, 597818834, 599906295, 601316222, 601789556, 604555585, 605635898, 606636743, 607022901, 607352826, 608852150, 609458462, 611234054, 611769326, 613049009, 613512005, 613727092, 613731722, 614063372, 614302203, 615900051, 617752073, 620732122, 621411314, 622023932, 623249204, 623352914, 624333929, 624454253, 628497459, 628876039, 629070397, 629257959, 629595727, 634644394, 635780114, 636456037, 637933286, 638904835, 639093905, 640506314, 640893314, 641631352, 641885594, 642059877, 642538792, 642599390, 642640365, 642962101, 643082410, 643121342, 645435982, 645742604, 647115044, 648107070, 648943538, 649444257, 650851316, 651232316, 652296678, 653807243, 654984492, 657038452, 658614208, 658924184, 659692520, 660048765, 660486776, 660892518, 661220981, 661756695, 661804341, 661905475, 662673483, 663250566, 665067559, 665473382, 666619894, 667074240, 669182832, 670594089, 670935094, 676263583, 678091425, 678551025, 679604891, 679852263, 680166901, 680458960, 681245720, 682500389, 683033530, 684462223, 684477729, 684873112, 686290590, 689425152, 691118391, 691169759, 692662013, 694654683, 698299730, 698504558, 700032982, 700610801, 700961121, 702290905, 703446793, 703728941, 704053729, 704594438, 704812696, 706384951, 707079458, 710375325, 712313924, 712452184, 714798843, 715912266, 716303395, 716346926, 718235271, 718317567, 719475544, 719709389, 720009656, 720148196, 720354462, 721077221, 721569870, 723353621, 723582637, 725358681, 726680586, 727211354, 727502853, 728703854, 729759091, 730200623, 731642746, 736505020, 738114398, 739087032, 740202182, 741664986, 741762990, 741972833, 742199621, 742410558, 742781784, 743168002, 744181761, 744420725, 744932410, 745160559, 745831522, 747333938, 747816180, 747873853, 749126244, 749359950, 751438194, 752746787, 753976169, 755294473, 755492018, 756148138, 756498494, 757699025, 758021019, 759341548, 759669073, 759672668, 760920450, 762505945, 763706979, 763847271, 764664741, 764791951, 764948460, 766614169, 767396102, 767768560, 767888063, 768205131, 770184692, 770239261, 770409363, 771813972, 772064162, 772782304, 774003929, 774405152, 775276884, 775377777, 775881815, 777490053, 779085038, 779728903, 780727305, 781955007, 784340359, 784568768, 785686008, 785781184, 788747950, 789022458, 789115153, 790000514, 790405126, 794784837, 795028068, 798149691, 798213383, 800209666, 801834779, 803446781, 807132125, 807651494, 807888887, 808307430, 812570610, 812847817, 814622936, 815619873, 815875829, 816368774, 816602367, 818562735, 822591410, 823808178, 826813043, 827461444, 827509935, 828196541, 829015401, 830777889, 831417987, 832823308, 833164431, 833549708, 837466838, 838151756, 838788775, 839022639, 841726099, 842089592, 843198042, 845366422, 846057508, 846981882, 847006843, 847277649, 848458789, 849855606, 849932136, 850757322, 852965392, 853978460, 854965919, 856670922, 856698894, 857788084, 857812842, 858173799, 858958555, 859092109, 859434536, 860904569, 861571229, 862131145, 863389736, 864041781, 865135197, 865987557, 866431851, 866782477, 868521346, 869274390, 870262615, 870408367, 870800281, 872741276, 875832152, 876860232, 880321639, 882399708, 884154661, 885437479, 885767330, 885831329, 885989680, 887740108, 887948599, 888553230, 890139996, 890323244, 890830316, 892844450, 893905929, 895654133, 895721081, 896865695, 898132685, 898471567, 898513431, 899817794, 900932082, 902251142, 902766158, 903067822, 903225624, 905061267, 905111176, 905838481, 906026126, 906140554, 906193324, 906981272, 907834232, 908165368, 908940287, 909891292, 909966931, 910127903, 910996750, 912243148, 912435944, 912769087, 914132925, 914588237, 914631693, 914938754, 915147478, 915150435, 915706128, 916425245, 919061915, 921286766, 922542429, 922995000, 923362058, 923504181, 924942150, 925356272, 925525030, 925827876, 927055692, 927997478, 929827123, 930966409, 931090597, 931114040, 931218692, 931344898, 931630952, 931828435, 932452111, 933908306, 935256550, 936187291, 937146793, 938396041, 939521054, 939592380, 940161738, 940834127, 941963833, 942233578, 943168763, 943348138, 945580965, 948281989, 952603288, 954337666, 955601017, 956648093, 961112823, 962192153, 963586356, 964732667, 965677440, 967402039, 970353533, 972180270, 973067210, 975602723, 975871808, 977107467, 979164167, 981696167, 982882437, 983125161, 984299091, 984507661, 985242207, 985533963, 985706680, 986646850, 986800066, 987731515, 988411985, 988542711, 990213834, 992548954, 994409706, 995185435, 996794987, 997055888, 997289674, 998470068, 998508767, 998750219];
passenger=[1, 1, 1, 2, 3, 3, 5, 8, 5, 3, 3, 2, 5, 3, 1, 2, 1, 2, 1, 2, 2, 4, 5, 5, 2, 6, 2, 2, 3, 2, 5, 4, 6, 5, 7, 1, 1, 1, 4, 1, 4, 2, 1, 5, 5, 3, 5, 1, 1, 4, 3, 7, 4, 3, 3, 1, 2, 3, 2, 3, 1, 1, 5, 4, 3, 4, 6, 4, 3, 1, 1, 2, 2, 4, 3, 2, 6, 3, 3, 1, 3, 2, 2, 3, 4, 2, 8, 2, 3, 5, 6, 4, 2, 1, 3, 3, 3, 2, 2, 6, 8, 7, 4, 3, 6, 2, 2, 5, 1, 2, 2, 3, 2, 3, 1, 5, 3, 2, 2, 3, 6, 1, 3, 2, 2, 5, 5, 4, 1, 4, 4, 3, 2, 5, 2, 3, 4, 5, 4, 3, 5, 2, 1, 3, 3, 7, 2, 3, 2, 3, 3, 4, 3, 2, 1, 2, 3, 3, 2, 2, 6, 5, 4, 3, 6, 2, 4, 3, 3, 6, 3, 3, 7, 4, 3, 2, 1, 2, 5, 2, 2, 2, 7, 2, 4, 3, 2, 3, 7, 2, 3, 4, 2, 3, 5, 3, 1, 3, 2, 3, 3, 3, 5, 3, 3, 2, 5, 2, 5, 2, 3, 2, 4, 5, 1, 7, 5, 2, 3, 5, 1, 6, 4, 5, 7, 2, 4, 2, 2, 4, 4, 3, 2, 2, 1, 3, 2, 2, 2, 2, 3, 3, 3, 4, 3, 3, 4, 5, 1, 3, 6, 1, 4, 5, 3, 1, 2, 1, 4, 1, 6, 4, 4, 3, 1, 2, 3, 3, 4, 2, 5, 1, 2, 6, 1, 3, 5, 2, 4, 4, 2, 8, 3, 3, 4, 2, 1, 1, 6, 2, 3, 2, 5, 8, 4, 2, 1, 4, 6, 4, 2, 2, 8, 7, 4, 3, 5, 2, 1, 1, 3, 7, 4, 2, 1, 8, 3, 3, 4, 3, 3, 7, 1, 2, 2, 1, 4, 4, 2, 4, 4, 4, 3, 3, 3, 3, 2, 4, 3, 4, 3, 2, 4, 3, 2, 7, 1, 3, 4, 4, 1, 4, 3, 3, 1, 4, 4, 1, 3, 1, 4, 1, 2, 3, 3, 4, 7, 3, 5, 1, 1, 4, 4, 3, 2, 3, 3, 1, 6, 2, 2, 2, 3, 1, 1, 4, 2, 4, 2, 5, 2, 4, 2, 3, 2, 2, 1, 3, 3, 5, 7, 2, 4, 2, 3, 1, 3, 4, 1, 3, 2, 2, 2, 3, 4, 2, 4, 7, 6, 4, 6, 2, 1, 4, 2, 5, 3, 2, 1, 2, 4, 3, 1, 2, 5, 1, 3, 4, 4, 3, 8, 1, 1, 2, 1, 2, 2, 3, 4, 1, 3, 2, 2, 4, 1, 3, 3, 3, 1, 1, 6, 2, 2, 3, 1, 5, 4, 2, 6, 4, 5, 2, 1, 2, 2, 4, 5, 7, 7, 3, 2, 3, 2, 1, 4, 2, 3, 2, 1, 3, 2, 4, 6, 2, 5, 2, 4, 4, 3, 2, 3, 3, 1, 3, 5, 5, 1, 2, 5, 1, 2, 5, 6, 4, 2, 4, 7, 4, 3, 3, 2, 3, 1, 1, 3, 2, 6, 4, 5, 8, 2, 9, 5, 3, 4, 5, 4, 1, 2, 2, 4, 3, 2, 3, 2, 6, 1, 5, 2, 3, 4, 3, 3, 2, 2, 1, 1, 3, 1, 3, 3, 3, 5, 1, 6, 5, 3, 6, 1, 4, 1, 2, 2, 1, 4, 4, 5, 2, 1, 5, 4, 4, 1, 2, 2, 2, 2, 4, 2, 5, 3, 4, 3, 4, 1, 6, 2, 4, 2, 5, 2, 6, 2, 2, 4, 3, 3, 4, 3, 3, 2, 8, 2, 3, 3, 2, 3, 3, 5, 1, 3, 2, 5, 8, 2, 3, 2, 2, 2, 4, 3, 5, 1, 2, 2, 4, 2, 1, 3, 3, 3, 9, 2, 5, 2, 5, 3, 6, 3, 4, 4, 3, 5, 2, 4, 7, 3, 3, 2, 2, 3, 3, 4, 4, 2, 5, 1, 3, 2, 1, 2, 9, 2, 3, 3, 2, 4, 5, 1, 1, 5, 3, 3, 3, 1, 6, 5, 3, 6, 1, 3, 2, 3, 1, 3, 5, 5, 3, 5, 3, 2, 5, 1, 3, 3, 3, 3, 4, 5, 5, 1, 3, 4, 3, 6, 4, 2, 2, 4, 2, 3, 4, 3, 3, 1, 4, 2, 1, 3, 1, 2, 4, 5, 6, 2, 4, 1, 6, 5, 4, 4, 1, 4, 1, 2, 2, 2, 3, 3, 3, 1, 4, 2, 2, 5, 4, 2, 3, 4, 4, 1, 4, 4, 8, 6, 2, 4, 4, 4, 2, 4, 1, 4, 3, 3, 4, 7, 4, 2, 3, 3, 2, 1, 4, 8, 4, 1, 2, 2, 3, 1, 3, 6, 2, 2, 6, 3, 1, 9, 1, 4, 3, 4, 3, 4, 4, 3, 1, 3, 1, 2, 2, 5, 2, 2, 3, 3, 5, 4, 2, 5, 4, 1, 1, 1, 2, 2, 2, 4, 1, 2, 2, 3, 1, 4, 2, 1, 2, 5, 5, 1, 2, 6, 4, 6, 5, 3, 5, 2, 2, 3, 5, 3, 5, 6, 1, 2, 2, 6, 1, 3, 4, 3, 4, 7, 4, 3, 7, 4, 4, 2, 2, 1, 2, 2, 2, 8, 1, 4, 3, 1, 4, 1, 5, 5, 1, 3, 1, 7, 2, 3, 4, 3, 3, 3, 4, 1, 1, 1, 5, 1, 2, 1, 2, 3, 3, 2, 2, 1, 1, 3, 6, 4, 2, 1, 7, 3, 3, 4, 3, 2, 4, 4, 3, 4, 7, 1, 3, 4, 2, 5, 3, 3, 6, 5, 4, 1, 3, 8, 2, 3, 3, 6, 1, 3, 2];
country=[{609},{202},{296},{729,166},{326,992,943},{574,243,307},{311,828,937,933,97},{913,181,909,345,907,905,224,942},{83,55,809,197,249},{853,878,7},{890,100,243},{751,134},{268,505,229,50,173},{870,993,387},{379},{133,521},{416},{590,378},{411},{559,450},{149,934},{70,272,557,125},{264,309,234,102,639},{94,647,697,983,152},{20,778},{233,194,680,914,726,638},{348,505},{853,643},{208,60,404},{127,695},{133,24,106,293,746},{510,995,612,79},{242,875,780,180,79,376},{83,610,295,625,25},{994,448,404,377,199,44,264},{432},{861},{729},{252,443,7,409},{628},{849,792,437,344},{836,678},{700},{255,856,748,426,102},{126,726,362,975,102},{810,753,321},{162,261,981,838,696},{168},{604},{19,160,328,325},{330,834,184},{627,638,304,413,528,625,199},{469,325,920,900},{383,378,804},{43,390,265},{473},{201,34},{922,277,761},{417,227},{930,641,846},{328},{610},{749,557,296,404,422},{293,311,222,788},{359,20,800},{402,497,775,522},{994,683,575,838,985,681},{419,822,434,852},{993,454,547},{477},{976},{718,211},{728,588},{365,110,693,410},{609,953,261},{773,390},{446,44,277,243,293,943},{365,587,639},{693,668,329},{612},{426,305,348},{851,153},{349,306},{264,664,412},{269,570,876,524},{721,944},{257,160,668,125,13,2,794,112},{577,918},{4,391,978},{838,949,812,938,910},{661,500,191,306,255,382},{24,697,222,483},{726,276},{215},{420,647,52},{281,250,764},{858,961,716},{851,930},{50,288},{420,763,870,476,724,300},{378,522,522,680,214,2,477,116},{513,860,500,180,55,505,700},{469,950,332,485},{783,829,404},{817,828,300,585,199,846},{156,831},{189,977},{31,587,675,449,233},{565},{455,861},{606,148},{287,777,441},{310,94},{957,642,687},{494},{285,970,845,288,18},{300,665,756},{700,878},{921,191},{309,50,798},{918,828,296,252,728,810},{812},{278,933,753},{368,854},{557,142},{119,420,491,937,22},{681,113,292,577,510},{722,573,278,256},{117},{63,330,922,747},{590,460,695,408},{612,823,804},{368,248},{138,826,271,480,171},{151,520},{583,889,736},{227,937,222,184},{419,91,315,909,494},{532,272,107,19},{112,693,91},{925,467,700,52,745},{90,937},{41},{67,341,891},{538,572,94},{196,517,24,380,312,878,590},{788,210},{433,848,658},{994,879},{42,417,851},{343,196,22},{22,969,750,555},{228,682,293},{775,856},{55},{353,11},{122,310,943},{648,113,11},{305,377},{232,310},{261,49,629,404,28,56},{697,357,503,665,404},{970,150,353,501},{298,545,847},{634,278,500,811,523,285},{958,390},{879,268,571,760},{293,448,215},{427,339,356},{198,226,837,321,232,943},{402,54,778},{466,113,115},{920,429,73,597,921,628,476},{337,344,933,790},{127,644,579},{600,700},{40},{707,88},{100,985,284,40,306},{444,559},{431,55},{854,426},{907,309,547,830,876,150,83},{67,187},{538,53,681,264},{22,732,604},{299,13},{847,968,19},{25,958,175,444,40,859,557},{831,329},{838,993,19},{979,816,449,644},{404,476},{744,686,504},{164,261,554,472,477},{76,331,331},{876},{149,672,583},{837,423},{127,287,25},{214,843,494},{260,380,500},{522,246,298,211,89},{524,972,421},{587,113,378},{254,86},{979,511,355,793,285},{24,2},{943,178,259,163,339},{132,276},{603,285,554},{594,849},{255,13,46,163},{150,641,426,947,373},{421},{289,408,815,934,724,681,764},{328,52,942,494,662},{211,451},{22,933,377},{933,878,933,771,376},{589},{357,972,724,68,418,700},{481,383,164,866},{25,201,996,683,171},{579,681,341,583,547,411,743},{360,958},{328,264,319,687},{581,180},{830,510},{34,161,209,840},{856,776,992,272},{391,448,904},{847,557},{771,909},{270},{834,438,996},{761,671},{827,856},{17,259},{200,364},{35,350,357},{2,133,686},{233,772,691},{982,996,194,395},{940,331,826},{102,763,479},{985,170,915,207},{282,916,42,11,828},{571},{62,20,86},{144,293,155,887,835,609},{449},{995,718,64,519},{479,365,736,25,780},{720,447,753},{826},{996,379},{994},{754,171,863,688},{257},{736,84,914,832,856,315},{160,693,920,6},{874,371,870,357},{943,55,390},{539},{746,641},{296,498,876},{853,446,5},{255,603,259,867},{681,464},{344,321,286,244,553},{457},{860,125},{443,963,772,344,579,55},{663},{548,845,711},{276,684,992,85,822},{380,538},{576,876,207,292},{526,502,969,354},{22,372},{828,98,854,878,937,496,62,341},{728,604,552},{788,635,306},{59,997,356,301},{252,783},{683},{789},{411,975,830,745,759,222},{306,693},{221,312,511},{595,116},{682,434,503,9,574},{403,148,284,310,522,805,133,676},{838,233,865,212},{383,82},{485},{193,504,642,745},{390,994,353,382,930,472},{997,807,798,836},{3,106},{588,509},{151,9,131,883,757,67,270,594},{274,45,847,975,838,957,32},{221,683,201,586},{24,558,638},{470,171,143,950,428},{771,827},{892},{824},{330,838,71},{609,843,590,558,612,154,16},{623,475,372,777},{367,545},{158},{596,739,404,763,254,239,597,907},{866,5,940},{874,587,510},{399,348,698,240},{308,795,587},{383,730,263},{467,198,152,683,50,189,609},{642},{383,796},{918,873},{220},{21,761,778,17},{778,310,405,266},{391,874},{771,902,601,830},{255,191,288,587},{874,123,127,269},{383,158,274},{189,108,223},{989,114,897},{156,94,685},{379,958},{558,383,353,212},{329,817,378},{432,356,956,615},{704,539,727},{994,483},{372,697,6,609},{697,971,937},{94,309},{262,700,629,697,52,382,583},{325},{377,79,189},{904,573,639,379},{485,105,49,5},{331},{304,133,77,609},{232,464,587},{596,825,189},{532},{979,93,620,219},{278,79,438,385},{276},{180,443,809},{968},{866,763,990,608},{243},{924,115},{557,603,400},{830,777,840},{35,415,172,503},{46,265,658,587,479,134,67},{948,665,855},{160,67,635,330,164},{297},{477},{630,975,19,940},{184,16,104,194},{594,504,394},{607,780},{243,710,485},{642,511,798},{937},{67,726,975,404,459,637},{629,633},{628,426},{547,90},{704,294,830},{152},{274},{255,788,715,129},{893,19},{642,743,998,801},{408,460},{49,44,328,4,126},{391,448},{243,432,19,19},{171,669},{554,368,470},{723,147},{701,90},{798},{50,272,7},{447,970,828},{189,733,20,740,205},{464,315,847,178,69,251,945},{274,693},{609,169,421,641},{860,17},{834,160,769},{695},{860,192,943},{22,494,653,571},{744},{903,90,22},{985,365},{768,88},{540,38},{303,776,144},{455,831,94,229},{108,549},{309,261,687,612},{787,610,903,628,83,438,311},{90,369,249,620,873,90},{348,902,944,171},{893,517,662,344,363,727},{953,356},{392},{401,150,698,491},{304,612},{109,217,304,136,204},{674,798,551},{642,50},{605},{682,155},{161,757,84,44},{576,391,400},{755},{993,387},{636,496,518,328,260},{754},{784,336,728},{397,294,260,601},{262,922,920,576},{872,112,52},{256,217,634,469,879,439,412,905},{387},{94},{88,288},{383},{549,808},{881,164},{540,231,936},{467,524,940,650},{724},{373,77,13},{499,956},{528,352},{898,521,587,263},{860},{937,860,117},{307,612,670},{77,859,583},{776},{93},{348,380,684,485,63,717},{950,410},{17,629},{883,612,9},{828},{356,909,494,934,898},{264,728,896,337},{37,42},{766,298,28,810,46,573},{952,359,196,896},{298,641,476,613,820},{214,191},{353},{16,975},{736,689},{291,711,421,949},{246,284,67,524,222},{260,505,169,378,557,87,539},{852,579,76,554,252,169,759},{553,349,531},{185,391},{533,296,310},{772,542},{308},{665,160,25,708},{373,416},{876,311,552},{994,356},{648},{212,716,293},{922,391},{583,92,82,344},{304,729,983,677,492,341},{371,881},{687,526,147,533,62},{309,6},{6,236,538,133},{898,232,234,246},{105,464,695},{2,557},{695,285,505},{368,833,856},{224},{133,937,909},{263,900,469,777,402},{532,743,462,126,983},{4},{232,743},{198,870,831,295,457},{876},{117,199},{223,935,408,432,383},{296,214,113,632,444,255},{142,605,341,505},{865,1},{499,285,272,830},{938,891,771,571,591,897,560},{626,97,510,1000},{570,639,465},{276,170,212},{233,402},{211,411,20},{315},{439},{273,904,764},{382,524},{963,701,552,298,86,245},{393,985,220,425},{356,83,21,878,216},{178,962,134,296,386,570,389,530},{822,404},{38,331,449,658,225,521,603,642,164},{751,252,292,828,761},{771,594,263},{54,946,88,309},{44,761,597,968,586},{20,379,997,746},{772},{388,321},{939,947},{810,848,223,722},{870,390,869},{387,700},{745,7,319},{342,777},{438,810,594,819,510,832},{960},{257,684,909,438,478},{909,191},{877,672,717},{112,539,71,561},{538,223,937},{724,754,863},{223,896},{838,429},{856},{771},{589,640,870},{993},{494,122,485},{43,119,274},{164,566,404},{533,984,69,370,704},{823},{222,761,220,205,298,154},{455,993,884,811,996},{11,169,94},{817,125,385,4,727,907},{270},{163,702,752,376},{198},{54,386},{751,579},{215},{397,708,775,601},{2,876,395,403},{176,579,902,694,6},{997,631},{121},{285,232,863,22,590},{244,8,127,870},{160,822,463,915},{922},{769,759},{979,184},{178,638},{71,562},{205,453,615,93},{964,695},{783,667,777,634,761},{122,223,191},{105,539,577,44},{376,822,511},{632,336,53,234},{958},{511,72,425,97,88,650},{876,130},{444,396,117,164},{340,585},{562,970,638,620,943},{924,665},{979,292,109,315,356,54},{348,24},{850,683},{576,348,79,50},{861,331,394},{697,642,831},{554,14,288,97},{349,684,256},{97,50,126},{697,688},{224,88,860,42,256,36,772,260},{815,212},{119,603,775},{925,943,728},{831,321},{976,933,503},{612,491,180},{413,542,579,488,898},{19},{465,188,888},{704,387},{547,729,681,436,372},{377,88,479,364,180,824,298,260},{352,801},{237,777,921},{116,737},{449,461},{264,826},{676,224,323,150},{19,122,739},{55,759,833,862,328},{658},{724,275},{788,160},{255,243,28,861},{199,772},{62},{169,629,642},{663,880,255},{269,697,369},{289,970,706,719,664,969,984,62,119},{726,494},{24,726,585,88,390},{1,994},{745,383,961,180,382},{122,682,729},{116,582,687,695,46,279},{876,745,417},{52,588,969,304},{216,487,469,540},{267,861,629},{763,107,520,784,598},{17,612},{618,68,150,454},{877,461,646,697,43,970,12},{664,243,864},{920,63,601},{329,536},{503,539},{755,518,937},{682,473,336},{328,507,700,184},{642,505,236,930},{717,994},{84,716,405,467,997},{605},{983,968,40},{4,605},{628},{742,348},{315,581,510,942,118,499,418,730,451},{711,174},{907,511,962},{376,387,249},{924,510},{112,892,524,693},{798,174,577,976,26},{196},{490},{44,860,390,53,617},{988,771,574},{382,41,513},{453,785,344},{642},{288,219,30,439,171,933},{67,793,603,455,90},{62,983,357},{432,451,287,798,377,795},{452},{881,691,368},{864,487},{774,784,973},{883},{784,876,816},{524,298,441,763,232},{727,2,708,479,344},{876,34,620},{379,22,210,119,356},{408,256,922},{2,682},{699,260,822,235,534},{190},{504,704,365},{996,559,417},{418,135,844},{212,809,99},{511,448,855,825},{583,309,597,67,391},{665,683,728,341,243},{889},{467,596,331},{588,558,698,207},{557,727,63},{587,67,223,9,252,762},{414,63,7,42},{617,736},{3,564},{212,408,695,337},{667,389},{975,743,511},{557,796,443,117},{742,663,491},{397,511,677},{798},{537,949,631,67},{221,847},{272},{323,232,937},{315},{448,776},{83,937,583,319},{43,986,729,356,117},{460,903,4,92,979,207},{40,857},{376,20,643,293},{108},{460,849,245,725,451,425},{953,20,522,926,482},{309,404,960,614},{722,256,168,214},{191},{539,547,589,282},{184},{43,884},{930,180},{6,385},{936,19,168},{350,638,102},{127,180,222},{797},{594,223,731,711},{304,781},{88,287},{333,99,25,505,634},{868,854,49,669},{37,642},{562,862,270},{247,210,6,726},{641,519,587,845},{920},{128,871,639,949},{762,985,831,19},{799,363,233,956,432,634,205,27},{920,9,321,224,373,331},{412,335},{35,706,994,727},{264,53,750,643},{983,796,44,554},{639,105},{603,930,345,540},{406},{612,74,689,600},{828,511,559},{826,890,775},{42,143,861,958},{835,905,781,349,325,62,370},{307,45,449,466},{603,610},{604,856,878},{112,878,640},{195,311},{485},{684,604,192,956},{716,878,693,641,144,969,697,616},{36,298,40,363},{661},{993,851},{883,82},{894,66,491},{463},{188,554,896},{705,734,625,465,428,940},{743,272},{572,315},{970,722,2,660,907,610},{321,355,163},{928},{105,363,40,212,910,496,420,583,767},{996},{349,556,278,629},{634,20,381},{768,980,901,684},{894,973,26},{79,35,648,464},{341,777,233,362},{128,90,52},{494},{55,471,937},{424},{620,278},{349,243},{220,426,402,441,152},{309,562},{436,425},{511,590,853},{214,560,396},{847,603,363,778,305},{331,742,50,933},{152,761},{755,557,478,848,881},{933,298,221,754},{821},{638},{801},{201,927},{310,105},{962,161},{260,524,539,603},{99},{889,156},{469,903},{814,788,142},{351},{743,112,469,957},{86,503},{169},{641,642},{918,285,466,412,823},{665,630,346,508,590},{910},{391,628},{681,747,24,464,135,592},{99,462,1000,729},{223,939,645,557,854,878},{831,322,751,402,554},{119,40,574},{326,577,668,783,162},{775,448},{703,687},{728,294,500},{214,336,867,426,639},{481,559,609},{634,646,25,164,753},{421,682,881,594,881,312},{196},{42,323},{105,254},{317,20,425,695,451,763},{136},{17,227,462},{310,234,386,44},{510,19,477},{402,726,309,90},{199,244,296,583,717,22,861},{880,704,416,814},{296,711,311},{354,199,861,348,682,135,256},{298,504,87,133},{822,188,24,260},{358,24},{884,205},{740},{328,830},{281,955},{67,768},{71,979,992,601,932,62,496,735},{664},{476,28,133,579},{682,505,515},{328},{20,127,102,448},{898},{896,488,293,798,13},{798,959,728,315,856},{152},{528,189,900},{338},{224,240,128,90,390,365,617},{372,972},{241,326,557},{728,68,435,746},{296,121,483},{996,815,128},{52,511,884},{746,539,793,645},{373},{20},{502},{597,773,294,522,370},{510},{990,364},{365},{102,978},{770,831,491},{259,259,798},{188,378},{488,180},{576},{775},{870,959,179},{65,184,19,469,60,243},{783,999,623,675},{438,293},{255},{440,127,684,477,223,71,36},{67,610,995},{672,754,854},{381,674,809,594},{99,89,492},{554,109},{612,212,169,213},{416,683,662,985},{207,907,490},{13,762,717,252},{331,328,553,454,298,420,460},{326},{505,89,608},{759,695,319,413},{370,63},{65,570,825,367,777},{729,727,127},{341,707,398},{417,172,368,583,594,181},{308,876,557,23,920},{366,777,207,540},{42},{737,373,125},{428,195,499,395,758,228,774,180},{232,993},{552,906,185},{847,375,48},{243,319,542,24,319,337},{924},{252,373,142},{1,583}]