coefsvec=[[12, 3], [44, 7], [108, 11], [176, 13], [256, 17], [332, 19], [816, 29], [2124, 47], [2736, 53], [4428, 67], [4972, 71], [6092, 79], [7872, 89], [9216, 97], [10032, 101], [11952, 109], [18624, 137], [22192, 149], [22700, 151], [24368, 157], [27948, 167], [31756, 179], [32432, 181], [36172, 191], [36864, 193], [39852, 199], [44172, 211], [51084, 227], [52016, 229], [53952, 233], [56652, 239], [66048, 257], [68716, 263], [78528, 281], [85296, 293], [96492, 311], [98496, 313], [100656, 317], [109548, 331], [120684, 347], [146124, 383], [156848, 397], [176688, 421], [191852, 439], [209088, 457], [214092, 463], [229452, 479], [248652, 499], [253356, 503], [258352, 509], [270528, 521], [298508, 547], [309168, 557], [316044, 563], [325292, 571], [332288, 577], [344044, 587], [352512, 593], [361152, 601], [411648, 641], [412364, 643], [425904, 653], [432972, 659], [452096, 673], [465196, 683], [476108, 691], [501296, 709], [515532, 719], [527148, 727], [562700, 751], [572336, 757], [596784, 773], [656064, 809], [675756, 823], [684076, 827], [704044, 839], [778572, 883], [785004, 887], [843372, 919], [861696, 929], [877248, 937], [933548, 967], [941868, 971], [954624, 977], [981900, 991], [992816, 997], [1024432, 1013], [1037676, 1019], [1060908, 1031], [1077516, 1039], [1099456, 1049], [1102572, 1051], [1127916, 1063], [1141424, 1069], [1192496, 1093], [1272512, 1129], [1322892, 1151], [1350252, 1163], [1440512, 1201], [1469744, 1213], [1479168, 1217], [1493676, 1223], [1530288, 1237], [1559552, 1249], [1582956, 1259], [1628976, 1277], [1643532, 1283], [1679616, 1297], [1692592, 1301], [1737772, 1319], [1759244, 1327], [1866156, 1367], [1906992, 1381], [1982464, 1409], [2027084, 1423], [2039472, 1429], [2092716, 1447], [2126412, 1459], [2198124, 1483], [2208844, 1487], [2214656, 1489], [2226864, 1493], [2280108, 1511], [2319372, 1523], [2341292, 1531], [2377836, 1543], [2469132, 1571], [2600112, 1613], [2626992, 1621], [2645228, 1627], [2680368, 1637], [2743488, 1657], [2776524, 1667], [2784816, 1669], [2865456, 1693], [2921136, 1709], [3000624, 1733], [3027632, 1741], [3154176, 1777], [3193324, 1787], [3197232, 1789], [3240128, 1801], [3281100, 1811], [3319692, 1823], [3348972, 1831], [3483756, 1867], [3499788, 1871], [3506432, 1873], [3526956, 1879], [3565056, 1889], [3612592, 1901], [3658944, 1913], [3733424, 1933], [3796272, 1949], [3803148, 1951], [3914284, 1979], [3947724, 1987], [3991216, 1997], [4008204, 2003], [4160172, 2039], [4210992, 2053], [4255372, 2063], [4278192, 2069], [4465152, 2113], [4530432, 2129], [4588236, 2143], [4673792, 2161], [4750412, 2179], [4849452, 2203], [4869324, 2207], [4935600, 2221], [5027916, 2243], [5135724, 2267], [5146416, 2269], [5204672, 2281], [5254832, 2293], [5326896, 2309], [5339628, 2311], [5523148, 2351], [5624588, 2371], [5665968, 2381], [5702576, 2389], [5721792, 2393], [5954752, 2441], [5982988, 2447], [6084044, 2467], [6113984, 2473], [6132144, 2477], [6402252, 2531], [6445676, 2539], [6492592, 2549], [6533936, 2557], [6809856, 2609], [6843584, 2617], [6864432, 2621], [7065932, 2659], [7132428, 2671], [7163568, 2677], [7214604, 2687], [7225856, 2689], [7247664, 2693], [7285932, 2699], [7358144, 2713], [7396236, 2719], [7507888, 2741], [7573504, 2753], [7706304, 2777], [7789932, 2791], [7840512, 2801], [7853516, 2803], [8080492, 2843], [8124300, 2851], [8157888, 2857], [8329068, 2887], [8388864, 2897], [8504624, 2917], [8633644, 2939], [8780172, 2963], [8810176, 2969], [8823212, 2971], [8988972, 2999], [9108396, 3019], [9132556, 3023], [9217328, 3037], [9242112, 3041], [9291456, 3049], [9364400, 3061], [9536256, 3089], [9668912, 3109], [9722124, 3119], [10001772, 3163], [10040832, 3169], [10114992, 3181], [10160396, 3187], [10179628, 3191], [10297536, 3209], [10342656, 3217], [10564812, 3251], [10578096, 3253], [10877004, 3299], [10931948, 3307], [11173964, 3343], [11203404, 3347], [11282892, 3359], [11377584, 3373], [11487792, 3389], [11493068, 3391], [11788992, 3433], [11948544, 3457], [11971632, 3461], [11987244, 3463], [12180492, 3491], [12239532, 3499], [12325100, 3511], [12449984, 3529], [12475056, 3533], [12522444, 3539], [12540848, 3541], [12816432, 3581], [12902592, 3593], [13123884, 3623], [13227696, 3637], [13264172, 3643], [13476588, 3671], [13484736, 3673], [13516848, 3677], [13660928, 3697], [13690800, 3701], [13750832, 3709], [13825836, 3719], [14142208, 3761], [14208192, 3769], [14275084, 3779], [14791724, 3847], [14829228, 3851], [15060672, 3881], [15121152, 3889], [15258636, 3907], [15340464, 3917], [15354956, 3919], [15387916, 3923], [15429312, 3929], [15542892, 3943], [15572268, 3947], [15905712, 3989], [16012800, 4001], [16016652, 4003], [16054764, 4007], [16167600, 4021], [16591552, 4073], [16744496, 4093], [16900812, 4111], [17025676, 4127], [17040384, 4129], [17240256, 4153], [17643200, 4201], [17726412, 4211], [17775808, 4217], [17876272, 4229], [18079536, 4253], [18150192, 4261], [18239628, 4271], [18339756, 4283], [18726444, 4327], [18819212, 4339], [18905904, 4349], [18988848, 4357], [19035756, 4363], [19118256, 4373], [19430592, 4409], [19547952, 4421], [19713728, 4441], [19769804, 4447], [19862208, 4457], [19909836, 4463], [20075008, 4481], [20088972, 4483], [20178096, 4493], [20313836, 4507], [20370944, 4513], [20401456, 4517], [20458284, 4523], [21182636, 4603], [21358512, 4621], [21516876, 4639], [21682944, 4657], [21734636, 4663], [22001100, 4691], [22109196, 4703], [22278400, 4721], [22369472, 4729], [22642092, 4759], [22875212, 4783], [23343692, 4831], [24029676, 4903], [24088752, 4909], [24311628, 4931], [24324656, 4933], [24364224, 4937], [24662124, 4967], [24720816, 4973], [24866028, 4987], [24980972, 4999], [25082112, 5009], [25209648, 5021], [25766064, 5077], [25806528, 5081], [25869708, 5087], [26000556, 5099], [26019248, 5101], [26133696, 5113], [26208716, 5119], [26486316, 5147], [26543616, 5153], [26818412, 5179], [27355212, 5231], [27375872, 5233], [27424944, 5237], [27671472, 5261], [28127404, 5303], [28328684, 5323], [28437424, 5333], [28585548, 5347], [29074176, 5393], [29138476, 5399], [29355372, 5419], [29485868, 5431], [29601792, 5441], [29988144, 5477], [30009132, 5479], [30055852, 5483], [30250032, 5501], [30316044, 5507], [30478592, 5521], [30874544, 5557], [30942572, 5563], [31004672, 5569], [31051056, 5573], [31250412, 5591], [31607852, 5623], [31787244, 5639], [31819968, 5641], [31879116, 5647], [31937292, 5651], [32131632, 5669], [32404272, 5693], [32615052, 5711], [32901824, 5737], [32971532, 5743], [33719436, 5807], [34103052, 5839], [34199232, 5849], [34234668, 5851], [34292736, 5857], [34447536, 5869], [34773184, 5897], [35078796, 5923], [35272012, 5939], [36628272, 6053], [36943884, 6079], [37464768, 6121], [37579212, 6131], [37612976, 6133], [37727052, 6143], [37991052, 6163], [38410416, 6197], [38467692, 6203], [38638784, 6217], [38689968, 6221], [38793392, 6229], [39015404, 6247], [39515148, 6287], [39679596, 6299], [39710000, 6301], [39818988, 6311], [39905968, 6317], [40049856, 6329], [40235756, 6343], [40450752, 6361], [40528844, 6367], [40680684, 6379], [40808112, 6389], [41577216, 6449], [41602572, 6451], [41990400, 6481], [42121068, 6491], [42867788, 6547], [42944192, 6553], [43082316, 6563], [43165292, 6571], [43243776, 6577], [43639436, 6607], [44256304, 6653], [44336652, 6659], [44367152, 6661], [44747776, 6689], [45001136, 6709], [45373696, 6737], [45942252, 6779], [46110828, 6791], [46152896, 6793], [46277004, 6803], [46555884, 6823], [46689024, 6833], [46786752, 6841], [47189424, 6869], [47202732, 6871], [47586636, 6899], [47694636, 6907], [47834928, 6917], [48414732, 6959], [48533868, 6967], [48666624, 6977], [48753324, 6983], [48944304, 6997], [49554252, 7039], [49956912, 7069], [50105772, 7079], [50694912, 7121], [50804076, 7127], [51140172, 7151], [51642124, 7187], [52013744, 7213], [52106252, 7219], [52253232, 7229], [52447532, 7243], [53029836, 7283], [53423792, 7309], [53775152, 7333], [54037292, 7351], [54287552, 7369], [54654464, 7393], [55256256, 7433], [55502508, 7451], [55630476, 7459], [55891376, 7477], [55972032, 7481], [56088576, 7489], [56507184, 7517], [56692416, 7529], [56795904, 7537], [56851632, 7541], [56943468, 7547], [57126252, 7559], [57175232, 7561], [57335984, 7573], [57610412, 7591], [57877228, 7607], [58340396, 7639], [58422636, 7643], [58875072, 7673], [59007488, 7681], [59136300, 7691], [59634284, 7723], [59694604, 7727], [60728064, 7793], [61093056, 7817], [61661104, 7853], [62077676, 7879], [62131756, 7883], [62412592, 7901], [62522508, 7907], [62696524, 7919], [62830188, 7927], [62980096, 7937], [63218700, 7951], [64128192, 8009], [64274688, 8017], [64622892, 8039], [64858032, 8053], [65422016, 8089], [65610032, 8101], [65785548, 8111], [66379788, 8147], [66753900, 8171], [67538412, 8219], [68262444, 8263], [68363696, 8269], [68758064, 8293], [68823744, 8297], [69069548, 8311], [69157424, 8317], [69358784, 8329], [69764096, 8353], [70186176, 8377], [70872524, 8419], [71040432, 8429], [71068428, 8431], [71269676, 8443], [71572400, 8461], [72266928, 8501], [72479232, 8513], [72593600, 8521], [72900972, 8539], [72970764, 8543], [73316556, 8563], [73623600, 8581], [73891248, 8597], [73930604, 8599], [74338956, 8623], [74409676, 8627], [74443952, 8629], [75051052, 8663], [75278384, 8677], [75352768, 8681], [75481344, 8689], [75668652, 8699], [75796236, 8707], [76031372, 8719], [76496748, 8747], [76738752, 8761], [77501196, 8803], [77806512, 8821], [78080304, 8837], [78122412, 8839], [78291712, 8849], [78547212, 8863], [78613644, 8867], [79602732, 8923], [79935152, 8941], [80103148, 8951], [81010368, 9001], [81111564, 9007], [81230256, 9013], [81876672, 9049], [82197356, 9067], [82636812, 9091], [82959536, 9109], [83479296, 9137], [83849264, 9157], [84127152, 9173], [84283952, 9181], [84387596, 9187], [84634956, 9199], [84710604, 9203], [85341612, 9239], [86055728, 9277], [86126592, 9281], [86155532, 9283], [86341296, 9293], [86851116, 9319], [87161024, 9337], [87252528, 9341], [87909376, 9377], [88401836, 9403], [88585776, 9413], [88701612, 9419], [88963776, 9433], [89052208, 9437], [90180288, 9497], [90973644, 9539], [91126508, 9547], [91891404, 9587], [92164608, 9601], [92410544, 9613], [92583084, 9623], [92709936, 9629], [93088512, 9649], [93316400, 9661], [93667212, 9679], [93863616, 9689], [94828844, 9739], [94927372, 9743], [95429312, 9769], [95765804, 9787], [96238412, 9811], [96603696, 9829], [96674496, 9833], [97026732, 9851], [97145344, 9857], [97180236, 9859], [97755468, 9887], [98130636, 9907], [98565312, 9929], [98809008, 9941], [98968112, 9949], [100134828, 10007], [100799532, 10039], [101334156, 10067], [101381552, 10069], [101566092, 10079], [101851056, 10093], [101975436, 10099], [102052716, 10103], [102658224, 10133], [102783276, 10139], [102836528, 10141], [103032300, 10151], [103633200, 10181], [104494284, 10223], [104902092, 10243], [104990316, 10247], [105103792, 10253], [105392556, 10267], [106135436, 10303], [106366144, 10313], [106502400, 10321], [106982956, 10343], [108118412, 10399], [108701548, 10427], [108766512, 10429], [108851712, 10433], [109749168, 10477], [110214732, 10499], [110502656, 10513], [110885900, 10531], [111482316, 10559], [111651308, 10567], [112125744, 10589], [112282416, 10597], [112497036, 10607], [112634544, 10613], [112997100, 10631], [113550336, 10657], [113679596, 10663], [113784364, 10667], [114198284, 10687], [114980492, 10723], [115093184, 10729], [115308172, 10739], [115613696, 10753], [115997132, 10771], [116383536, 10789], [117294732, 10831], [117442224, 10837], [117777456, 10853], [117909612, 10859], [118585536, 10889], [118593068, 10891], [118856492, 10903], [118984752, 10909], [120398896, 10973], [121048236, 11003], [122253568, 11057], [122282892, 11059], [122833196, 11083], [122899596, 11087], [123567024, 11117], [124278192, 11149], [124503276, 11159], [124770700, 11171], [126594252, 11251], [126799152, 11261], [127394604, 11287], [127658252, 11299], [128331776, 11329], [128822892, 11351], [129246912, 11369], [129551276, 11383], [130221900, 11411], [131498924, 11467], [131836716, 11483], [132023628, 11491], [132186816, 11497], [132849644, 11527], [133357104, 11549], [133418700, 11551], [134051052, 11579], [134469808, 11597], [134933504, 11617], [135305472, 11633], [135899328, 11657], [136843404, 11699], [137315052, 11719], [137879564, 11743], [138727116, 11779], [138987696, 11789], [139241152, 11801], [139714992, 11821], [139855244, 11827], [140738796, 11863], [141282828, 11887], [141530304, 11897], [141657676, 11903], [141823792, 11909], [142868736, 11953], [142995564, 11959], [143274496, 11969], [143692044, 11987], [144144684, 12007], [144874544, 12037], [144977088, 12041], [145018476, 12043], [145697068, 12071], [145748672, 12073], [146419248, 12101], [146557548, 12107], [146623664, 12109], [146870124, 12119], [147437964, 12143], [147604656, 12149], [147920972, 12163], [148889196, 12203], [149089100, 12211], [150114096, 12253], [150844608, 12281], [151027712, 12289], [151995072, 12329], [152441388, 12347], [153217772, 12379], [153772800, 12401], [153959616, 12409], [154659504, 12437], [155006732, 12451], [155155136, 12457], [155700684, 12479], [156014892, 12491], [156502412, 12511], [156650544, 12517], [156910476, 12527], [157201644, 12539], [157574336, 12553], [158766272, 12601], [159039948, 12611], [159066416, 12613], [159771648, 12641], [159921708, 12647], [161198784, 12697], [161341452, 12703], [161598144, 12713], [161831168, 12721], [162304076, 12739], [162727088, 12757], [162868652, 12763], [163335600, 12781], [163795532, 12799], [164073664, 12809], [164401072, 12821], [166101696, 12889], [166217776, 12893], [167478448, 12941], [167791296, 12953], [167939532, 12959], [168159788, 12967], [168279984, 12973], [168544492, 12983], [169069676, 13003], [169259264, 13009], [170271936, 13049], [171417392, 13093], [171683212, 13103], [171821232, 13109], [172302828, 13127], [172818284, 13147], [173777292, 13183], [173870796, 13187], [174675456, 13217], [174720524, 13219], [174980016, 13229], [175511552, 13249], [175988556, 13267], [176629932, 13291], [176783616, 13297], [177217536, 13313], [177718668, 13331], [177849024, 13337], [177921452, 13339], [179073072, 13381], [180110512, 13421], [180658688, 13441], [180920172, 13451], [181238892, 13463], [181609776, 13477], [182589632, 13513], [182872332, 13523], [183231488, 13537], [184308928, 13577], [184868144, 13597], [185450892, 13619], [185712876, 13627], [187093516, 13679], [187147008, 13681], [187322796, 13687], [187447852, 13691], [187582464, 13697], [187909552, 13709], [188000012, 13711], [188248768, 13721], [188323052, 13723], [188462592, 13729], [189241648, 13757], [189320652, 13759], [189418636, 13763], [190109232, 13789], [191218992, 13829], [191302700, 13831], [191564032, 13841], [192434432, 13873], [192544944, 13877], [193546944, 13913], [193791488, 13921], [194114736, 13933], [195080908, 13967], [196270272, 14009], [196316012, 14011], [196804784, 14029], [196905216, 14033], [197410188, 14051], [197571264, 14057], [198416748, 14087], [199034348, 14107], [200468172, 14159], [200880432, 14173], [201533616, 14197], [202208688, 14221], [203011776, 14249], [203068332, 14251], [203933888, 14281], [204554892, 14303], [205075200, 14321], [205120332, 14323], [205825388, 14347], [206464512, 14369], [207892172, 14419], [208712908, 14447], [208746752, 14449], [209114928, 14461], [209633292, 14479], [210348332, 14503], [211179056, 14533], [211470732, 14543], [211646896, 14549], [211995648, 14561], [212931072, 14593], [216449216, 14713], [216983852, 14731], [217298352, 14741], [217452204, 14747], [217622016, 14753], [218066508, 14767], [218152972, 14771], [218425196, 14779], [219415344, 14813], [219840044, 14827], [219969228, 14831], [221061296, 14869], [221915904, 14897], [223152556, 14939], [223504812, 14951], [225380144, 15013], [225517248, 15017], [226563504, 15053], [226803632, 15061], [227197952, 15073], [227286064, 15077], [227741900, 15091], [228019248, 15101], [228191436, 15107], [230192176, 15173], [230615948, 15187], [230985036, 15199], [231539456, 15217], [232032256, 15233], [232286400, 15241], [232810092, 15259], [232952844, 15263], [233155632, 15269], [233186348, 15271], [233662188, 15287], [234029004, 15299], [234273644, 15307], [234654572, 15319], [235010252, 15331], [235595952, 15349], [235948032, 15361], [237161152, 15401], [237578416, 15413], [237962828, 15427], [238515916, 15443], [238706732, 15451], [240579308, 15511], [241060204, 15527], [241803148, 15551], [242387712, 15569], [242834636, 15583], [243563436, 15607], [244683116, 15643], [244823308, 15647], [244872704, 15649], [245818892, 15679], [247336844, 15727], [247432908, 15731], [247522736, 15733], [247632064, 15737], [248377600, 15761], [248763184, 15773], [249346572, 15791], [249517488, 15797], [249901056, 15809], [250341516, 15823], [252180672, 15881], [252429056, 15889], [252811568, 15901], [253425356, 15919], [253534284, 15923], [253981184, 15937], [255093388, 15971], [255131696, 15973], [256012800, 16001], [256208236, 16007], [257798336, 16057], [257925168, 16061], [258186032, 16069], [258761196, 16087], [258935532, 16091], [260092876, 16127], [260435052, 16139], [260506800, 16141], [261904556, 16183], [262074672, 16189], [262980288, 16217], [263154252, 16223], [263364912, 16229], [263998656, 16249], [264181296, 16253], [265743792, 16301], [266739632, 16333], [268321328, 16381], [269288492, 16411], [269497856, 16417], [269839468, 16427], [270531468, 16447], [270691632, 16453], [271986864, 16493], [273193216, 16529], [273779916, 16547], [273971904, 16553], [274275072, 16561], [274434156, 16567], [276159276, 16619], [276571692, 16631], [276633792, 16633], [277177536, 16649], [277426944, 16657], [277586352, 16661], [277968384, 16673], [278623664, 16693], [278852972, 16699], [280241712, 16741], [280475948, 16747], [280975596, 16763], [282979884, 16823], [283193136, 16829], [284919372, 16879], [285233344, 16889], [285681132, 16903], [286287552, 16921], [286517324, 16927], [287716172, 16963], [288334512, 16981], [288525996, 16987], [288732672, 16993], [289697328, 17021], [289899468, 17027], [289953072, 17029], [290380032, 17041], [290777904, 17053], [293196684, 17123], [294671564, 17167], [295513772, 17191], [295929612, 17203], [296046636, 17207], [296118464, 17209], [296877900, 17231], [297152172, 17239], [298944172, 17291], [299224332, 17299], [299849264, 17317], [300019392, 17321], [301929984, 17377], [302275884, 17387], [302781632, 17401], [303418476, 17419], [303806700, 17431], [304432832, 17449], [305433904, 17477], [305662956, 17483], [306920652, 17519], [308010188, 17551], [310535532, 17623], [310705644, 17627], [311737536, 17657], [311832812, 17659], [312656012, 17683], [314307072, 17729], [314921868, 17747], [316252012, 17783], [316510092, 17791], [317054988, 17807], [319054572, 17863], [320063052, 17891], [320492556, 17903], [320772332, 17911], [321218892, 17923], [321413312, 17929], [321816844, 17939], [322920972, 17971], [323165376, 17977], [323524044, 17987], [324455472, 18013], [325563692, 18043], [325667916, 18047], [326129452, 18059], [328322476, 18119], [328783536, 18133], [329359152, 18149], [330105024, 18169], [330882828, 18191], [331649100, 18211], [331833024, 18217], [332086284, 18223], [332406976, 18233], [333077292, 18251], [333282048, 18257], [333750576, 18269], [334469376, 18289], [334929200, 18301], [335335616, 18313], [336367152, 18341], [336796416, 18353], [337517452, 18371], [337750956, 18379], [338432816, 18397], [339743232, 18433], [339962732, 18439], [340110252, 18443], [340634304, 18457], [340791600, 18461], [342324012, 18503], [342890928, 18517], [343012032, 18521], [343657452, 18539], [345465388, 18587], [346558656, 18617], [348202800, 18661], [348870572, 18679], [350160576, 18713], [350860332, 18731], [351272364, 18743], [351492912, 18749], [353140416, 18793], [353289904, 18797], [357682176, 18913], [359409996, 18959], [361306112, 19009], [361520944, 19013], [362198700, 19031], [362370096, 19037], [362957612, 19051], [363971052, 19079], [364281228, 19087], [365574400, 19121], [366342192, 19141], [367895728, 19181], [368873964, 19207], [370880364, 19259], [371182284, 19267], [371410112, 19273], [372028096, 19289], [373735472, 19333], [375564684, 19379], [375589808, 19381], [375821996, 19387], [377037504, 19417], [377147952, 19421], [377283276, 19423], [377384268, 19427], [377913600, 19441], [378213164, 19447], [378816876, 19463], [379046832, 19469], [379823616, 19489], [380314800, 19501], [381425132, 19531], [381905964, 19543], [382989132, 19571], [383458956, 19583], [384474816, 19609], [386515632, 19661], [387583596, 19687], [387940608, 19697], [388027404, 19699], [388405552, 19709], [389144844, 19727], [390098412, 19751], [390402764, 19759], [391098368, 19777], [393658368, 19841], [394468272, 19861], [395654732, 19891], [396490944, 19913], [396790092, 19919], [397456896, 19937], [398423232, 19961], [398892336, 19973], [399120492, 19979], [399601452, 19991], [399736512, 19993], [399874864, 19997]];