lista = [177313793519, 15151599263944, 862842, 5588463597, 20223939243182, 334639, 60756668356639, 22242033, 64379375, 71604440938099, 19151111209160, 84153191, 28464813222042, 95572448338062, 7919, 31285757956275, 28825582, 5733, 669784429362, 427364, 26791119, 7915, 1315598831, 31959317393591, 751731427784, 519179, 99808691979195, 519524, 975797, 4017914633, 33688855792284, 4666, 28714480, 204426, 3975, 4655572895, 8280359186, 44332266991193, 334419, 881511662268, 8840592624, 356293175788, 4491, 31621324317117, 971979596448, 6088622028, 829762, 3724, 84628828, 2688972453, 95822288, 514419, 5988262653, 577528, 64592453996659, 8680468495, 66799155201784, 8453, 88247757953140, 1388956020, 8220, 843784736635, 5926, 796873483371, 53202695, 4844483353, 51621959992413, 60958882, 223944202859, 9717932659, 4044775535, 468620, 667717604895, 2844, 353119, 935395, 60261919377773, 919359404837, 6082, 158660, 224668958642, 774075, 9931, 4611736055, 3513247153, 8497, 604235, 4657995393, 6446, 776095799326, 6093, 608497821577, 881366, 662491244455, 9564, 2497, 91196433287142, 53864495, 66596075, 31642815759920, 5139959184, 7555117579, 75197353938686, 71848611, 282859, 17625395, 974466, 887940, 336831468428, 597362682895, 1148, 68952677824057, 80136213737795, 8866888855, 8062443560, 596668249931, 774659, 93688264, 9119, 17426840281135, 71718822425599, 48664497645184, 75641966, 57804822865182, 642222372859, 75954024, 48687546, 575713979940, 628680, 15956628, 1333686055, 71628640376444, 60426488911935, 7968402631, 86201999956451, 935360447597, 86665771, 9351241553, 88863362, 538828448464, 9779392660, 866855, 1728118011, 13625162978662, 807162224222, 64353757, 4226, 71687746, 281322466077, 3742979320, 661595, 9933339586, 15392448208848, 8680, 48628828112873, 9551, 37372097735742, 2479, 13516291681346, 265973684048, 798679995962, 845568396466, 15608695, 9159, 7320201577, 392297447315, 208857, 60201591468024, 139195756457, 868479, 11462259171984, 579191, 535579809386, 8284174673, 595580664633, 46152848203153, 1786443964, 39951786, 68934417, 664262, 57935922, 626099, 82245986356217, 4211374484, 51715744, 5317, 1360199322, 31379515, 19885553, 4655918213, 8015, 35226091441548, 576219399531, 9724, 80992268913755, 99333955, 6828265137, 828695, 7946661786, 57154211447157, 97911948, 9982974435, 2873118464, 91971722338097, 758248, 2460, 599533, 401751, 711720, 6077, 19776060667157, 268619409524, 4053, 429140, 73469326, 40222415, 97484259337317, 714084, 623579191537, 395797246660, 485964, 202468, 99487135463339, 91824848, 24486828241595, 17195920176680, 193924176424, 8884, 883977134680, 4211, 11712026423117, 5922, 601891, 71486679, 267357, 37374879242671, 885180, 685779, 8839, 979917, 9566669982, 19939748317946, 868055608488, 976448951375, 828817, 48533740, 937351484033, 8471286666, 2255, 282213, 9117, 662657202620, 881324, 9353407399, 888251, 71577182397119, 1919266462, 2491285564, 44574266, 598691, 7399462428, 974655, 55596864, 51793779157922, 46667384, 1522, 97868820, 28356233, 8866626086, 4675, 9719826880, 71398044, 717155573993, 62152048442860, 7368484224, 77791315, 194880223168, 60883393, 735599, 48596279, 868688, 332691, 683915, 48916811845144, 22154642804442, 5720754471, 19809793973159, 869988779588, 15533393403144, 649364, 357973973133, 202877465340, 2686719391, 422648446851, 4655, 91517320, 286684803779, 15206040889733, 6477738017, 8013]