A Python solution to Project Euler Problem 99

euler99.py

""" Project Euler Problem 99 http://projecteuler.net/index.php?section=problems&id=99 """
def max_base_exp(base_exps):
  from math import log
  return reduce(lambda a, b: a if a[2] * log(a[1]) > b[2] * log(b[1]) else b, base_exps)

print max_base_exp([
 (1, 519432, 525806),
 (2, 632382, 518061),
 (3, 78864, 613712),
 (4, 466580, 530130),
 (5, 780495, 510032),
 (6, 525895, 525320),
 (7, 15991, 714883),
 (8, 960290, 502358),
 (9, 760018, 511029),
 (10, 166800, 575487),
 (11, 210884, 564478),
 (12, 555151, 523163),
 (13, 681146, 515199),
 (14, 563395, 522587),
 (15, 738250, 512126),
 (16, 923525, 503780),
 (17, 595148, 520429),
 (18, 177108, 572629),
 (19, 750923, 511482),
 (20, 440902, 532446),
 (21, 881418, 505504),
 (22, 422489, 534197),
 (23, 979858, 501616),
 (24, 685893, 514935),
 (25, 747477, 511661),
 (26, 167214, 575367),
 (27, 234140, 559696),
 (28, 940238, 503122),
 (29, 728969, 512609),
 (30, 232083, 560102),
 (31, 900971, 504694),
 (32, 688801, 514772),
 (33, 189664, 569402),
 (34, 891022, 505104),
 (35, 445689, 531996),
 (36, 119570, 591871),
 (37, 821453, 508118),
 (38, 371084, 539600),
 (39, 911745, 504251),
 (40, 623655, 518600),
 (41, 144361, 582486),
 (42, 352442, 541775),
 (43, 420726, 534367),
 (44, 295298, 549387),
 (45, 6530, 787777),
 (46, 468397, 529976),
 (47, 672336, 515696),
 (48, 431861, 533289),
 (49, 84228, 610150),
 (50, 805376, 508857),
 (51, 444409, 532117),
 (52, 33833, 663511),
 (53, 381850, 538396),
 (54, 402931, 536157),
 (55, 92901, 604930),
 (56, 304825, 548004),
 (57, 731917, 512452),
 (58, 753734, 511344),
 (59, 51894, 637373),
 (60, 151578, 580103),
 (61, 295075, 549421),
 (62, 303590, 548183),
 (63, 333594, 544123),
 (64, 683952, 515042),
 (65, 60090, 628880),
 (66, 951420, 502692),
 (67, 28335, 674991),
 (68, 714940, 513349),
 (69, 343858, 542826),
 (70, 549279, 523586),
 (71, 804571, 508887),
 (72, 260653, 554881),
 (73, 291399, 549966),
 (74, 402342, 536213),
 (75, 408889, 535550),
 (76, 40328, 652524),
 (77, 375856, 539061),
 (78, 768907, 510590),
 (79, 165993, 575715),
 (80, 976327, 501755),
 (81, 898500, 504795),
 (82, 360404, 540830),
 (83, 478714, 529095),
 (84, 694144, 514472),
 (85, 488726, 528258),
 (86, 841380, 507226),
 (87, 328012, 544839),
 (88, 22389, 690868),
 (89, 604053, 519852),
 (90, 329514, 544641),
 (91, 772965, 510390),
 (92, 492798, 527927),
 (93, 30125, 670983),
 (94, 895603, 504906),
 (95, 450785, 531539),
 (96, 840237, 507276),
 (97, 380711, 538522),
 (98, 63577, 625673),
 (99, 76801, 615157),
 (100, 502694, 527123),
 (101, 597706, 520257),
 (102, 310484, 547206),
 (103, 944468, 502959),
 (104, 121283, 591152),
 (105, 451131, 531507),
 (106, 566499, 522367),
 (107, 425373, 533918),
 (108, 40240, 652665),
 (109, 39130, 654392),
 (110, 714926, 513355),
 (111, 469219, 529903),
 (112, 806929, 508783),
 (113, 287970, 550487),
 (114, 92189, 605332),
 (115, 103841, 599094),
 (116, 671839, 515725),
 (117, 452048, 531421),
 (118, 987837, 501323),
 (119, 935192, 503321),
 (120, 88585, 607450),
 (121, 613883, 519216),
 (122, 144551, 582413),
 (123, 647359, 517155),
 (124, 213902, 563816),
 (125, 184120, 570789),
 (126, 258126, 555322),
 (127, 502546, 527130),
 (128, 407655, 535678),
 (129, 401528, 536306),
 (130, 477490, 529193),
 (131, 841085, 507237),
 (132, 732831, 512408),
 (133, 833000, 507595),
 (134, 904694, 504542),
 (135, 581435, 521348),
 (136, 455545, 531110),
 (137, 873558, 505829),
 (138, 94916, 603796),
 (139, 720176, 513068),
 (140, 545034, 523891),
 (141, 246348, 557409),
 (142, 556452, 523079),
 (143, 832015, 507634),
 (144, 173663, 573564),
 (145, 502634, 527125),
 (146, 250732, 556611),
 (147, 569786, 522139),
 (148, 216919, 563178),
 (149, 521815, 525623),
 (150, 92304, 605270),
 (151, 164446, 576167),
 (152, 753413, 511364),
 (153, 11410, 740712),
 (154, 448845, 531712),
 (155, 925072, 503725),
 (156, 564888, 522477),
 (157, 7062, 780812),
 (158, 641155, 517535),
 (159, 738878, 512100),
 (160, 636204, 517828),
 (161, 372540, 539436),
 (162, 443162, 532237),
 (163, 571192, 522042),
 (164, 655350, 516680),
 (165, 299741, 548735),
 (166, 581914, 521307),
 (167, 965471, 502156),
 (168, 513441, 526277),
 (169, 808682, 508700),
 (170, 237589, 559034),
 (171, 543300, 524025),
 (172, 804712, 508889),
 (173, 247511, 557192),
 (174, 543486, 524008),
 (175, 504383, 526992),
 (176, 326529, 545039),
 (177, 792493, 509458),
 (178, 86033, 609017),
 (179, 126554, 589005),
 (180, 579379, 521481),
 (181, 948026, 502823),
 (182, 404777, 535969),
 (183, 265767, 554022),
 (184, 266876, 553840),
 (185, 46631, 643714),
 (186, 492397, 527958),
 (187, 856106, 506581),
 (188, 795757, 509305),
 (189, 748946, 511584),
 (190, 294694, 549480),
 (191, 409781, 535463),
 (192, 775887, 510253),
 (193, 543747, 523991),
 (194, 210592, 564536),
 (195, 517119, 525990),
 (196, 520253, 525751),
 (197, 247926, 557124),
 (198, 592141, 520626),
 (199, 346580, 542492),
 (200, 544969, 523902),
 (201, 506501, 526817),
 (202, 244520, 557738),
 (203, 144745, 582349),
 (204, 69274, 620858),
 (205, 292620, 549784),
 (206, 926027, 503687),
 (207, 736320, 512225),
 (208, 515528, 526113),
 (209, 407549, 535688),
 (210, 848089, 506927),
 (211, 24141, 685711),
 (212, 9224, 757964),
 (213, 980684, 501586),
 (214, 175259, 573121),
 (215, 489160, 528216),
 (216, 878970, 505604),
 (217, 969546, 502002),
 (218, 525207, 525365),
 (219, 690461, 514675),
 (220, 156510, 578551),
 (221, 659778, 516426),
 (222, 468739, 529945),
 (223, 765252, 510770),
 (224, 76703, 615230),
 (225, 165151, 575959),
 (226, 29779, 671736),
 (227, 928865, 503569),
 (228, 577538, 521605),
 (229, 927555, 503618),
 (230, 185377, 570477),
 (231, 974756, 501809),
 (232, 800130, 509093),
 (233, 217016, 563153),
 (234, 365709, 540216),
 (235, 774508, 510320),
 (236, 588716, 520851),
 (237, 631673, 518104),
 (238, 954076, 502590),
 (239, 777828, 510161),
 (240, 990659, 501222),
 (241, 597799, 520254),
 (242, 786905, 509727),
 (243, 512547, 526348),
 (244, 756449, 511212),
 (245, 869787, 505988),
 (246, 653747, 516779),
 (247, 84623, 609900),
 (248, 839698, 507295),
 (249, 30159, 670909),
 (250, 797275, 509234),
 (251, 678136, 515373),
 (252, 897144, 504851),
 (253, 989554, 501263),
 (254, 413292, 535106),
 (255, 55297, 633667),
 (256, 788650, 509637),
 (257, 486748, 528417),
 (258, 150724, 580377),
 (259, 56434, 632490),
 (260, 77207, 614869),
 (261, 588631, 520859),
 (262, 611619, 519367),
 (263, 100006, 601055),
 (264, 528924, 525093),
 (265, 190225, 569257),
 (266, 851155, 506789),
 (267, 682593, 515114),
 (268, 613043, 519275),
 (269, 514673, 526183),
 (270, 877634, 505655),
 (271, 878905, 505602),
 (272, 1926, 914951),
 (273, 613245, 519259),
 (274, 152481, 579816),
 (275, 841774, 507203),
 (276, 71060, 619442),
 (277, 865335, 506175),
 (278, 90244, 606469),
 (279, 302156, 548388),
 (280, 399059, 536557),
 (281, 478465, 529113),
 (282, 558601, 522925),
 (283, 69132, 620966),
 (284, 267663, 553700),
 (285, 988276, 501310),
 (286, 378354, 538787),
 (287, 529909, 525014),
 (288, 161733, 576968),
 (289, 758541, 511109),
 (290, 823425, 508024),
 (291, 149821, 580667),
 (292, 269258, 553438),
 (293, 481152, 528891),
 (294, 120871, 591322),
 (295, 972322, 501901),
 (296, 981350, 501567),
 (297, 676129, 515483),
 (298, 950860, 502717),
 (299, 119000, 592114),
 (300, 392252, 537272),
 (301, 191618, 568919),
 (302, 946699, 502874),
 (303, 289555, 550247),
 (304, 799322, 509139),
 (305, 703886, 513942),
 (306, 194812, 568143),
 (307, 261823, 554685),
 (308, 203052, 566221),
 (309, 217330, 563093),
 (310, 734748, 512313),
 (311, 391759, 537328),
 (312, 807052, 508777),
 (313, 564467, 522510),
 (314, 59186, 629748),
 (315, 113447, 594545),
 (316, 518063, 525916),
 (317, 905944, 504492),
 (318, 613922, 519213),
 (319, 439093, 532607),
 (320, 445946, 531981),
 (321, 230530, 560399),
 (322, 297887, 549007),
 (323, 459029, 530797),
 (324, 403692, 536075),
 (325, 855118, 506616),
 (326, 963127, 502245),
 (327, 841711, 507208),
 (328, 407411, 535699),
 (329, 924729, 503735),
 (330, 914823, 504132),
 (331, 333725, 544101),
 (332, 176345, 572832),
 (333, 912507, 504225),
 (334, 411273, 535308),
 (335, 259774, 555036),
 (336, 632853, 518038),
 (337, 119723, 591801),
 (338, 163902, 576321),
 (339, 22691, 689944),
 (340, 402427, 536212),
 (341, 175769, 572988),
 (342, 837260, 507402),
 (343, 603432, 519893),
 (344, 313679, 546767),
 (345, 538165, 524394),
 (346, 549026, 523608),
 (347, 61083, 627945),
 (348, 898345, 504798),
 (349, 992556, 501153),
 (350, 369999, 539727),
 (351, 32847, 665404),
 (352, 891292, 505088),
 (353, 152715, 579732),
 (354, 824104, 507997),
 (355, 234057, 559711),
 (356, 730507, 512532),
 (357, 960529, 502340),
 (358, 388395, 537687),
 (359, 958170, 502437),
 (360, 57105, 631806),
 (361, 186025, 570311),
 (362, 993043, 501133),
 (363, 576770, 521664),
 (364, 215319, 563513),
 (365, 927342, 503628),
 (366, 521353, 525666),
 (367, 39563, 653705),
 (368, 752516, 511408),
 (369, 110755, 595770),
 (370, 309749, 547305),
 (371, 374379, 539224),
 (372, 919184, 503952),
 (373, 990652, 501226),
 (374, 647780, 517135),
 (375, 187177, 570017),
 (376, 168938, 574877),
 (377, 649558, 517023),
 (378, 278126, 552016),
 (379, 162039, 576868),
 (380, 658512, 516499),
 (381, 498115, 527486),
 (382, 896583, 504868),
 (383, 561170, 522740),
 (384, 747772, 511647),
 (385, 775093, 510294),
 (386, 652081, 516882),
 (387, 724905, 512824),
 (388, 499707, 527365),
 (389, 47388, 642755),
 (390, 646668, 517204),
 (391, 571700, 522007),
 (392, 180430, 571747),
 (393, 710015, 513617),
 (394, 435522, 532941),
 (395, 98137, 602041),
 (396, 759176, 511070),
 (397, 486124, 528467),
 (398, 526942, 525236),
 (399, 878921, 505604),
 (400, 408313, 535602),
 (401, 926980, 503640),
 (402, 882353, 505459),
 (403, 566887, 522345),
 (404, 3326, 853312),
 (405, 911981, 504248),
 (406, 416309, 534800),
 (407, 392991, 537199),
 (408, 622829, 518651),
 (409, 148647, 581055),
 (410, 496483, 527624),
 (411, 666314, 516044),
 (412, 48562, 641293),
 (413, 672618, 515684),
 (414, 443676, 532187),
 (415, 274065, 552661),
 (416, 265386, 554079),
 (417, 347668, 542358),
 (418, 31816, 667448),
 (419, 181575, 571446),
 (420, 961289, 502320),
 (421, 365689, 540214),
 (422, 987950, 501317),
 (423, 932299, 503440),
 (424, 27388, 677243),
 (425, 746701, 511701),
 (426, 492258, 527969),
 (427, 147823, 581323),
 (428, 57918, 630985),
 (429, 838849, 507333),
 (430, 678038, 515375),
 (431, 27852, 676130),
 (432, 850241, 506828),
 (433, 818403, 508253),
 (434, 131717, 587014),
 (435, 850216, 506834),
 (436, 904848, 504529),
 (437, 189758, 569380),
 (438, 392845, 537217),
 (439, 470876, 529761),
 (440, 925353, 503711),
 (441, 285431, 550877),
 (442, 454098, 531234),
 (443, 823910, 508003),
 (444, 318493, 546112),
 (445, 766067, 510730),
 (446, 261277, 554775),
 (447, 421530, 534289),
 (448, 694130, 514478),
 (449, 120439, 591498),
 (450, 213308, 563949),
 (451, 854063, 506662),
 (452, 365255, 540263),
 (453, 165437, 575872),
 (454, 662240, 516281),
 (455, 289970, 550181),
 (456, 847977, 506933),
 (457, 546083, 523816),
 (458, 413252, 535113),
 (459, 975829, 501767),
 (460, 361540, 540701),
 (461, 235522, 559435),
 (462, 224643, 561577),
 (463, 736350, 512229),
 (464, 328303, 544808),
 (465, 35022, 661330),
 (466, 307838, 547578),
 (467, 474366, 529458),
 (468, 873755, 505819),
 (469, 73978, 617220),
 (470, 827387, 507845),
 (471, 670830, 515791),
 (472, 326511, 545034),
 (473, 309909, 547285),
 (474, 400970, 536363),
 (475, 884827, 505352),
 (476, 718307, 513175),
 (477, 28462, 674699),
 (478, 599384, 520150),
 (479, 253565, 556111),
 (480, 284009, 551093),
 (481, 343403, 542876),
 (482, 446557, 531921),
 (483, 992372, 501160),
 (484, 961601, 502308),
 (485, 696629, 514342),
 (486, 919537, 503945),
 (487, 894709, 504944),
 (488, 892201, 505051),
 (489, 358160, 541097),
 (490, 448503, 531745),
 (491, 832156, 507636),
 (492, 920045, 503924),
 (493, 926137, 503675),
 (494, 416754, 534757),
 (495, 254422, 555966),
 (496, 92498, 605151),
 (497, 826833, 507873),
 (498, 660716, 516371),
 (499, 689335, 514746),
 (500, 160045, 577467),
 (501, 814642, 508425),
 (502, 969939, 501993),
 (503, 242856, 558047),
 (504, 76302, 615517),
 (505, 472083, 529653),
 (506, 587101, 520964),
 (507, 99066, 601543),
 (508, 498005, 527503),
 (509, 709800, 513624),
 (510, 708000, 513716),
 (511, 20171, 698134),
 (512, 285020, 550936),
 (513, 266564, 553891),
 (514, 981563, 501557),
 (515, 846502, 506991),
 (516, 334, 1190800),
 (517, 209268, 564829),
 (518, 9844, 752610),
 (519, 996519, 501007),
 (520, 410059, 535426),
 (521, 432931, 533188),
 (522, 848012, 506929),
 (523, 966803, 502110),
 (524, 983434, 501486),
 (525, 160700, 577267),
 (526, 504374, 526989),
 (527, 832061, 507640),
 (528, 392825, 537214),
 (529, 443842, 532165),
 (530, 440352, 532492),
 (531, 745125, 511776),
 (532, 13718, 726392),
 (533, 661753, 516312),
 (534, 70500, 619875),
 (535, 436952, 532814),
 (536, 424724, 533973),
 (537, 21954, 692224),
 (538, 262490, 554567),
 (539, 716622, 513264),
 (540, 907584, 504425),
 (541, 60086, 628882),
 (542, 837123, 507412),
 (543, 971345, 501940),
 (544, 947162, 502855),
 (545, 139920, 584021),
 (546, 68330, 621624),
 (547, 666452, 516038),
 (548, 731446, 512481),
 (549, 953350, 502619),
 (550, 183157, 571042),
 (551, 845400, 507045),
 (552, 651548, 516910),
 (553, 20399, 697344),
 (554, 861779, 506331),
 (555, 629771, 518229),
 (556, 801706, 509026),
 (557, 189207, 569512),
 (558, 737501, 512168),
 (559, 719272, 513115),
 (560, 479285, 529045),
 (561, 136046, 585401),
 (562, 896746, 504860),
 (563, 891735, 505067),
 (564, 684771, 514999),
 (565, 865309, 506184),
 (566, 379066, 538702),
 (567, 503117, 527090),
 (568, 621780, 518717),
 (569, 209518, 564775),
 (570, 677135, 515423),
 (571, 987500, 501340),
 (572, 197049, 567613),
 (573, 329315, 544673),
 (574, 236756, 559196),
 (575, 357092, 541226),
 (576, 520440, 525733),
 (577, 213471, 563911),
 (578, 956852, 502490),
 (579, 702223, 514032),
 (580, 404943, 535955),
 (581, 178880, 572152),
 (582, 689477, 514734),
 (583, 691351, 514630),
 (584, 866669, 506128),
 (585, 370561, 539656),
 (586, 739805, 512051),
 (587, 71060, 619441),
 (588, 624861, 518534),
 (589, 261660, 554714),
 (590, 366137, 540160),
 (591, 166054, 575698),
 (592, 601878, 519990),
 (593, 153445, 579501),
 (594, 279899, 551729),
 (595, 379166, 538691),
 (596, 423209, 534125),
 (597, 675310, 515526),
 (598, 145641, 582050),
 (599, 691353, 514627),
 (600, 917468, 504026),
 (601, 284778, 550976),
 (602, 81040, 612235),
 (603, 161699, 576978),
 (604, 616394, 519057),
 (605, 767490, 510661),
 (606, 156896, 578431),
 (607, 427408, 533714),
 (608, 254849, 555884),
 (609, 737217, 512182),
 (610, 897133, 504851),
 (611, 203815, 566051),
 (612, 270822, 553189),
 (613, 135854, 585475),
 (614, 778805, 510111),
 (615, 784373, 509847),
 (616, 305426, 547921),
 (617, 733418, 512375),
 (618, 732087, 512448),
 (619, 540668, 524215),
 (620, 702898, 513996),
 (621, 628057, 518328),
 (622, 640280, 517587),
 (623, 422405, 534204),
 (624, 10604, 746569),
 (625, 746038, 511733),
 (626, 839808, 507293),
 (627, 457417, 530938),
 (628, 479030, 529064),
 (629, 341758, 543090),
 (630, 620223, 518824),
 (631, 251661, 556451),
 (632, 561790, 522696),
 (633, 497733, 527521),
 (634, 724201, 512863),
 (635, 489217, 528217),
 (636, 415623, 534867),
 (637, 624610, 518548),
 (638, 847541, 506953),
 (639, 432295, 533249),
 (640, 400391, 536421),
 (641, 961158, 502319),
 (642, 139173, 584284),
 (643, 421225, 534315),
 (644, 579083, 521501),
 (645, 74274, 617000),
 (646, 701142, 514087),
 (647, 374465, 539219),
 (648, 217814, 562985),
 (649, 358972, 540995),
 (650, 88629, 607424),
 (651, 288597, 550389),
 (652, 285819, 550812),
 (653, 538400, 524385),
 (654, 809930, 508645),
 (655, 738326, 512126),
 (656, 955461, 502535),
 (657, 163829, 576343),
 (658, 826475, 507891),
 (659, 376488, 538987),
 (660, 102234, 599905),
 (661, 114650, 594002),
 (662, 52815, 636341),
 (663, 434037, 533082),
 (664, 804744, 508880),
 (665, 98385, 601905),
 (666, 856620, 506559),
 (667, 220057, 562517),
 (668, 844734, 507078),
 (669, 150677, 580387),
 (670, 558697, 522917),
 (671, 621751, 518719),
 (672, 207067, 565321),
 (673, 135297, 585677),
 (674, 932968, 503404),
 (675, 604456, 519822),
 (676, 579728, 521462),
 (677, 244138, 557813),
 (678, 706487, 513800),
 (679, 711627, 513523),
 (680, 853833, 506674),
 (681, 497220, 527562),
 (682, 59428, 629511),
 (683, 564845, 522486),
 (684, 623621, 518603),
 (685, 242689, 558077),
 (686, 125091, 589591),
 (687, 363819, 540432),
 (688, 686453, 514901),
 (689, 656813, 516594),
 (690, 489901, 528155),
 (691, 386380, 537905),
 (692, 542819, 524052),
 (693, 243987, 557841),
 (694, 693412, 514514),
 (695, 488484, 528271),
 (696, 896331, 504881),
 (697, 336730, 543721),
 (698, 728298, 512647),
 (699, 604215, 519840),
 (700, 153729, 579413),
 (701, 595687, 520398),
 (702, 540360, 524240),
 (703, 245779, 557511),
 (704, 924873, 503730),
 (705, 509628, 526577),
 (706, 528523, 525122),
 (707, 3509, 847707),
 (708, 522756, 525555),
 (709, 895447, 504922),
 (710, 44840, 646067),
 (711, 45860, 644715),
 (712, 463487, 530404),
 (713, 398164, 536654),
 (714, 894483, 504959),
 (715, 619415, 518874),
 (716, 966306, 502129),
 (717, 990922, 501212),
 (718, 835756, 507474),
 (719, 548881, 523618),
 (720, 453578, 531282),
 (721, 474993, 529410),
 (722, 80085, 612879),
 (723, 737091, 512193),
 (724, 50789, 638638),
 (725, 979768, 501620),
 (726, 792018, 509483),
 (727, 665001, 516122),
 (728, 86552, 608694),
 (729, 462772, 530469),
 (730, 589233, 520821),
 (731, 891694, 505072),
 (732, 592605, 520594),
 (733, 209645, 564741),
 (734, 42531, 649269),
 (735, 554376, 523226),
 (736, 803814, 508929),
 (737, 334157, 544042),
 (738, 175836, 572970),
 (739, 868379, 506051),
 (740, 658166, 516520),
 (741, 278203, 551995),
 (742, 966198, 502126),
 (743, 627162, 518387),
 (744, 296774, 549165),
 (745, 311803, 547027),
 (746, 843797, 507118),
 (747, 702304, 514032),
 (748, 563875, 522553),
 (749, 33103, 664910),
 (750, 191932, 568841),
 (751, 543514, 524006),
 (752, 506835, 526794),
 (753, 868368, 506052),
 (754, 847025, 506971),
 (755, 678623, 515342),
 (756, 876139, 505726),
 (757, 571997, 521984),
 (758, 598632, 520198),
 (759, 213590, 563892),
 (760, 625404, 518497),
 (761, 726508, 512738),
 (762, 689426, 514738),
 (763, 332495, 544264),
 (764, 411366, 535302),
 (765, 242546, 558110),
 (766, 315209, 546555),
 (767, 797544, 509219),
 (768, 93889, 604371),
 (769, 858879, 506454),
 (770, 124906, 589666),
 (771, 449072, 531693),
 (772, 235960, 559345),
 (773, 642403, 517454),
 (774, 720567, 513047),
 (775, 705534, 513858),
 (776, 603692, 519870),
 (777, 488137, 528302),
 (778, 157370, 578285),
 (779, 63515, 625730),
 (780, 666326, 516041),
 (781, 619226, 518883),
 (782, 443613, 532186),
 (783, 597717, 520257),
 (784, 96225, 603069),
 (785, 86940, 608450),
 (786, 40725, 651929),
 (787, 460976, 530625),
 (788, 268875, 553508),
 (789, 270671, 553214),
 (790, 363254, 540500),
 (791, 384248, 538137),
 (792, 762889, 510892),
 (793, 377941, 538833),
 (794, 278878, 551890),
 (795, 176615, 572755),
 (796, 860008, 506412),
 (797, 944392, 502967),
 (798, 608395, 519571),
 (799, 225283, 561450),
 (800, 45095, 645728),
 (801, 333798, 544090),
 (802, 625733, 518476),
 (803, 995584, 501037),
 (804, 506135, 526853),
 (805, 238050, 558952),
 (806, 557943, 522972),
 (807, 530978, 524938),
 (808, 634244, 517949),
 (809, 177168, 572616),
 (810, 85200, 609541),
 (811, 953043, 502630),
 (812, 523661, 525484),
 (813, 999295, 500902),
 (814, 840803, 507246),
 (815, 961490, 502312),
 (816, 471747, 529685),
 (817, 380705, 538523),
 (818, 911180, 504275),
 (819, 334149, 544046),
 (820, 478992, 529065),
 (821, 325789, 545133),
 (822, 335884, 543826),
 (823, 426976, 533760),
 (824, 749007, 511582),
 (825, 667067, 516000),
 (826, 607586, 519623),
 (827, 674054, 515599),
 (828, 188534, 569675),
 (829, 565185, 522464),
 (830, 172090, 573988),
 (831, 87592, 608052),
 (832, 907432, 504424),
 (833, 8912, 760841),
 (834, 928318, 503590),
 (835, 757917, 511138),
 (836, 718693, 513153),
 (837, 315141, 546566),
 (838, 728326, 512645),
 (839, 353492, 541647),
 (840, 638429, 517695),
 (841, 628892, 518280),
 (842, 877286, 505672),
 (843, 620895, 518778),
 (844, 385878, 537959),
 (845, 423311, 534113),
 (846, 633501, 517997),
 (847, 884833, 505360),
 (848, 883402, 505416),
 (849, 999665, 500894),
 (850, 708395, 513697),
 (851, 548142, 523667),
 (852, 756491, 511205),
 (853, 987352, 501340),
 (854, 766520, 510705),
 (855, 591775, 520647),
 (856, 833758, 507563),
 (857, 843890, 507108),
 (858, 925551, 503698),
 (859, 74816, 616598),
 (860, 646942, 517187),
 (861, 354923, 541481),
 (862, 256291, 555638),
 (863, 634470, 517942),
 (864, 930904, 503494),
 (865, 134221, 586071),
 (866, 282663, 551304),
 (867, 986070, 501394),
 (868, 123636, 590176),
 (869, 123678, 590164),
 (870, 481717, 528841),
 (871, 423076, 534137),
 (872, 866246, 506145),
 (873, 93313, 604697),
 (874, 783632, 509880),
 (875, 317066, 546304),
 (876, 502977, 527103),
 (877, 141272, 583545),
 (878, 71708, 618938),
 (879, 617748, 518975),
 (880, 581190, 521362),
 (881, 193824, 568382),
 (882, 682368, 515131),
 (883, 352956, 541712),
 (884, 351375, 541905),
 (885, 505362, 526909),
 (886, 905165, 504518),
 (887, 128645, 588188),
 (888, 267143, 553787),
 (889, 158409, 577965),
 (890, 482776, 528754),
 (891, 628896, 518282),
 (892, 485233, 528547),
 (893, 563606, 522574),
 (894, 111001, 595655),
 (895, 115920, 593445),
 (896, 365510, 540237),
 (897, 959724, 502374),
 (898, 938763, 503184),
 (899, 930044, 503520),
 (900, 970959, 501956),
 (901, 913658, 504176),
 (902, 68117, 621790),
 (903, 989729, 501253),
 (904, 567697, 522288),
 (905, 820427, 508163),
 (906, 54236, 634794),
 (907, 291557, 549938),
 (908, 124961, 589646),
 (909, 403177, 536130),
 (910, 405421, 535899),
 (911, 410233, 535417),
 (912, 815111, 508403),
 (913, 213176, 563974),
 (914, 83099, 610879),
 (915, 998588, 500934),
 (916, 513640, 526263),
 (917, 129817, 587733),
 (918, 1820, 921851),
 (919, 287584, 550539),
 (920, 299160, 548820),
 (921, 860621, 506386),
 (922, 529258, 525059),
 (923, 586297, 521017),
 (924, 953406, 502616),
 (925, 441234, 532410),
 (926, 986217, 501386),
 (927, 781938, 509957),
 (928, 461247, 530595),
 (929, 735424, 512277),
 (930, 146623, 581722),
 (931, 839838, 507288),
 (932, 510667, 526494),
 (933, 935085, 503327),
 (934, 737523, 512167),
 (935, 303455, 548204),
 (936, 992779, 501145),
 (937, 60240, 628739),
 (938, 939095, 503174),
 (939, 794368, 509370),
 (940, 501825, 527189),
 (941, 459028, 530798),
 (942, 884641, 505363),
 (943, 512287, 526364),
 (944, 835165, 507499),
 (945, 307723, 547590),
 (946, 160587, 577304),
 (947, 735043, 512300),
 (948, 493289, 527887),
 (949, 110717, 595785),
 (950, 306480, 547772),
 (951, 318593, 546089),
 (952, 179810, 571911),
 (953, 200531, 566799),
 (954, 314999, 546580),
 (955, 197020, 567622),
 (956, 301465, 548487),
 (957, 237808, 559000),
 (958, 131944, 586923),
 (959, 882527, 505449),
 (960, 468117, 530003),
 (961, 711319, 513541),
 (962, 156240, 578628),
 (963, 965452, 502162),
 (964, 992756, 501148),
 (965, 437959, 532715),
 (966, 739938, 512046),
 (967, 614249, 519196),
 (968, 391496, 537356),
 (969, 62746, 626418),
 (970, 688215, 514806),
 (971, 75501, 616091),
 (972, 883573, 505412),
 (973, 558824, 522910),
 (974, 759371, 511061),
 (975, 173913, 573489),
 (976, 891351, 505089),
 (977, 727464, 512693),
 (978, 164833, 576051),
 (979, 812317, 508529),
 (980, 540320, 524243),
 (981, 698061, 514257),
 (982, 69149, 620952),
 (983, 471673, 529694),
 (984, 159092, 577753),
 (985, 428134, 533653),
 (986, 89997, 606608),
 (987, 711061, 513557),
 (988, 779403, 510081),
 (989, 203327, 566155),
 (990, 798176, 509187),
 (991, 667688, 515963),
 (992, 636120, 517833),
 (993, 137410, 584913),
 (994, 217615, 563034),
 (995, 556887, 523038),
 (996, 667229, 515991),
 (997, 672276, 515708),
 (998, 325361, 545187),
 (999, 172115, 573985),
 (1000, 13846, 725685)])