coefsvec=[[5,2], [20, 5], [180, 13], [260, 17], [360, 19], [500, 23], [800, 29], [900, 31], [1800, 43], [3380, 59], [3600, 61], [6120, 79], [7940, 89], [9360, 97], [10440, 103], [11700, 109], [12560, 113], [17000, 131], [26280, 163], [27560, 167], [31940, 179], [36500, 191], [36900, 193], [39780, 199], [51140, 227], [56900, 239], [57600, 241], [62600, 251], [65600, 257], [76320, 277], [78800, 281], [80100, 283], [96200, 311], [97380, 313], [108900, 331], [120740, 347], [124100,353], [146180, 383], [150800, 389], [160100, 401], [167040, 409], [177300, 421], [185000, 431], [192420, 439], [201380, 449], [208260,457], [211700, 461], [214740, 463], [217940, 467], [228500, 479], [236520, 487], [249300, 499], [252200, 503], [272520, 523], [291600,541], [298260, 547], [309920, 557], [316520, 563], [324560, 569], [333540, 577], [343880, 587], [367560, 607], [397800, 631], [412740,643], [417320, 647], [427040, 653], [436500, 661], [467240, 683], [490400, 701], [501300, 709], [527400, 727], [571680, 757], [590400,769], [633680, 797], [654800, 809], [682340, 827], [686160, 829], [726480, 853], [733220, 857], [736200, 859], [779220, 883], [820980,907], [830600, 911], [842760, 919], [896360, 947], [935460, 967], [953600, 977], [981000, 991], [994320, 997], [1024340, 1013], [1036520, 1019], [1041300, 1021], [1061300, 1031], [1098320, 1049], [1103400, 1051], [1179540, 1087], [1188500, 1091], [1193760, 1093], [1203920, 1097], [1260180, 1123], [1276740, 1129], [1330020, 1153], [1372500, 1171], [1440900, 1201], [1471860, 1213], [1493300, 1223], [1508660, 1229], [1629200, 1277], [1659620, 1289], [1679940, 1297], [1690100, 1301], [1698120, 1303], [1739240, 1319], [1758600, 1327], [1852100, 1361], [1870580, 1367], [2022120, 1423], [2039220, 1429], [2107400, 1451], [2226080, 1493], [2245160, 1499], [2285000, 1511], [2318420, 1523], [2341800, 1531], [2396340, 1549], [2430500, 1559], [2452500, 1567], [2467400, 1571], [2502980, 1583], [2547540, 1597], [2585700, 1609], [2599220, 1613], [2742480, 1657], [2762820, 1663], [2779400, 1667], [2879120, 1697], [2963300, 1721], [2999840, 1733], [3028500, 1741], [3050280, 1747], [3070800, 1753], [3090600, 1759], [3196980, 1789], [3277700, 1811], [3352500, 1831], [3487140, 1867], [3504960, 1873], [3526920, 1879], [3565700, 1889], [3610400, 1901], [3633320, 1907], [3916580, 1979], [3972420, 1993], [4009160, 2003], [4041000, 2011], [4064400, 2017], [4104680, 2027], [4115700, 2029], [4210740, 2053], [4351460, 2087], [4364100, 2089], [4453700, 2111], [4528580, 2129], [4540500, 2131], [4581200, 2141], [4666500, 2161], [4849380, 2203], [4867220, 2207], [5000180, 2237], [5011560, 2239], [5027240, 2243], [5063400, 2251], [5199300, 2281], [5328020, 2309], [5339700, 2311], [5438420, 2333], [5468360, 2339], [5522600, 2351], [5666900, 2381], [5674500, 2383], [5754500, 2399], [5808200, 2411], [5866280, 2423], [5936400, 2437], [5989640, 2447], [6042440, 2459], [6112080, 2473], [6133280, 2477], [6261300, 2503], [6358500, 2521], [6405800, 2531], [6441480, 2539], [6510600, 2551], [6810500, 2609], [6866000, 2621], [6927680, 2633], [7007400, 2647], [7069320, 2659], [7161300, 2677], [7193160, 2683], [7224200, 2687], [7252640, 2693], [7279460, 2699], [7324740, 2707], [7391880, 2719], [7579280, 2753], [7652520, 2767], [7706960, 2777], [7776080, 2789], [7822800, 2797], [8085800, 2843], [8126100, 2851], [8159040, 2857], [8432420, 2903], [8458580, 2909], [8503200, 2917], [8990120, 2999], [9060500, 3011], [9109620, 3019], [9299520, 3049], [9481140, 3079], [9535940, 3089], [9734400, 3121], [9835280, 3137], [9998820, 3163], [10026920, 3167], [10040580, 3169], [10152900, 3187], [10354320, 3217], [10368500,3221], [10568900, 3251], [10696500, 3271], [10878740, 3299], [10890000, 3301], [10929780, 3307], [10972260, 3313], [11169000,3343], [11195780, 3347], [11281640, 3359], [11297700, 3361], [11379600, 3373], [11478800, 3389], [11492100, 3391], [11782980,3433], [11888720, 3449], [11971700, 3461], [11985480, 3463], [12190100, 3491], [12362400, 3517], [12446820, 3529], [12478160,3533], [12518600, 3539], [12585780, 3547], [12645140, 3557], [12748500, 3571], [12821300, 3581], [12837780, 3583], [13008420,3607], [13047840, 3613], [13180500, 3631], [13265460, 3643], [13469300, 3671], [13514420, 3677], [13823720, 3719], [13973940,3739], [14138000, 3761], [14207040, 3769], [14284100, 3779], [14382180, 3793], [14410100, 3797], [14468660, 3803], [14689700,3833], [14844960, 3853], [14915300, 3863], [15033780, 3877], [15267240, 3907], [15338900, 3917], [15729300, 3967], [16004900,4001], [16098260, 4013], [16147460, 4019], [16208820, 4027], [16410600, 4051], [16451280, 4057], [16753680, 4093], [16802820,4099], [17024660, 4127], [17040420, 4129], [17128820, 4139], [17273360, 4157], [17291880, 4159], [17643600, 4201], [17896500,4231], [17979200, 4241], [18086900, 4253], [18162000, 4261], [18262980, 4273], [18455940, 4297], [18719460, 4327], [18807620,4337], [18907040, 4349], [19338740, 4397], [19441700, 4409], [19538900, 4421], [19555380, 4423], [19858640, 4457], [19910120,4463], [20104200, 4483], [20415240, 4519], [20697300, 4549], [21002120, 4583], [21181320, 4603], [21511080, 4639], [21563540,4643], [21606020, 4649], [21680640, 4657], [21889160, 4679], [22002500, 4691], [22280000, 4721], [22304340, 4723], [22562600,4751], [22641480, 4759], [22907240, 4787], [22970660, 4793], [23623200, 4861], [23726900, 4871], [23898320, 4889], [24030180,4903], [24195560, 4919], [24430760, 4943], [24726260, 4973], [24861960, 4987], [24922980, 4993], [25020260, 5003], [25087460,5009], [25504100, 5051], [25770960, 5077], [25868180, 5087], [26010900, 5101], [26209800, 5119], [26697960, 5167], [26998560,5197], [27123300, 5209], [27362900, 5231], [27422420, 5237], [27797120, 5273], [28047620, 5297], [28178000, 5309], [28328040,5323], [28432160, 5333], [28581480, 5347], [28622600, 5351], [29009000, 5387], [29230020, 5407], [29335760, 5417], [29363940,5419], [29484900, 5431], [29555280, 5437], [29595200, 5441], [29922500, 5471], [30324500, 5507], [30450260, 5519], [30484800,5521], [30542760, 5527], [30581300, 5531], [30942900, 5563], [31009680, 5569], [31054580, 5573], [31140000, 5581], [31787060,5639], [31810500, 5641], [31896360, 5647], [31948020, 5653], [32013000, 5659], [32126420, 5669], [32286420, 5683], [32402960,5693], [32604500, 5711], [32682260, 5717], [32903460, 5737], [32948000, 5741], [32971140, 5743], [33060240, 5749], [33527700,5791], [33642500, 5801], [33713000, 5807], [33953940, 5827], [34223400, 5851], [34339700, 5861], [34440480, 5869], [34574400,5881], [34771280, 5897], [34833800, 5903], [35270660, 5939], [35780000, 5981], [36077220, 6007], [36122600, 6011], [36338900,6029], [36433440, 6037], [36635540, 6053], [36869220, 6073], [37096200, 6091], [37363940, 6113], [38104820, 6173], [38394260,6197], [38416500, 6199], [38470280, 6203], [38567700, 6211], [38688500, 6221], [38790900, 6229], [39022920, 6247], [39327300,6271], [39389940, 6277], [40058960, 6329], [40424360, 6359], [40688100, 6379], [41230800, 6421], [41603400, 6451], [41839380,6469], [41887460, 6473], [41998500, 6481], [42616080, 6529], [42850440, 6547], [42907400, 6551], [43060040, 6563], [43139300,6569], [43179300, 6571], [43308500, 6581], [43552100, 6599], [44038260, 6637], [44519940, 6673], [44611560, 6679], [44744720,6689], [44756100, 6691], [44916840, 6703], [45137300, 6719], [45725220, 6763], [45954740, 6779], [46116200, 6791], [46140480,6793], [46274600, 6803], [46542600, 6823], [46594760, 6827], [47105540, 6863], [47187380, 6869], [47583080, 6899], [47750600,6911], [47834420, 6917], [48456000, 6961], [48581300, 6971], [48861000, 6991], [49010000, 7001], [49186100, 7013], [49597160,7043], [49972500, 7069], [50523680, 7109], [50694500, 7121], [50794760, 7127], [51237000, 7159], [51724880, 7193], [51928740,7207], [52015860, 7213], [52247120, 7229], [52362000, 7237], [52504520, 7247], [53030660, 7283], [53231940, 7297], [53378120,7307], [53416080, 7309], [53604900, 7321], [53729300, 7331], [54003920, 7349], [54294480, 7369], [54997380, 7417], [55504100,7451], [55599680, 7457], [55642500, 7459], [56047940, 7487], [56083140, 7489], [56494100, 7517], [56682020, 7529], [57161700,7561], [57400400, 7577], [57486980, 7583], [57622500, 7591], [57794760, 7603], [57855080, 7607], [58339620, 7639], [58880900,7673], [58982400, 7681], [59138600, 7691], [59693780, 7727], [59911200, 7741], [60094080, 7753], [60155600, 7757], [60673680,7789], [60719360, 7793], [61283060, 7829], [61891380, 7867], [61968420, 7873], [62069940, 7879], [62149640, 7883], [62435600,7901], [62917200, 7933], [62980160, 7937], [63192020, 7949], [63402660, 7963], [64139300, 8009], [64160100, 8011], [64835280,8053], [65298500, 8081], [65418660, 8089], [65618100, 8101], [65782100, 8111], [65894420, 8117], [65978120, 8123], [66751400,8171], [66892680, 8179], [67090500, 8191], [67371840, 8209], [67535780, 8219], [67737800, 8231], [67767120, 8233], [67848080,8237], [67948520, 8243], [68375700, 8269], [68452880, 8273], [68757840, 8293], [69057000, 8311], [69174900, 8317], [70167780,8377], [70862760, 8419], [70943540, 8423], [71097300, 8431], [71673300, 8467], [72704340, 8527], [72898020, 8539], [73891280,8597], [73926180, 8599], [74341800, 8623], [74408660, 8627], [74455380, 8629], [74657700, 8641], [75043700, 8663], [75284640,8677], [75344900, 8681], [75484260, 8689], [75552980, 8693], [75908160, 8713], [76006440, 8719], [76329360, 8737], [76514420,8747], [76760100, 8761], [77130920, 8783], [77761220, 8819], [77793300, 8821], [78098000, 8837], [78297920, 8849], [78504500,8861], [78559380, 8863], [78618500, 8867], [79068960, 8893], [79602120, 8923], [79938000, 8941], [80438480, 8969], [80464500,8971], [80964020, 8999], [81186500, 9011], [81232020, 9013], [81733700, 9041], [81773640, 9043], [82056200, 9059], [82192680,9067], [83393460, 9133], [83467520, 9137], [83842740, 9157], [83931200, 9161], [84276000, 9181], [84604500, 9199], [85010900,9221], [85152200, 9227], [86118800, 9281], [86352080, 9293], [86676200, 9311], [86855400, 9319], [87166980, 9337], [87252500,9341], [87282180, 9343], [88406820, 9403], [88596980, 9413], [88768800, 9421], [88963200, 9433], [89038580, 9437], [89619080,9467], [90077000, 9491], [90443700, 9511], [90869840, 9533], [91219400, 9551], [92160900, 9601], [92968740, 9643], [93088260,9649], [93633440, 9677], [93672900, 9679], [93861440, 9689], [94718880, 9733], [94828680, 9739], [95023700, 9749], [95652000,9781], [95768100, 9787], [95844200, 9791], [96110180, 9803], [96237000, 9811], [96598800, 9829], [97150340, 9857], [97196040,9859], [97425000, 9871], [97734440, 9887], [98032500, 9901], [98583680, 9929], [98605800, 9931], [99323460, 9967], [99456660,9973], [100132580, 10007], [100173060, 10009], [101364660, 10069], [101568200, 10079], [101855520, 10093], [102004200, 10099], [102055880, 10103], [102684320, 10133], [103024100, 10151], [103388240, 10169], [103553280, 10177], [103658000, 10181], [103878800, 10193], [104901480, 10243], [104987240, 10247], [105409800, 10267], [105473000, 10271], [105515280, 10273], [106100000, 10301], [106144200, 10303], [106506000, 10321], [106718900, 10331], [106862480, 10337], [106962740, 10343], [107952200, 10391], [108119700, 10399], [108744480, 10429], [109244340, 10453], [109328720, 10457], [109454600, 10463], [109748880, 10477], [110515140, 10513], [110881800, 10531], [111471560, 10559], [111677220, 10567], [112275360, 10597], [112364900, 10601], [112629920, 10613], [112912200, 10627], [113201640, 10639], [113430600, 10651], [114190920, 10687], [114282500, 10691], [114705000, 10711], [115608420, 10753], [116225300, 10781], [116381520, 10789], [116597000, 10799], [117642440, 10847], [117930020, 10859], [117954000, 10861], [118428740, 10883], [118614600, 10891], [118985760, 10909], [119602820, 10937], [119644200, 10939], [120052980, 10957], [120693960, 10987], [121046120, 11003], [122236580, 11057], [122531600, 11069], [122548500, 11071], [122817780, 11083], [122899400, 11087], [123480900, 11113], [123565940, 11117], [123610500, 11119], [123899400, 11131], [124506440, 11159], [124546500, 11161], [125362080, 11197], [125712080, 11213], [126382820, 11243], [126816500, 11261], [127193540, 11279], [127374120, 11287], [127644840, 11299], [128062260, 11317], [128822600, 11351], [128874960, 11353], [129552840, 11383], [130224200, 11411], [131042600, 11447], [131878760, 11483], [132001700, 11489], [132874920, 11527], [133360400, 11549], [134073800, 11579], [134245800, 11587], [135318800, 11633], [135862820, 11657], [136329300, 11677], [137593800, 11731], [137904840, 11743], [138742020, 11779], [138828980, 11783], [138970400, 11789], [139268900, 11801], [139720500, 11821], [139865940, 11827], [140716260, 11863], [141536720, 11897], [141811700, 11909], [142249640, 11927], [142386080, 11933], [142857360, 11953], [143014500, 11959], [143248400, 11969], [143280900, 11971], [144180900, 12007], [144257000, 12011], [145010340, 12043], [145167300, 12049], [146330640, 12097], [146435600, 12101], [146555720, 12107], [146703680, 12113], [146867240, 12119], [147577040, 12149], [148757300, 12197], [149504660, 12227], [149774120, 12239], [149840100, 12241], [150112800, 12253], [150504500, 12269], [151002000, 12289], [151304400, 12301], [151832840, 12323], [152018000, 12329], [152325000, 12343], [153100980, 12373], [153190340, 12377], [153760400, 12401], [153959760, 12409], [154059680, 12413], [154662560, 12437], [155010600, 12451], [155900340, 12487], [156000200, 12491], [156514500, 12511], [157255200, 12541], [159012200, 12611], [159215220, 12619], [159673680, 12637], [159770000, 12641], [160228100, 12659], [160530500, 12671], [160996580, 12689], [161188560, 12697], [161597060, 12713], [162369380, 12743], [162717840, 12757], [162881640, 12763], [164378000, 12821], [164909700, 12841], [165178260, 12853], [166103460, 12889], [166224980, 12893], [166360520, 12899], [166570020, 12907], [166670600, 12911], [166875300, 12919], [168122340, 12967], [168307380, 12973], [168475140, 12979], [169000400, 13001], [169165640, 13007], [169232400, 13009], [169941920, 13037], [170111720, 13043], [170631720, 13063], [171424800, 13093], [171686120, 13103], [172136000, 13121], [172293320, 13127], [173157300, 13159], [173626020, 13177], [173870660, 13187], [174694340, 13217], [174997940, 13229], [175299200, 13241], [175789940, 13259], [176656500, 13291], [176788800, 13297], [177862820, 13337], [177905160, 13339], [179046900, 13381], [179536680, 13399], [179850600, 13411], [179991360, 13417], [180904100, 13451], [181225700, 13463], [181875560, 13487], [182211380, 13499], [182590020, 13513], [182855300, 13523], [183240720, 13537], [184308260, 13577], [184861620, 13597], [185832000, 13633], [187922720, 13709], [188240000, 13721], [188460900, 13729], [189064100, 13751], [189298440, 13759], [189936800, 13781], [190388900, 13799], [190642500, 13807], [192441600, 13873], [192547220, 13877], [192715700, 13883], [193383560, 13907], [194049800, 13931], [194961780, 13963], [195053780, 13967], [195945300, 13999], [196235300, 14009], [196794000, 14029], [198344340, 14083], [200172960, 14149], [200297600, 14153], [200849940, 14173], [200960420, 14177], [202209300, 14221], [202872200, 14243], [203063400, 14251], [205074500, 14321], [205237640, 14327], [205639200, 14341], [206460740, 14369], [206961620, 14387], [207374400, 14401], [207559080, 14407], [207665000, 14411], [208718600, 14447], [208760580, 14449], [209099700, 14461], [209952320, 14489], [210803300, 14519], [211180320, 14533], [211481000, 14543], [211678160, 14549], [212010500, 14561], [212053140, 14563], [212869700, 14591], [212956740, 14593], [213756500, 14621], [213987600, 14629], [214099520, 14633], [214289000, 14639], [214802960, 14657], [215200400, 14669], [215564040, 14683], [216447300, 14713], [216981000, 14731], [217296500, 14741], [218192900, 14771], [218522900, 14783], [219396020, 14813], [219981800, 14831], [220335140, 14843], [220554900, 14851], [221058720, 14869], [221363720, 14879], [221644980, 14887], [221760500, 14891], [221898560, 14897], [222886800, 14929], [224461620, 14983], [225492800, 15017], [226573940, 15053], [226826100, 15061], [227172240, 15073], [227310740, 15077], [227467880, 15083], [227740500, 15091], [228012500, 15101], [228921800, 15131], [229159080, 15139], [230614740, 15187], [230812740, 15193], [230983560, 15199], [231854180, 15227], [232827300, 15259], [232928840, 15263], [233694920, 15287], [233747280, 15289], [234037640, 15299], [234466560, 15313], [235053000, 15331], [235574100, 15349], [235973700, 15361], [236299680, 15373], [236450960, 15377], [237978900, 15427], [238470740, 15443], [238716900, 15451], [239031200, 15461], [240139940, 15497], [240560100, 15511], [241057160, 15527], [242051400, 15559], [242401040, 15569], [242859240, 15583], [243368100, 15601], [243963540, 15619], [244234580, 15629], [244718820, 15643], [244859940, 15649], [245553800, 15671], [245943080, 15683], [247326120, 15727], [247433300, 15731], [247505040, 15733], [247691700, 15739], [248000180, 15749], [248598440, 15767], [249324500, 15791], [249554420, 15797], [250148160, 15817], [250348680, 15823], [251485380, 15859], [252176900, 15881], [252409940, 15887], [253547720, 15923], [255047300, 15971], [256019600, 16001], [256227380, 16007], [258000840, 16063], [258318020, 16073], [258769800, 16087], [259082660, 16097], [259295720, 16103], [260047940, 16127], [261870120, 16183], [262006760, 16187], [262098000, 16189], [262196240, 16193], [263168660, 16223], [263407520, 16229], [264032100, 16249], [264584520, 16267], [266287940, 16319], [266931540, 16339], [267261200, 16349], [267932160, 16369], [269310600, 16411], [270060800, 16433], [270476100, 16447], [270605000, 16451], [271788680, 16487], [272874600, 16519], [273770120, 16547], [273971840, 16553], [274248000, 16561], [275763860, 16607], [276173300, 16619], [276558500, 16631], [276623460, 16633], [277966820, 16673], [278622900, 16693], [279827280, 16729], [280231200, 16741], [280467720, 16747], [280891080, 16759], [280966760, 16763], [282586100, 16811], [283187360, 16829], [283653540, 16843], [285242180, 16889], [285612500, 16901], [285701940, 16903], [286489620, 16927], [286627400, 16931], [287718660, 16963], [288334800, 16981], [290126660, 17033], [291618000, 17077], [292387400, 17099], [292632660, 17107], [292990580, 17117], [293196740, 17123], [293642820, 17137], [295226900, 17183], [295497000, 17191], [295918020, 17203], [296046440, 17207], [297806400, 17257], [299020320, 17293], [299222100, 17299], [299988800, 17321], [300448400, 17333], [301048100, 17351], [301303080, 17359], [301942800, 17377], [303387300, 17419], [304467300, 17449], [305413280, 17477], [305662760, 17483], [306543060, 17509], [306880520, 17519], [308016900, 17551], [308635920, 17569], [308798900, 17573], [309088800, 17581], [309635600, 17597], [309690900, 17599], [310675880, 17627], [311735360, 17657], [312169040, 17669], [312582800, 17681], [314282660, 17729], [314583120, 17737], [314921540, 17747], [316202660, 17783], [316414100, 17789], [316485000, 17791], [318249000, 17839], [318626100, 17851], [319092660, 17863], [320069000, 17891], [320495060, 17903], [321132800, 17921], [321199380, 17923], [321772100, 17939], [322489800, 17959], [323188560, 17977], [323552840, 17987], [324462420, 18013], [325470500, 18041], [325560420, 18043], [326207700, 18061], [329153480, 18143], [329400080, 18149], [330110820, 18169], [330516000, 18181], [330938600, 18191], [331201800, 18199], [331833060, 18217], [332048340, 18223], [332408960, 18233], [334898100, 18301], [335161620, 18307], [335384100, 18313], [335929040, 18329], [337373460, 18367], [337496900, 18371], [338452020, 18397], [339004880, 18413], [339972840, 18439], [340116200, 18443], [340652160, 18457], [340797200, 18461], [341514000, 18481], [342853920, 18517], [343068840, 18523], [343670900, 18539], [345443240, 18587], [345667940, 18593], [346571840, 18617], [348195600, 18661], [348571400, 18671], [348876900, 18679], [349319700, 18691], [351839520, 18757], [352388660, 18773], [354871400, 18839], [357158120, 18899], [357672960, 18913], [359407700, 18959], [359938080, 18973], [360185220, 18979], [361006400, 19001], [361461920, 19013], [362157800, 19031], [362427860, 19037], [363604500, 19069], [363768740, 19073], [363977480, 19079], [364275540, 19087], [365591300, 19121], [367872500, 19181], [367949160, 19183], [369030500, 19211], [370872500, 19259], [372506900, 19301], [372800160, 19309], [373203620, 19319], [373767840, 19333], [375312020, 19373], [376476020, 19403], [377009280, 19417], [377248680, 19423], [377410280, 19427], [377606720, 19433], [378186120, 19447], [378579200, 19457], [379316340, 19477], [380258100, 19501], [380485800, 19507], [381453300, 19531], [381821600, 19541], [382307600, 19553], [382580900, 19559], [382991300, 19571], [384003360, 19597], [386578100, 19661], [387932480, 19697], [388014120, 19699], [389176580, 19727], [389590760, 19739], [390211200, 19753], [390555140, 19763], [391095360, 19777], [391730660, 19793], [392097600, 19801], [392528340, 19813], [392829300, 19819], [394452000, 19861], [394663140, 19867], [395533700, 19889], [395644500, 19891], [396732500, 19919], [397473680, 19937], [397924640, 19949], [398421200, 19961], [398541960, 19963], [399689280, 19993], [399853940, 19997]];