O(lgn) solution(joke)
\nclass Solution {\n    static boolean[] prime;\n    public int primePalindrome(int n) {\n       String str = "2,3,5,7,11,101,131,151,181,191,313,353,373,383,72
```\nclass Solution {\n    static boolean[] prime;\n    public int primePalindrome(int n) {\n       String str = "2,3,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899,100030001,100050001,100060001,100111001,100131001,100161001,100404001,100656001,100707001,100767001,100888001,100999001,101030101,101060101,101141101,101171101,101282101,101292101,101343101,101373101,101414101,101424101,101474101,101595101,101616101,101717101,101777101,101838101,101898101,101919101,101949101,101999101,102040201,102070201,102202201,102232201,102272201,102343201,102383201,102454201,102484201,102515201,102676201,102686201,102707201,102808201,102838201,103000301,103060301,103161301,103212301,103282301,103303301,103323301,103333301,103363301,103464301,103515301,103575301,103696301,103777301,103818301,103828301,103909301,103939301,104000401,104030401,104040401,104111401,104222401,104282401,104333401,104585401,104616401,104787401,104838401,104919401,104949401,105121501,105191501,105202501,105262501,105272501,105313501,105323501,105343501,105575501,105616501,105656501,105757501,105818501,105868501,105929501,106060601,106111601,106131601,106191601,106222601,106272601,106353601,106444601,106464601,106545601,106555601,106717601,106909601,106929601,107000701,107070701,107121701,107232701,107393701,107414701,107424701,107595701,107636701,107646701,107747701,107757701,107828701,107858701,107868701,107888701,107939701,107949701,108070801,108101801,108121801,108151801,108212801,108323801,108373801,108383801,108434801,108464801,108484801,108494801,108505801,108565801,108686801,108707801,108767801,108838801,108919801,108959801,109000901,109101901,109111901,109161901,109333901,109404901,109434901,109444901,109474901,109575901,109656901,109747901,109777901,109797901,109818901,109909901,109929901,110111011,110232011,110252011,110343011,110424011,110505011,110565011,110676011,110747011,110757011,110909011,110949011,110999011,111010111,111020111,111050111,111070111,111181111,111191111,111262111,111272111,111454111,111484111,111515111,111616111,111686111,111757111,111848111,112030211,112060211,112111211,112161211,112171211,112212211,112434211,112494211,112545211,112636211,112878211,112959211,112969211,112989211,113030311,113090311,113111311,113262311,113282311,113474311,113535311,113565311,113616311,113636311,113888311,113939311,114040411,114191411,114232411,114353411,114383411,114484411,114494411,114535411,114727411,114808411,114818411,114848411,114878411,114898411,115000511,115020511,115060511,115111511,115141511,115191511,115212511,115222511,115404511,115464511,115545511,115636511,115737511,115767511,115797511,115828511,115959511,116000611,116010611,116040611,116424611,116505611,116646611,116696611,116757611,116777611,116828611,116868611,116919611,117070711,117101711,117262711,117272711,117323711,117484711,117505711,117515711,117616711,117686711,117757711,117767711,117797711,117818711,117959711,118252811,118272811,118414811,118464811,118525811,118626811,118686811,118696811,118717811,118818811,118848811,118909811,118959811,119010911,119171911,119202911,119343911,119363911,119454911,119585911,119595911,119646911,119676911,119696911,119717911,119787911,119868911,119888911,119969911,120191021,120242021,120434021,120454021,120494021,120535021,120565021,120646021,120808021,120868021,120989021,121080121,121111121,121131121,121161121,121272121,121282121,121393121,121414121,121555121,121747121,121818121,121878121,121939121,121989121,122040221,122232221,122262221,122292221,122333221,122363221,122373221,122393221,122444221,122484221,122535221,122696221,122787221,122858221,122919221,123161321,123292321,123424321,123484321,123494321,123575321,123767321,123838321,123989321,124000421,124080421,124101421,124131421,124252421,124323421,124333421,124434421,124515421,124525421,124626421,124656421,124717421,124737421,124959421,124989421,125000521,125010521,125232521,125252521,125292521,125343521,125474521,125505521,125565521,125606521,125616521,125757521,125838521,125939521,125979521,125999521,126101621,126161621,126181621,126202621,126212621,126323621,126424621,126484621,126535621,126595621,126616621,126676621,126686621,126727621,126737621,126757621,126878621,127060721,127090721,127131721,127212721,127383721,127494721,127545721,127636721,127656721,127686721,127717721,127747721,127828721,127909721,127929721,128070821,128090821,128121821,128181821,128202821,128252821,128262821,128282821,128444821,128474821,128525821,128535821,128595821,128646821,128747821,128787821,128868821,128919821,128939821,129080921,129202921,129292921,129323921,129373921,129484921,129494921,129535921,129737921,129919921,129979921,130020031,130030031,130060031,130141031,130171031,130222031,130333031,130444031,130464031,130545031,130555031,130585031,130606031,130636031,130717031,130767031,130818031,130828031,130858031,130969031,131030131,131111131,131121131,131222131,131252131,131333131,131555131,131565131,131585131,131646131,131676131,131828131,132010231,132191231,132464231,132535231,132595231,132646231,132676231,132757231,133020331,133060331,133111331,133161331,133252331,133474331,133494331,133575331,133686331,133767331,133818331,133909331,134090431,134181431,134232431,134424431,134505431,134525431,134535431,134616431,134757431,134808431,134858431,134888431,134909431,134919431,134979431,135010531,135040531,135101531,135121531,135161531,135262531,135434531,135494531,135515531,135626531,135646531,135707531,135838531,135868531,135878531,135929531,135959531,135979531,136090631,136171631,136222631,136252631,136303631,136363631,136474631,136545631,136737631,136797631,136818631,136909631,136969631,137030731,137040731,137060731,137090731,137151731,137171731,137232731,137282731,137333731,137363731,137424731,137474731,137606731,137636731,137696731,137757731,137808731,137838731,137939731,137999731,138040831,138131831,138242831,138292831,138313831,138383831,138454831,138575831,138616831,138646831,138757831,138898831,138959831,138989831,139131931,139161931,139222931,139252931,139282931,139383931,139474931,139515931,139606931,139626931,139717931,139848931,139959931,139969931,139999931,140000041,140030041,140151041,140303041,140505041,140565041,140606041,140777041,140787041,140828041,140868041,140898041,141020141,141070141,141131141,141151141,141242141,141262141,141313141,141343141,141383141,141484141,141494141,141575141,141595141,141616141,141767141,141787141,141848141,142000241,142030241,142080241,142252241,142272241,142353241,142363241,142464241,142545241,142555241,142686241,142707241,142797241,142858241,142888241,143090341,143181341,143262341,143303341,143454341,143474341,143585341,143636341,143787341,143828341,143919341,143969341,144010441,144020441,144202441,144212441,144313441,144353441,144404441,144434441,144484441,144505441,144707441,144757441,144808441,144818441,144848441,144878441,144898441,144979441,144989441,145020541,145030541,145090541,145353541,145363541,145393541,145464541,145494541,145575541,145666541,145767541,146030641,146040641,146181641,146222641,146252641,146313641,146363641,146505641,146555641,146565641,146676641,146858641,146909641,147191741,147232741,147242741,147313741,147343741,147373741,147434741,147515741,147565741,147616741,147686741,147707741,147757741,147838741,147929741,148020841,148060841,148080841,148414841,148444841,148525841,148545841,148585841,148666841,148686841,148707841,148818841,148858841,148888841,148969841,149000941,149333941,149343941,149484941,149535941,149555941,149616941,149646941,149696941,149858941,149888941,149909941,149919941,149939941,150070051,150151051,150181051,150202051,150272051,150434051,150494051,150505051,150626051,150686051,150727051,150808051,150818051,150979051,151080151,151161151,151212151,151222151,151282151,151353151,151545151,151585151,151656151,151737151,151777151,151858151,151878151,151888151,151959151,151969151,151999151,152090251,152111251,152171251,152181251,152252251,152363251,152393251,152454251,152505251,152565251,152616251,152646251,152666251,152696251,152888251,152939251,153212351,153272351,153292351,153313351,153323351,153404351,153424351,153454351,153484351,153494351,153626351,153808351,153818351,153838351,153979351,154030451,154191451,154252451,154272451,154303451,154323451,154383451,154393451,154474451,154494451,154555451,154575451,154989451,155060551,155141551,155171551,155292551,155313551,155333551,155373551,155424551,155474551,155535551,155646551,155666551,155676551,155808551,155828551,155868551,156151651,156262651,156343651,156424651,156434651,156494651,156545651,156595651,156656651,156707651,156727651,156757651,156848651,156878651,156949651,157090751,157101751,157161751,157252751,157393751,157444751,157555751,157717751,157878751,157888751,157939751,157959751,157989751,158090851,158111851,158222851,158252851,158363851,158474851,158595851,158676851,158696851,158747851,158808851,158858851,158898851,158909851,159020951,159040951,159050951,159121951,159181951,159191951,159202951,159232951,159262951,159292951,159323951,159404951,159464951,159565951,159595951,159646951,159757951,159808951,159919951,159929951,159959951,160020061,160050061,160080061,160101061,160131061,160141061,160161061,160171061,160393061,160545061,160696061,160707061,160717061,160797061,160878061,161171161,161282161,161313161,161363161,161474161,161484161,161535161,161585161,161636161,161787161,161838161,161969161,162040261,162232261,162404261,162464261,162484261,162565261,162686261,162707261,162757261,162898261,162919261,162949261,162959261,162979261,162989261,163101361,163333361,163434361,163464361,163474361,163494361,163515361,163555361,163606361,163686361,163696361,163878361,163959361,164000461,164070461,164151461,164292461,164333461,164454461,164484461,164585461,164616461,164696461,164717461,164727461,164838461,165101561,165161561,165191561,165212561,165343561,165515561,165535561,165808561,165878561,165898561,165919561,165949561,166000661,166080661,166171661,166191661,166404661,166545661,166555661,166636661,166686661,166818661,166828661,166878661,166888661,166929661,167000761,167111761,167262761,167393761,167454761,167474761,167484761,167636761,167646761,167787761,167888761,167898761,167979761,168151861,168191861,168232861,168404861,168505861,168515861,168565861,168818861,168898861,168929861,168949861,169060961,169131961,169141961,169282961,169333961,169383961,169464961,169555961,169606961,169656961,169666961,169686961,169777961,169797961,169858961,169999961,170040071,170060071,170232071,170303071,170333071,170414071,170424071,170484071,170606071,170616071,170646071,170828071,170838071,170909071,170979071,171080171,171262171,171292171,171343171,171565171,171575171,171767171,171919171,171959171,172060271,172090271,172161271,172353271,172363271,172393271,172474271,172585271,172656271,172747271,172767271,172797271,172878271,172909271,172959271,173000371,173030371,173090371,173252371,173373371,173454371,173525371,173585371,173696371,173757371,173777371,173828371,173868371,173888371,173898371,173919371,174080471,174121471,174131471,174181471,174313471,174343471,174595471,174646471,174676471,174919471,174949471,174979471,174989471,175000571,175090571,175101571,175111571,175353571,175444571,175555571,175626571,175747571,175777571,175848571,175909571,176090671,176111671,176141671,176181671,176232671,176313671,176333671,176373671,176393671,176414671,176585671,176636671,176646671,176666671,176696671,176757671,176787671,176888671,176898671,176939671,177121771,177161771,177202771,177242771,177323771,177565771,177616771,177707771,177757771,177868771,178101871,178131871,178141871,178161871,178353871,178414871,178515871,178525871,178656871,178717871,178747871,178878871,178969871,178989871,178999871,179010971,179060971,179222971,179232971,179262971,179414971,179454971,179484971,179717971,179777971,179808971,179858971,179868971,179909971,179969971,179999971,180070081,180101081,180161081,180292081,180515081,180535081,180545081,180565081,180616081,180757081,180959081,181111181,181515181,181545181,181666181,181737181,181797181,181888181,182010281,182202281,182373281,182585281,182616281,182636281,182777281,182858281,182949281,183232381,183626381,183656381,183737381,183898381,183979381,183989381,184030481,184212481,184222481,184303481,184393481,184414481,184545481,184585481,184606481,184636481,184747481,184818481,184878481,185232581,185373581,185393581,185525581,185555581,185595581,185676581,185757581,185838581,185858581,185868581,185999581,186010681,186040681,186050681,186070681,186101681,186131681,186151681,186161681,186424681,186484681,186505681,186565681,186656681,186676681,186787681,186898681,187090781,187101781,187111781,187161781,187272781,187404781,187434781,187444781,187525781,187767781,187909781,187939781,187999781,188010881,188060881,188141881,188151881,188303881,188373881,188414881,188454881,188505881,188525881,188535881,188616881,188636881,188646881,188727881,188777881,188868881,188888881,188898881,188979881,189080981,189131981,189262981,189292981,189464981,189535981,189595981,189727981,189787981,189838981,189898981,189929981,190000091,190020091,190080091,190101091,190252091,190404091,190434091,190464091,190494091,190656091,190696091,190717091,190747091,190777091,190858091,190909091,191090191,191171191,191232191,191292191,191313191,191565191,191595191,191727191,191757191,191838191,191868191,191939191,191969191,192101291,192191291,192202291,192242291,192313291,192404291,192454291,192484291,192767291,192797291,192898291,193000391,193030391,193191391,193212391,193282391,193303391,193383391,193414391,193464391,193555391,193686391,193858391,193888391,194000491,194070491,194121491,194222491,194232491,194292491,194303491,194393491,194505491,194595491,194606491,194787491,194939491,194999491,195010591,195040591,195070591,195151591,195202591,195242591,195353591,195505591,195545591,195707591,195767591,195868591,195878591,195949591,195979591,196000691,196090691,196323691,196333691,196363691,196696691,196797691,196828691,196878691,197030791,197060791,197070791,197090791,197111791,197121791,197202791,197292791,197343791,197454791,197525791,197606791,197616791,197868791,197898791,197919791,198040891,198070891,198080891,198131891,198292891,198343891,198353891,198383891,198454891,198565891,198656891,198707891,198787891,198878891,198919891,199030991,199080991,199141991,199171991,199212991,199242991,199323991,199353991,199363991,199393991,199494991,199515991,199545991,199656991,199767991,199909991,199999991";\n\t\tString[] tr = str.split(",");\n        int[] a = new int[tr.length];\n        for(int i=0;i<a.length;i++) a[i] = Integer.parseInt(tr[i]);\n        \n        //find the first\n        int lo=0;\n        int hi = a.length;\n        while(lo < hi){\n            int mid = lo+hi>>1;\n            if(a[mid] < n){\n                lo=mid+1;\n            }else{\n                hi=mid;\n            }\n        }\n        return a[lo];\n        \n    }\n    \n    private boolean isPrime(int n){\n        if( n <= 1) return false;\n        for(int i=2;i*i<=n;i++){\n            if(n%i==0) return false;\n        }\n        return true;\n    }\n}\n```
[]