coefsvec = [[6, 2], [9, 3], [105, 11], [276, 17], [324, 19], [945, 31], [1296, 37], [1620, 41], [1809, 43], [2121, 47], [3780, 61], [5184, 73], [6129, 79], [7764, 89], [9396, 97], [10320, 101], [12624, 113], [15876, 127], [16980, 131], [18576, 137], [24516, 157], [26649, 163], [36180, 191], [37044, 193], [44145, 211], [52164, 229], [62745, 251], [68769, 263], [71844, 269], [73305, 271], [85344, 293], [94041, 307], [96180, 311], [100356, 317], [110025, 331], [113076, 337], [128169, 359], [134676, 367], [142884, 379], [150864, 389], [167184, 409], [176580, 421], [186624, 433], [195684, 443], [201984, 449], [211680, 461], [217161, 467], [228609, 479], [240705, 491], [252249, 503], [291600, 541], [315969, 563], [322944, 569], [333396, 577], [358449, 599], [360180, 601], [367281, 607], [381456, 617], [383049, 619], [410100, 641], [427524, 653], [434409, 659], [457296, 677], [527796, 727], [536544, 733], [545049, 739], [550644, 743], [563220, 751], [573156, 757], [590004, 769], [596484, 773], [633636, 797], [654864, 809], [678564, 823], [683721, 827], [687204, 829], [702249, 839], [726624, 853], [738369, 859], [775680, 881], [785121, 887], [823716, 907], [829545, 911], [894921, 947], [935361, 967], [941220, 971], [965169, 983], [992736, 997], [1024224, 1013], [1065744, 1033], [1123620, 1061], [1128249, 1063], [1179441, 1087], [1189545, 1091], [1247076, 1117], [1261764, 1123], [1272564, 1129], [1351689, 1163], [1369305, 1171], [1392720, 1181], [1407876, 1187], [1440720, 1201], [1508004, 1229], [1527876, 1237], [1557684, 1249], [1583844, 1259], [1633689, 1279], [1665225, 1291], [1681236, 1297], [1696329, 1303], [1705641, 1307], [1737204, 1319], [1849920, 1361], [1887504, 1373], [1904580, 1381], [1982544, 1409], [2022489, 1423], [2039904, 1429], [2050704, 1433], [2071764, 1439], [2090961, 1447], [2109024, 1453], [2161620, 1471], [2192400, 1481], [2208516, 1487], [2218644, 1489], [2229444, 1493], [2284305, 1511], [2316489, 1523], [2396304, 1549], [2503329, 1583], [2547396, 1597], [2579361, 1607], [2588544, 1609], [2600964, 1613], [2626020, 1621], [2645001, 1627], [2762964, 1663], [2775561, 1667], [2864484, 1693], [2882196, 1697], [2883249, 1699], [2918544, 1709], [2960820, 1721], [2968164, 1723], [3093444, 1759], [3154896, 1777], [3179169, 1783], [3191076, 1787], [3240000, 1801], [3482676, 1867], [3498900, 1871], [3506004, 1873], [3521796, 1877], [3729105, 1931], [3733344, 1933], [3802545, 1951], [3947076, 1987], [3968244, 1993], [3998484, 1999], [4008609, 2003], [4042980, 2011], [4106121, 2027], [4276644, 2069], [4406724, 2099], [4529364, 2129], [4538025, 2131], [4588569, 2143], [4667220, 2161], [4872561, 2207], [4931280, 2221], [5030484, 2243], [5066145, 2251], [5167104, 2273], [5199120, 2281], [5257764, 2293], [5327844, 2309], [5473089, 2339], [5477220, 2341], [5504436, 2347], [5529345, 2351], [5552016, 2357], [5665680, 2381], [5702724, 2389], [5722164, 2393], [5755209, 2399], [5839476, 2417], [5983521, 2447], [6084801, 2467], [6119604, 2473], [6130896, 2477], [6356880, 2521], [6401025, 2531], [6496224, 2549], [6651204, 2579], [6708345, 2591], [6720084, 2593], [6864480, 2621], [7001721, 2647], [7054836, 2657], [7129620, 2671], [7203249, 2683], [7214676, 2687], [7226064, 2689], [7288449, 2699], [7322481, 2707], [7345545, 2711], [7442064, 2729], [7507680, 2741], [7573824, 2753], [7651476, 2767], [7840500, 2801], [7853409, 2803], [8156916, 2857], [8181600, 2861], [8283129, 2879], [8388816, 2897], [8424729, 2903], [8503056, 2917], [8569881, 2927], [8642889, 2939], [8811024, 2969], [8992809, 2999], [9002880, 3001], [9110529, 3019], [9218016, 3037], [9536064, 3089], [9734580, 3121], [9998289, 3163], [10042704, 3169], [10160721, 3187], [10291344, 3209], [10342836, 3217], [10369680, 3221], [10422864, 3229], [10562820, 3251], [10614969, 3259], [11036004, 3323], [11176569, 3343], [11196036, 3347], [11292480, 3361], [11499705, 3391], [11602116, 3407], [11779344, 3433], [11891124, 3449], [11974020, 3461], [11986164, 3463], [12027744, 3469], [12180705, 3491], [12243609, 3499], [12330225, 3511], [12373776, 3517], [12434676, 3527], [12540420, 3541], [12650256, 3557], [12664809, 3559], [12822180, 3581], [12902784, 3593], [13003281, 3607], [13051044, 3613], [13075776, 3617], [13123689, 3623], [13222116, 3637], [13267044, 3643], [13469505, 3671], [13490064, 3673], [13619745, 3691], [13661136, 3697], [13690080, 3701], [13755744, 3709], [13886721, 3727], [13928544, 3733], [13975524, 3739], [14186961, 3767], [14410116, 3797], [14799321, 3847], [15116544, 3889], [15260481, 3907], [15335136, 3917], [15386289, 3923], [15429264, 3929], [15578916, 3947], [16101924, 4013], [16149129, 4019], [16163280, 4021], [16393524, 4049], [16451856, 4057], [16631529, 4079], [16733220, 4091], [16794729, 4099], [17041104, 4129], [17073744, 4133], [17126964, 4139], [17279556, 4157], [17289369, 4159], [17774736, 4217], [17799129, 4219], [17899380, 4231], [18081924, 4253], [18156420, 4261], [18240900, 4271], [18250704, 4273], [18399444, 4289], [18824724, 4339], [19276305, 4391], [19325796, 4397], [19554129, 4423], [19767321, 4447], [19802625, 4451], [19911444, 4463], [20080980, 4481], [20088729, 4483], [20179044, 4493], [20304081, 4507], [20366964, 4513], [20802420, 4561], [20849076, 4567], [21127716, 4597], [21178449, 4603], [21353220, 4621], [21496416, 4637], [21549444, 4643], [21622545, 4651], [21687156, 4657], [21883689, 4679], [22365504, 4729], [22644009, 4759], [22869729, 4783], [22907076, 4787], [22971264, 4793], [23026929, 4799], [23203536, 4817], [23346900, 4831], [23621220, 4861], [23905044, 4889], [24029649, 4903], [24097284, 4909], [24198729, 4919], [24331104, 4933], [24508980, 4951], [24564816, 4957], [24665361, 4967], [24695604, 4969], [24721764, 4973], [24996249, 4999], [25022004, 5003], [25093584, 5009], [25767396, 5077], [25868241, 5087], [26021520, 5101], [26078841, 5107], [26195049, 5119], [26481921, 5147], [26824689, 5179], [26923344, 5189], [27123984, 5209], [27353220, 5231], [27416016, 5237], [27670020, 5261], [27879120, 5281], [28064436, 5297], [28175364, 5309], [28430244, 5333], [28586196, 5347], [28627305, 5351], [29294244, 5413], [29487105, 5431], [29556576, 5437], [29601600, 5441], [29685204, 5449], [29925105, 5471], [30008529, 5479], [30054129, 5483], [30316356, 5507], [30481920, 5521], [30543156, 5527], [30581145, 5531], [30869856, 5557], [31609089, 5623], [31818420, 5641], [31877361, 5647], [31945104, 5653], [31991316, 5657], [32126544, 5669], [32501520, 5701], [32607225, 5711], [33385284, 5779], [33432804, 5783], [33883920, 5821], [33942321, 5827], [34089849, 5839], [34144089, 5843], [34339680, 5861], [34435044, 5869], [34560564, 5879], [34766736, 5897], [35130996, 5927], [35427024, 5953], [36121545, 6011], [36350304, 6029], [36507969, 6043], [36555921, 6047], [36631824, 6053], [36878004, 6073], [36960084, 6079], [37229220, 6101], [37468980, 6121], [37583745, 6131], [37602144, 6133], [37835505, 6151], [37971369, 6163], [38470929, 6203], [38660436, 6217], [38711520, 6221], [39018996, 6247], [39691620, 6301], [39831225, 6311], [40159476, 6337], [40244769, 6343], [40351284, 6353], [40427289, 6359], [40450320, 6361], [40908996, 6397], [41220900, 6421], [41293881, 6427], [41579124, 6449], [41843844, 6469], [41996880, 6481], [42909345, 6551], [43154304, 6569], [43164900, 6571], [43301520, 6581], [44249604, 6653], [44330244, 6659], [44537364, 6673], [44732724, 6689], [44772345, 6691], [44895120, 6701], [44997984, 6709], [46285809, 6803], [46549809, 6823], [46596921, 6827], [46622304, 6829], [46676724, 6833], [46787220, 6841], [47099049, 6863], [47214900, 6871], [47364129, 6883], [47598084, 6899], [47839056, 6917], [48281184, 6949], [48581025, 6971], [48672576, 6977], [48865545, 6991], [48955536, 6997], [49005780, 7001], [49537089, 7039], [49801716, 7057], [50121204, 7079], [50438409, 7103], [51123345, 7151], [51503796, 7177], [51927156, 7207], [51988020, 7211], [52021764, 7213], [52125444, 7219], [52246404, 7229], [52519641, 7247], [52592004, 7253], [53232336, 7297], [54016224, 7349], [54040500, 7351], [54298944, 7369], [54650484, 7393], [55502820, 7451], [56225124, 7499], [56591529, 7523], [56676564, 7529], [56792016, 7537], [57123684, 7559], [57168180, 7561], [57411456, 7577], [57509169, 7583], [58344489, 7639], [58882704, 7673], [59075001, 7687], [59259249, 7699], [59341929, 7703], [59554656, 7717], [59922180, 7741], [60096384, 7753], [60155556, 7757], [60683364, 7789], [60728784, 7793], [61466580, 7841], [61874361, 7867], [61979904, 7873], [62041956, 7877], [62509956, 7907], [62708769, 7919], [62839476, 7927], [63180384, 7949], [63404964, 7963], [63872064, 7993], [64933569, 8059], [65313780, 8081], [65420244, 8089], [65500944, 8093], [65624580, 8101], [65870736, 8117], [65971689, 8123], [66357321, 8147], [66585780, 8161], [66711681, 8167], [67377744, 8209], [67537329, 8219], [67579920, 8221], [67766544, 8233], [68261049, 8263], [68445204, 8273], [68726745, 8291], [68823636, 8297], [69069105, 8311], [69923364, 8363], [70023744, 8369], [70365024, 8389], [71032464, 8429], [71076420, 8431], [71335161, 8447], [72863376, 8537], [72988209, 8543], [73310049, 8563], [73492704, 8573], [73625220, 8581], [73926324, 8599], [74358729, 8623], [74437521, 8627], [75030369, 8663], [75138144, 8669], [75342420, 8681], [75481524, 8689], [76005729, 8719], [76232745, 8731], [76339476, 8737], [76390980, 8741], [76494321, 8747], [76746420, 8761], [77054409, 8779], [77761329, 8819], [77968905, 8831], [78078816, 8837], [78536169, 8863], [79069284, 8893], [79710804, 8929], [80106705, 8951], [80320569, 8963], [80426304, 8969], [80463780, 8971], [81025920, 9001], [81110241, 9007], [81180225, 9011], [81524004, 9029], [82060884, 9059], [82203876, 9067], [82654020, 9091], [82847124, 9103], [82957284, 9109], [83290356, 9127], [83404944, 9133], [83476176, 9137], [83930100, 9161], [84286980, 9181], [84681924, 9203], [85345764, 9239], [85399380, 9241], [86048676, 9277], [86167044, 9283], [86705745, 9311], [86828004, 9319], [86902809, 9323], [87237600, 9341], [87387984, 9349], [87909396, 9377], [88587024, 9413], [88988544, 9433], [89051616, 9437], [89092089, 9439], [89720784, 9473], [90062745, 9491], [90194496, 9497], [90871524, 9533], [90973449, 9539], [91204305, 9551], [91906521, 9587], [92162880, 9601], [92392164, 9613], [92769705, 9631], [92981169, 9643], [93090384, 9649], [93862464, 9689], [94012596, 9697], [94714704, 9733], [95670180, 9781], [95778801, 9787], [95853780, 9791], [96358356, 9817], [96615504, 9829], [96675444, 9833], [96790164, 9839], [97157556, 9857], [97418025, 9871], [97745001, 9887], [98010000, 9901], [98129961, 9907], [98585664, 9929], [98980704, 9949], [99466704, 9973], [100135716, 10007], [100724676, 10037], [101210820, 10061], [102071529, 10103], [102228345, 10111], [102661344, 10133], [102787449, 10139], [103388724, 10169], [103562496, 10177], [103632720, 10181], [103890384, 10193], [104244705, 10211], [104493489, 10223], [104983641, 10247], [106131924, 10303], [106344564, 10313], [106520400, 10321], [106988964, 10343], [108134649, 10399], [108773604, 10429], [109341456, 10457], [109379889, 10459], [109748196, 10477], [109956201, 10487], [110250180, 10501], [110528064, 10513], [110844564, 10529], [111471444, 10559], [111644001, 10567], [112305636, 10597], [113000820, 10631], [113434020, 10651], [113564916, 10657], [114208596, 10687], [114277905, 10691], [114670944, 10709], [114736905, 10711], [115175844, 10733], [115995780, 10771], [116617929, 10799], [117296505, 10831], [117957600, 10861], [118072836, 10867], [118438404, 10883], [118573044, 10889], [120395364, 10973], [120516729, 10979], [120826944, 10993], [121080129, 11003], [122014836, 11047], [122235156, 11057], [122281569, 11059], [123069444, 11093], [123568836, 11117], [123622929, 11119], [124816464, 11173], [124916496, 11177], [125356896, 11197], [125733444, 11213], [127058964, 11273], [127193409, 11279], [127652409, 11299], [128148180, 11321], [128324304, 11329], [128829345, 11351], [128879424, 11353], [129549969, 11383], [129943284, 11399], [130190100, 11411], [130476129, 11423], [130790916, 11437], [130930884, 11443], [131021961, 11447], [131501961, 11467], [132315849, 11503], [132864921, 11527], [134079729, 11579], [134472336, 11597], [134940276, 11617], [135025380, 11621], [136329696, 11677], [136620864, 11689], [136881924, 11699], [136904580, 11701], [137318004, 11719], [137595105, 11731], [137902689, 11743], [138676596, 11777], [138970464, 11789], [139260480, 11801], [139536864, 11813], [139712580, 11821], [140726889, 11863], [141277041, 11887], [141803844, 11909], [142244601, 11927], [142372644, 11933], [143010009, 11959], [143240244, 11969], [143666001, 11987], [144895716, 12037], [145013409, 12043], [145163124, 12049], [146412420, 12101], [146563236, 12107], [146851044, 12119], [147428484, 12143], [147579684, 12149], [147868980, 12161], [147927249, 12163], [148747536, 12197], [149107905, 12211], [149511201, 12227], [149817600, 12241], [150129504, 12253], [150526944, 12269], [150700176, 12277], [150810900, 12281], [151831689, 12323], [152360244, 12343], [153070884, 12373], [153512820, 12391], [153763920, 12401], [153959184, 12409], [154554804, 12433], [155026305, 12451], [155564304, 12473], [155905641, 12487], [156011145, 12491], [156152016, 12497], [156506580, 12511], [156668256, 12517], [157203249, 12539], [157412241, 12547], [157959744, 12569], [158326569, 12583], [158493024, 12589], [158774580, 12601], [159067044, 12613], [159772020, 12641], [159944436, 12647], [160225089, 12659], [160539945, 12671], [161622324, 12713], [161809920, 12721], [162257364, 12739], [162362769, 12743], [162737316, 12757], [162872289, 12763], [163342980, 12781], [163596105, 12791], [163788804, 12799], [164391120, 12821], [164566404, 12829], [166203744, 12893], [166574961, 12907], [166846176, 12917], [166902849, 12919], [166987764, 12923], [167783184, 12953], [168281604, 12973], [169054884, 13003], [169159956, 13007], [169229844, 13009], [169834644, 13033], [171403344, 13093], [172294521, 13127], [172822761, 13147], [172947705, 13151], [173243049, 13163], [173621556, 13177], [173768004, 13183], [173878596, 13187], [175308180, 13241], [175996881, 13267], [176814036, 13297], [177107364, 13309], [177209844, 13313], [177891216, 13337], [178651401, 13367], [179024580, 13381], [180035136, 13417], [180642420, 13441], [181624356, 13477], [181887876, 13487], [182196324, 13499], [183658704, 13553], [184688505, 13591], [185299044, 13613], [185456049, 13619], [185693796, 13627], [185831604, 13633], [186267924, 13649], [186814404, 13669], [187466100, 13691], [187938144, 13709], [188458164, 13729], [189244356, 13757], [189410049, 13763], [190115424, 13789], [190606041, 13807], [191269620, 13831], [191570100, 13841], [192095169, 13859], [192433104, 13873], [192570756, 13877], [192599289, 13879], [192718329, 13883], [193212000, 13901], [193320729, 13903], [194071545, 13931], [194955444, 13963], [195083601, 13967], [195920016, 13997], [195960249, 13999], [196240884, 14009], [196916244, 14033], [197447625, 14051], [197598516, 14057], [198308169, 14083], [200167524, 14149], [200848464, 14173], [201839316, 14207], [202248900, 14221], [203024724, 14249], [203078745, 14251], [205137684, 14323], [205653600, 14341], [205833636, 14347], [206451924, 14369], [206969001, 14387], [207361620, 14401], [207648420, 14411], [208002489, 14423], [208232505, 14431], [209094480, 14461], [209613204, 14479], [209922624, 14489], [210315609, 14503], [210797529, 14519], [211295796, 14537], [211494969, 14543], [212018100, 14561], [213920001, 14627], [214095444, 14633], [214707024, 14653], [214806336, 14657], [216489024, 14713], [216561156, 14717], [217491561, 14747], [217625424, 14753], [217805409, 14759], [218159025, 14771], [218422089, 14779], [219633120, 14821], [219823281, 14827], [219947505, 14831], [220526145, 14851], [221023161, 14867], [221059044, 14869], [221361009, 14879], [221603121, 14887], [221712225, 14891], [222685929, 14923], [223383636, 14947], [224461044, 14983], [226599684, 15053], [226855620, 15061], [227286276, 15077], [227468004, 15083], [227710980, 15091], [228017220, 15101], [228191361, 15107], [228672720, 15121], [229465824, 15149], [230855184, 15193], [230979249, 15199], [231561936, 15217], [231857721, 15227], [232014804, 15233], [233125344, 15269], [233174025, 15271], [234947904, 15329], [235020420, 15331], [235561824, 15349], [235879209, 15359], [236300004, 15373], [236852505, 15391], [237192000, 15401], [237532164, 15413], [238355649, 15439], [238456644, 15443], [239219601, 15467], [240153396, 15497], [241113921, 15527], [241492320, 15541], [242062884, 15559], [242748900, 15581], [242814969, 15583], [243927369, 15619], [244246884, 15629], [244641600, 15641], [244682289, 15643], [244864404, 15649], [245558580, 15671], [245806164, 15679], [247510404, 15733], [247634196, 15737], [247739769, 15739], [248015184, 15749], [248414580, 15761], [248763204, 15773], [249217641, 15787], [249347220, 15791], [249530436, 15797], [249741924, 15803], [250163856, 15817], [250339329, 15823], [252048996, 15877], [252181620, 15881], [252433044, 15889], [253046916, 15907], [253250064, 15913], [253428804, 15919], [253525209, 15923], [255048900, 15971], [255680820, 15991], [257990724, 16063], [258215904, 16069], [258761601, 16087], [259125396, 16097], [259297524, 16103], [260061921, 16127], [260440164, 16139], [260500320, 16141], [262201344, 16193], [263155284, 16223], [263357664, 16229], [264582801, 16267], [265710480, 16301], [266277129, 16319], [266935689, 16339], [269304345, 16411], [269485056, 16417], [270011124, 16433], [270661905, 16451], [270694224, 16453], [271790196, 16487], [272024784, 16493], [272879604, 16519], [273775236, 16547], [274248180, 16561], [274434561, 16567], [274661604, 16573], [275631849, 16603], [275774361, 16607], [276165924, 16619], [276595620, 16631], [277161684, 16649], [277457616, 16657], [277559520, 16661], [277955664, 16673], [278623584, 16693], [280268100, 16741], [280440036, 16747], [280830564, 16759], [282981129, 16823], [283255380, 16831], [285258624, 16889], [286288020, 16921], [287711649, 16963], [288271089, 16979], [289350225, 17011], [289680720, 17021], [290090004, 17033], [290370420, 17041], [292147044, 17093], [292345809, 17099], [292618116, 17107], [293648976, 17137], [295244244, 17183], [295475364, 17189], [296048436, 17207], [296129844, 17209], [297821556, 17257], [299289249, 17299], [299990400, 17321], [300231681, 17327], [301307769, 17359], [302136804, 17383], [302344164, 17389], [303336276, 17417], [303387444, 17419], [303812505, 17431], [304223769, 17443], [305411856, 17477], [305880144, 17489], [306111636, 17497], [306892329, 17519], [311837769, 17659], [312167904, 17669], [313520436, 17707], [314283264, 17729], [314611776, 17737], [316418724, 17789], [316486305, 17791], [317771721, 17827], [318130116, 17837], [319705920, 17881], [320090820, 17891], [320481684, 17903], [320778225, 17911], [321797049, 17939], [322497369, 17959], [323154576, 17977], [325448820, 18041], [325776384, 18049], [326103369, 18059], [326795856, 18077], [328558356, 18127], [328778244, 18133], [329158809, 18143], [330106644, 18169], [330514020, 18181], [330882945, 18191], [332059284, 18223], [332312004, 18229], [332409744, 18233], [333064305, 18251], [333135504, 18253], [334391316, 18287], [334465524, 18289], [334925280, 18301], [335116116, 18307], [335256180, 18311], [335364624, 18313], [337315401, 18367], [337477380, 18371], [338414436, 18397], [338560080, 18401], [339051744, 18413], [339517521, 18427], [339745104, 18433], [340772100, 18461], [341511120, 18481], [342853776, 18517], [343032720, 18521], [343070964, 18523], [343708449, 18539], [343731600, 18541], [345484521, 18587], [347301216, 18637], [348200100, 18661], [348880689, 18679], [349371225, 18691], [350155764, 18713], [350377044, 18719], [350813025, 18731], [351531684, 18749], [352419984, 18773], [353560329, 18803], [354882249, 18839], [356013924, 18869], [357638100, 18911], [357894369, 18919], [358950921, 18947], [361362384, 19009], [361510224, 19013], [362918745, 19051], [363995289, 19079], [365575380, 19121], [366969156, 19157], [367916580, 19181], [367951329, 19183], [369118944, 19213], [369332649, 19219], [370058976, 19237], [370871169, 19259], [371184201, 19267], [371410704, 19273], [373752144, 19333], [375816996, 19387], [376008225, 19391], [376447284, 19403], [377369601, 19427], [377606544, 19433], [377928180, 19441], [378182196, 19447], [378535956, 19457], [379036644, 19469], [379083105, 19471], [379321056, 19477], [380521881, 19507], [381469905, 19531], [381917889, 19543], [383236596, 19577], [383469849, 19583], [387354420, 19681], [388018809, 19699], [388418784, 19709], [388738656, 19717], [389590089, 19739], [390076020, 19751], [390379284, 19759], [390537249, 19763], [391732944, 19793], [392753529, 19819], [394105284, 19853], [394660836, 19867], [395638020, 19891], [396503424, 19913], [397488276, 19937], [397930704, 19949], [398481444, 19963], [398914404, 19973], [399141609, 19979], [399606945, 19991], [399680244, 19993]];