Find the smallest prime palindrome greater than or equal to N.
Recall that a number is prime if it's only divisors are 1 and itself, and it is greater than 1. 
For example, 2,3,5,7,11 and 13 are primes.
Recall that a number is a palindrome if it reads the same from left to right as it does from right to left. 
For example, 12321 is a palindrome.
 

Example 1:
Input: 6
Output: 7


Example 2:
Input: 8
Output: 11


Example 3:
Input: 13
Output: 101



 
Note:

1 <= N <= 10^8
The answer is guaranteed to exist and be less than 2 * 10^8.

Difficulty: interview

Starter code:

class Solution:
    def primePalindrome(self, N: int) -> int:
        

Solutions:
import bisect


class Solution:
    def primePalindrome(self, N: int) -> int:
        return primes[bisect.bisect_left(primes, N)]


primes = [
    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,
]



class Solution:
    
    def next_palindrome(self,n):
        if self.AreAll9s(n):
            pal = str(1)  
            for i in range(1, len(str(n))):  
                pal = pal + str(0)  
            pal = pal + str(1)
            return int(pal)
            
        x = len(str(n))
        if x>2:
            first_num = n//10**(x-1)
            if x%2==0:
                pal = str(1)
                for i in range(1, len(str(n))):
                    pal = pal + str(0)
                pal = pal + str(1)
                return int(pal)
            if first_num%2==0 or first_num%5==0:
                n = (first_num+1) * (10**(x-1))
            
        if x%2 == 0:
            first_half = n//(10**(x//2))
            first_half_reversed = str(first_half)[::-1]
            second_half = n%(10**(x//2))
            if int(first_half_reversed) > second_half:
                return int(str(first_half)+first_half_reversed)
            else:
                first_half = first_half + 1
                pal = str(first_half)+str(first_half)[::-1]
                return int(pal)
            
        else:
            first_half = n//(10**(x//2))
            second_half = n%(10**x//2)
            first_half_reversed = str(first_half//10)[::-1]
            if int(first_half_reversed) > second_half:
                return int(str(first_half)+first_half_reversed)
            else:
                first_half = first_half + 1
                pal = str(first_half)+str(first_half//10)[::-1]
                return int(pal)
            
        
    def AreAll9s(self,  n):  
        for i in str(n): 
            if( int(i) != 9 ) : 
                return 0
        return 1
    
    def mrange(self, start, stop, step):
        while start < stop:
            yield start
            start += step
        
    def check_prime(self, num):
        if num == 2:
            return True
        if (num < 2) or (num % 2 == 0):
            return False
        return all(num % i for i in self.mrange(3, int((num)**0.5) + 1, 2))
    
    def primePalindrome(self, N: int) -> int:
        x = N
        while x>=N:
            if x>11:
                x = self.next_palindrome(x)
                if self.check_prime(x):
                    return x
            else:
                if self.check_prime(x):
                    return x
                x= x+1
            
        
        


class Solution:
    def primePalindrome(self, N: int) -> int:
        def checkPrime(x):
            if x == 1:
                return False

            for i in range(2, int(math.sqrt(x) + 0.01) + 1):
                if x % i == 0:
                    return False

            return True
        
        def makePal(ni):
            n = str(ni)
            l = len(n)
            hn = n[:l // 2]
            rhn = ''.join(reversed(hn))
            
            if l % 2 != 0:
                return int(hn + n[l // 2] + rhn)
            else:
                return int(hn + rhn)
                
        def nextPal(n):
            n = n + 10 ** (len(str(n)) // 2)
            return makePal(n)

        n = makePal(N)
        if n < N:
            n = nextPal(n)

        while True:
            if checkPrime(n):
                return n
            n = nextPal(n)

class Solution:
    def primePalindrome(self, N: int) -> int:
        
        def isPrime(num):
            if num < 2: return False
            for i in range(2, int(sqrt(num))+1):
                if num%i == 0 :
                    return False
            return True
        
        for length in range(1,6):
            for i in range(10**(length-1), 10**(length)):
                num = str(i)
                palindrome = int(num + num[-2::-1])
                if palindrome >= N and isPrime(palindrome):
                    return min(palindrome, 11) if N <= 11 else palindrome
        
        return 0

class Solution:
    def primePalindrome(self, N: int) -> int:
        if N == 1:
            return 2
        if N <= 3 or N ==5 or N == 7:
            return N
        if N == 4:
            return 5
        if N == 6:
            return 7
        if N <= 11:
            return 11
        
        
        for i in range(10, 2*10**4):
            s = str(i)
            num = int(s + s[:-1][::-1])
            if num >= N and self.is_prime(num):
                return num
        
    def is_prime(self, num):
        i = 2 
        while i*i <= num:
            if num%i == 0:
                return False
            i += 1
        return True

class Solution:
    def primePalindrome(self, N: int) -> int:
        
        
        def get_palindromes(n):
            if n == 1:
                for i in range(10):
                    yield i
            elif n % 2 == 0:
                d = n // 2
                for i in range(10**(d-1), 10**d):
                    s = str(i)
                    yield int(s + s[::-1])
            else:
                d = n // 2
                for i in range(10**(d-1), 10**d):
                    s = str(i)
                    for j in range(10):
                        yield int(s + str(j) + s[::-1])
        
        def check_prime(num):
            if num==1:
                return False
            elif num==2:
                return True
            for i in range(2, int(num**0.5+1)):
                if num%i==0:
                    return False
            return True        
        
        digits = len(str(N))
        while True:
            for n in get_palindromes(digits):
                if n>=N and check_prime(n):
                    return n
            digits+=1

class Solution:
    def primePalindrome(self, N: int) -> int:
        
        
        def get_palindromes(n):
            if n == 1:
                for i in range(10):
                    yield i
            elif n % 2 == 0:
                d = n // 2
                for i in range(10**(d-1), 10**d):
                    s = str(i)
                    yield int(s + s[::-1])
            else:
                d = n // 2
                for i in range(10**(d-1), 10**d):
                    s = str(i)
                    for j in range(10):
                        yield int(s + str(j) + s[::-1])
        
        def check_prime(x):
            if x == 1:
                return False
            if x == 2:
                return True
            for i in range(2, int(x**0.5+1)):
                if x % i == 0:
                    return False
            return True        
        
        digits = len(str(N))
        while True:
            for n in get_palindromes(digits):
                if n>=N and check_prime(n):
                    return n
            digits+=1

class Solution:
    def is_prime(self,N):
        if N==1:
            return False

        for i in range(2,int(math.sqrt(N))+1):
            if N%i==0:
                return False
        else:
            return True

    def primePalindrome(self, N: int) -> int:
        if N>=8 and N<=11:
            return 11
        for i in range(1,100000):
            s=str(i)
            d=s[::-1]
            y=int(s+d[1:])
            if y>=N and self.is_prime(y):
                return y

from math import sqrt

class Solution:
    def primePalindrome(self, N: int) -> int:
        ans = 9999999999
        MAX_K = 20_000
        
        if 8 <= N <= 11:
            return 11
        
        for i in range(2, MAX_K):
            # no need for even as would be div by 11
            o = make_odd_palindrome(i)      
            if o >= N and is_prime(o):
                return o

        return ans   
    
def make_odd_palindrome(n: int) -> int:
    s = str(n)
    p = s[:-1]
    odd = int(p + s[-1] + p[::-1])
    return odd
    
def is_prime(n: int) -> bool:
    for i in range(2, int(sqrt(n)) + 5):
        if n % i == 0 and n != i:
            return False
        
    return True

class Solution:
    def primePalindrome(self, N: int) -> int:
        if N < 12:
            for i in range(1, 12):
                if self.isPrime(i) and i >= N:
                    return i
        strN = str(N)
        strLen = len(strN)
        if strLen % 2 == 0:
            startPoint = 10 ** (strLen - strLen // 2)
        else:
            startPoint = int(strN[:strLen - strLen//2])
        for point in range(startPoint, 10**6):
            strPoint = str(point)
            palindrome = int(strPoint + strPoint[-2::-1])
            if palindrome >= N and self.isPrime(palindrome):
                return palindrome
    def isPrime(self, p):
        return p > 1 and all(p % d for d in range(2, int(p**0.5)+1))
            
        


class Solution(object):
    def primePalindrome(self, N):
        def is_prime(n):
            return n > 1 and all(n%d for d in range(2, int(n**.5) + 1))

        for length in range(1, 6):
            #Check for odd-length palindromes
            for root in range(10**(length - 1), 10**length):
                s = str(root)
                x = int(s + s[-2::-1]) #eg. s = '123' to x = int('12321')
                if x >= N and is_prime(x):
                    return x
                    #If we didn't check for even-length palindromes:
                    #return min(x, 11) if N <= 11 else x

            #Check for even-length palindromes
            for root in range(10**(length - 1), 10**length):
                s = str(root)
                x = int(s + s[-1::-1]) #eg. s = '123' to x = int('123321')
                if x >= N and is_prime(x):
                    return x

class Solution:
    def primePalindrome(self, N: int) -> int:
        digits = len(str(N))
        
        while True:
            for num in self.get_pali(digits):
                if num >= N and self.is_prime(num):
                    return num
            digits += 1
    
    def get_pali(self, digits):
        if digits == 0:
            yield 0
        elif digits == 1:
            for i in range(10):
                yield i
        elif digits % 2 == 0:
            half = digits//2
            for i in range(10**(half-1), 10**half):
                yield int(str(i)+(str(i)[::-1]))
        else:
            half = digits//2
            for i in range(10**(half-1), 10**half):
                for j in range(10):
                    yield int( str(i) + str(j) + str(i)[::-1]  )
    
    def is_prime(self, num):
        if num < 2:
            return False
        if num == 2:
            return True
        for i in range(2, int(num**0.5+1)):
            if num % i == 0:
                return False
        return True


class Solution:
    def primePalindrome(self, N: int) -> int:
        def is_prime(n):
            return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))
        
        for length in range(1, 6):
            for root in range(10**(length - 1), 10 ** length):
                s = str(root)
                x = int(s + s[-2::-1])
                if x >= N and is_prime(x):
                    return x
                
            for root in range(10**(length - 1), 10 ** length):
                s = str(root)
                x = int(s + s[-1::-1])
                if x >= N and is_prime(x):
                    return x

class Solution:
    def is_prime(n: int) -> bool:
        i = 2
        while i * i <= n:
            if n % i == 0:
                return False
            i = i + 1
        return True


    def is_palindrome(n: int) -> bool:
        num_string = str(n)
        num_length = len(num_string)

        if num_string[num_length - 1] == 0:
            return False

        i = 0
        while i < num_length - i - 1:
            if num_string[i] != num_string[num_length - i - 1]:
                return False
            i = i + 1

        return True


    def prime_palindrome(n: int) -> int:
        answer = n

        if answer <= 2:
            return 2

        if 7 < answer <= 11:
            return 11

        if answer % 2 == 0:
            answer = answer + 1

        while True:
            num_length = len(str(answer))
            if num_length % 2 == 0:
                answer = 10 ** num_length + 1
                continue
            elif Solution.is_palindrome(answer) and Solution.is_prime(answer):
                return answer
            answer = answer + 2
    
    
    def primePalindrome(self, N: int) -> int:
        return Solution.prime_palindrome(N)


class Solution:
    def primePalindrome(self, N: int) -> int:
        
        def isprime(i):
            if i == 1:
                return False
            for j in range(2,int(i**(0.5))+1):
                if i%j == 0:
                    return False
            return True
        
        i = N
        while i < 2*(10**10):
            x = str(i)
            if len(x)%2 == 0 and len(x)>2:
                i = 10 ** (len(x))
                continue
            elif x == x[::-1]:
                if isprime(i):
                    return i
            i += 1
            
                    


# Math
# Explanation: Solution 1
# O(n)
# O(logn)

class Solution:
    def primePalindrome(self, N: int) -> int:
        def is_prime(n):
            return n > 1 and all(n%d for d in range(2, int(n**.5) + 1))
        
        for length in range(1,6):
            for root in range(10**(length-1),10**(length)):
                s = str(root)
                x = int(s+s[-2::-1])
                if x>=N and is_prime(x):
                    return x
            
            for root in range(10**(length-1),10**(length)):
                s = str(root)
                x = int(s+s[-1::-1])
                if x>=N and is_prime(x):
                    return x

class Solution:
    def primePalindrome(self, N: int) -> int:
        
        def isPrime(n):
            return n > 1 and all( n % f for f in range(2, int(n ** .5)+1) )
        
        def isPalin(n):
            tmp = str(n)
            return tmp == tmp[::-1]
        
        while True:
            if isPalin(N) and isPrime(N):
                return N
            
            N += 1
            if 12 <= N <= 99:
                N = 100
            elif 1000 <= N <= 9999:
                N = 10000
            elif 100000 <= N <= 999999:
                N = 1000000
            elif 10000000 <= N <= 99999999:
                N = 100000000
        


class Solution:
    def primePalindrome(self, N: int) -> int:
        
        # Brutal force over time limit
        if N == 1 or N == 2:
            return 2
        
        def isprime(k):
            j = 3
            while j*j <= k:
                if k%j == 0:
                    return False
                j += 2
            return True
        
        
        i = N//2*2+1
        while i < 10**7:
            if str(i) == str(i)[::-1]:
                if isprime(i):
                    return i
            i += 2
        return 100030001

class Solution:
    def primePalindrome(self, N: int) -> int:
        if N < 12:
            for i in range(1, 12):
                if self.isPrime(i) and i >= N:
                    return i
        strN = str(N)
        strLen = len(strN)
        if strLen % 2 == 0:
            startPoint = 10 ** (strLen // 2)
        else:
            startPoint = int(strN[:strLen//2+1])
        for point in range(startPoint, 10**6):
            strPoint = str(point)
            palindrome = int(strPoint + strPoint[-2::-1])
            if palindrome >= N and self.isPrime(palindrome):
                return palindrome
    def isPrime(self, p):
        return p > 1 and all(p % d for d in range(2, int(p**0.5)+1))
            
        


class Solution:
    def primePalindrome(self, N: int) -> int:
        if N == 1:
            return 2

        N_ary = []
        compute_N = N
        while not compute_N == 0:
            N_ary.insert(0, compute_N % 10)
            compute_N //= 10
            
        middle = len(N_ary) // 2
        for i in range(middle, len(N_ary)):
            N_ary[i] = N_ary[len(N_ary) - 1 - i] = min(N_ary[i], N_ary[len(N_ary) - 1 - i])
            
        result = 0
        while True:
            num = self.ary_to_int(N_ary)
            if num < N:
                N_ary = self.compute_next_ary(N_ary)
                continue
            is_prime = True
            for i in range(2, num):
                if i**2 > num:
                    break
                if num % i == 0:
                    is_prime = False
                    break
            if is_prime == True:
                result = num
                break
            N_ary = self.compute_next_ary(N_ary)
            
        return result


    def ary_to_int(self, ary: List[int]) -> int:
        result = 0
        for num in ary:
            result = result * 10 + num
        return result
    
        
    def compute_next_ary(self, ary: List[int]) -> List[int]:
        middle = len(ary) // 2

        is_all_nine = True
        for i in range(middle, len(ary)):
            if not ary[i] == 9:
                is_all_nine = False
                break                
        if is_all_nine:
            ary = [0 for i in range(len(ary) + 1)]
            ary[0] = ary[-1] = 1
            return ary
        
        for i in range(middle, len(ary)):
            if ary[i] == 9:
                ary[i] = ary[len(ary) - 1 - i] = 0
            else:
                ary[i] = ary[len(ary) - 1 - i] = ary[i] + 1
                break
        return ary


class Solution(object):
    def primePalindrome(self, N):
        def is_prime(n):
            return n > 1 and all(n%d for d in range(2, int(n**.5) + 1))

        for length in range(1, 6):
            #Check for odd-length palindromes
            for root in range(10**(length - 1), 10**length):
                s = str(root)
                x = int(s + s[-2::-1]) #eg. s = '123' to x = int('12321')
                if x >= N and is_prime(x):
                    return x
                    #If we didn't check for even-length palindromes:
                    #return min(x, 11) if N <= 11 else x

            #Check for even-length palindromes
            for root in range(10**(length - 1), 10**length):
                s = str(root)
                x = int(s + s[-1::-1]) #eg. s = '123' to x = int('123321')
                if x >= N and is_prime(x):
                    return x




class Solution:
    def primePalindrome(self, N: int) -> int:
        def even_palindrome(n: int) -> int:
            return int(str(n) + str(n)[::-1])
        
        def odd_palindrome(n: int) -> int:
            return int(str(n) + str(n)[::-1][1:])
        
        def is_prime(n: int) -> int:
            return n > 1 and all(n%i for i in range(2, int(n**.5)+1))
        
        odd, even = 1, 1
        while True:
            next_even = even_palindrome(even)
            next_odd = odd_palindrome(odd)
            # print(next_even, next_odd)
            cur = min(next_even, next_odd)
            if cur >= N and is_prime(cur):
                return cur
            if next_even > next_odd:
                odd += 1
            else:
                even += 1        

class Solution:
    def primePalindrome(self, N: int) -> int:
        def isPrime(n):
            if n > 1:
                if n == 2:
                    return True
                if n % 2 == 0:
                    return False
                for x in range(3, int(n**.5 + 1), 2):
                    if n % x == 0:
                        return False
                return True
            return False
        def nextPalind(N):
            i = N + 1
            while True:
                if str(i) == str(i)[::-1]:
                    return i
                else:
                    i += 1
        if N >= 9989900:
            return 100030001
        
        if isPrime(N) and (str(N)==str(N)[::-1]):
            return N
        else:
            i = nextPalind(N)
            while not isPrime(i):
                i = nextPalind(i)
            return i

class Solution:
    def primePalindrome(self, N: int) -> int:
        
        if N == 1:
            return 2
        
        import math
        def isPrime (n):
            
            lm = int (math.floor (math.sqrt(n)))
            for i in range (2, lm+1):
                if n%i == 0:
                    return False
                
            return True
        
        def odd (n):
            
            t = n
            n = n//10
            mul = 1
            new = 0
            while n:
                new = new*10 + (n%10)
                mul = mul*10
                n = n//10
                
            return t*mul+new
        
        def even (n):
            
            t = n
            mul = 1
            new = 0
            while n:
                new = new*10 + (n%10)
                mul = mul*10
                n = n//10
                
            return t*mul + new
        
        o = 1
        e = 1
        
        while True:
            
            opal = odd (o)
            epal = even (e)
            #print (opal, epal)
            
            if opal < epal:
                if opal >= N and isPrime (opal):
                    return opal
                o += 1
            else:
                if epal >= N and isPrime (epal):
                    return epal
                e += 1            

class Solution:
    def primePalindrome(self, N: int) -> int:
        @lru_cache(None)
        def isPrime(n):
            if n == 1:
                return False
            for i in range(2, int(sqrt(n))+1):
                if isPrime(i):
                    if n % i == 0:
                        return False
            return True

        def isPalindrome(n):
            return n == int(str(n)[::-1])

        while True:
            if isPalindrome(N) and isPrime(N):
                return N
            N += 1
            length = len(str(N))
            if length > 2 and length % 2 == 0:
                N = int('1'+'0'*(length-1) + '1')
        return None

def isPrimes(n):
    return n > 1 and all(n%d > 0 for d in range(2, int(sqrt(n)) + 1))

def reverse(x):
    return int(str(x)[::-1])

class Solution:
    def primePalindrome(self, N: int) -> int:
        if N >= 9989900:
            return 100030001
        while True:
            if N == reverse(N) and isPrimes(N):
                return N
            N += 1
        


class Solution:

    def is_prime(self, n):
        small_primes = (2, 3, 5, 7, 11, 13, 17, 19)
        if n == 1:
            return False
        if n in small_primes:
           return True
        for p in small_primes:
            if n % p == 0:
                return False
        check_limit = int(n**0.5)+1
        for p in range(small_primes[-1], check_limit, 2):
            if n % p == 0:
                return False
        return True

    def is_odd_len_palindrome(self, n):
        n_str = str(n)
        total_digit = len(n_str)
        len_is_odd = total_digit % 2 != 0
        if not len_is_odd:
            return False
        half_len_n = int((total_digit+1)/2)
        if n_str[:half_len_n] != n_str[total_digit-half_len_n:][::-1]:
            return False
        return True

    def find_odd_len_palindrome_after_n(self, n):
        if n < 9:
            return n + 1
        elif n < 11:
            return 11
        n_str = str(n)
        total_digit = len(n_str)
        len_is_odd = total_digit % 2 != 0
        if not len_is_odd:
            return int('1' + '0'*(total_digit-1) + '1')
        half_len_n = int((total_digit+1)/2)
        left_str = n_str[:half_len_n]
        right_str = left_str[:total_digit-half_len_n][::-1]
        p = int(left_str+right_str)
        if p > n:
            return p
        else:
            left = int(left_str)
            left += 1
            increase_digit = len(str(left)) > len(left_str)
            left_str = str(left)
            if increase_digit:
                return int('1' + '0' * total_digit + '1')
            left_str = left_str[:half_len_n]
            right_str = left_str[:total_digit-half_len_n][::-1]
            return int(left_str+right_str)


    def primePalindrome(self, N: int) -> int:
        if self.is_odd_len_palindrome(N) and self.is_prime(N):
            return N
        elif N == 11:
            return N
        i = self.find_odd_len_palindrome_after_n(N)
        while i < 2 * 10 ** 8:
            if self.is_prime(i):
                return i
            i = self.find_odd_len_palindrome_after_n(i)
        return i


class Solution:
    
    def primePalindrome(self, N: int) -> int:
        
        def is_prime(num):
            return num>1 and all(num%d for d in range(2,int(num**0.5)+1))
                
        while True:
            if str(N)==str(N)[::-1] and is_prime(N):
                return N
            N+=1
            if 10**7<N<10**8:
                N=10**8
        


class Solution:
    def primePalindrome(self, N: int) -> int:
        def isPrime(num):
            if num == 1:
                return False
            for div in range(2,int(num**0.5)+1):
                if num%div == 0:
                    return False
            return True

        def isPalindrome(num):
            num = str(num)
            left = 0
            right = len(num)-1
            while left < right:
                if num[left] != num[right]:
                    return False
                left += 1
                right -= 1
            return True

        while True:
            if isPalindrome(N) and isPrime(N):
                break
            N += 1
            if 10**7 < N < 10**8:
                N = 10**8
        return N

class Solution:
    def primePalindrome(self, N: int) -> int:
        for i in range(N, 10**7+1):
            if not self.isPalindrome(i): continue
            if not self.isPrime(i): continue
            return i
        
        for i in range(10**8, 2*10**8):
            if not self.isPalindrome(i): continue
            if not self.isPrime(i): continue
            return i
        
    def isPalindrome(self, i):
        i = str(i)
        return i == i[::-1]
    
    def isPrime(self, i):
        return i > 1 and all([i%d != 0 for d in range(2, int(sqrt(i))+1)])

class Solution:
    def primePalindrome(self, N: int) -> int:
        if N == 1:
            return 2
        def isPrime(num):
            for i in range(2, int(num ** 0.5) + 1):
                if num % i == 0:
                    return False
            return True
        while str(N) != str(N)[::-1] or not isPrime(N):
            N += 1
            if 10 ** 7 < N < 10 ** 8:
                N = 10 ** 8
        return N


class Solution:
    def primePalindrome(self, N: int) -> int:
        def isPrime(x):
            '''
            for i in range(2,int(sqrt(x))+1):
                if x % i == 0:
                    return False
            return True
            '''
            return x > 1 and all(x%d for d in range(2,int(x**.5)+1))
        def isPalindrome(x):
            x = str(x)
            if len(x) == 1:
                return True
            i = 0
            j = len(x) - 1
            while i < j:
                if x[i] == x[j]:
                    i += 1
                    j -= 1
                else:
                    return False
            return True
        if N <= 1:
            return 2
        i = N
        while True:
            if str(i) == str(i)[::-1] and isPrime(i):
                return i
            i += 1
            if 10**7 < i < 10**8:
                i = 10**8
        return -1


class Solution:
    def primePalindrome(self, N: int) -> int:
        def reverse(n):
            return int(str(n)[::-1])
        
        def isPrime(n):
            return n > 1 and all(n%d for d in range(2, int(n**.5) + 1))
        
        while True:
            if N == reverse(N) and isPrime(N):
                return N
            N += 1
            if 10**7 < N < 10**8:
                N = 10**8


class Solution:
    def primePalindrome(self, N: int) -> int:
        def is_prime(n):
            return n > 1 and all(n % d for d in range(2, int(n**.5) + 1))

        def reverse(x):
            return int(str(N)[::-1])

        while True:
            if N == reverse(N) and is_prime(N):
                return N
            N += 1
            if 10**7 < N < 10**8:
                N = 10**8
        
        return 2*(10**8)

class Solution:
    def primePalindrome(self, N: int) -> int:
        
        def isprime(N):
            if N <= 1: return False
            n = 2
            while n <= N**.5:
                if N%n == 0:
                    return False
                n += 1
            return True
        
        def ispali(N):
            s = str(N)
            i, j = 0, len(s)-1
            while i <= j:
                if s[i] != s[j]:
                    return False
                i +=1
                j -=1
            return True
        
        
        while 1:
            if ispali(N):
                if isprime(N):
                    return N
            N += 1
            if 10**7 < N < 10**8:
                N = 10**8

class Solution:
    def primePalindrome(self, N: int) -> int:
        def check_p(n):
            return n>1 and all(n%d for d in range(2, int(n**0.5)+1))
        while True:
            if str(N)==str(N)[::-1] and check_p(N):
                return N
            N+=1
            if 10**8>N>10**7:
                N=10**8

class Solution:
    def primePalindrome(self, N: int) -> int:
        def ispad(n):
            n = str(n)
            n = list(n)
            left, right = 0,len(n)-1
            while left < right:
                if n[left] != n[right]:
                    return False
                left += 1
                right -= 1
            return True
            
        
        def isprime(n):
            for i in range(2, int(n**.5)+1):
                if n%i==0:
                    return False
            return True
        
        if N==1:
            return 2
        
        while True:
            if ispad(N) and isprime(N):
                return N
            N+=1
            if 10**7 < N < 10**8:
                N = 10**8


class Solution:
    def primePalindrome(self, N: int) -> int:
        i = N
        while True:
            if self.isPalindrome(str(i)):
                if self.isPrime(i):
                    return i
            i += 1
            if 10**7 < i < 10**8:
                i = 10**8
            
    def isPalindrome(self, s):
        for i in range(0, len(s) // 2):
            if s[i] != s[len(s)-1-i]:
                return False
        return True

    def isPrime(self, n):
        if n < 2 or len(str(n)) == 8:
            return False
        
        upper = int(sqrt(n))
        for i in range(2, upper+1):
            if n % i == 0:
                return False
        return True

        # return True


class Solution:
    def primePalindrome(self, N: int) -> int:
        def isPrime(x):
            if x == 1:
                return False
            for i in range(2,int(x**0.5)+1):
                if x%i == 0:
                    return False
            return True

        def isPalindrome(x):
            x = str(x)
            l = [ch for ch in x]
            return l[::-1]==l
           
        while True:
            if isPalindrome(N) and isPrime(N):
                break
            N += 1
            if 10**7 < N < 10**8:
                N = 10**8
        return N

class Solution(object):
    def primePalindrome(self, N):
        def is_prime(n):
            return n > 1 and all(n % d for d in range(2, int(n**.5) + 1))

        def reverse(x):
            ans = 0
            while x:
                ans = 10 * ans + x % 10
                x //= 10
            return ans

        while True:
            if N == reverse(N) and is_prime(N):
                return N
            N += 1
            if 10**7 < N < 10**8:
                N = 10**8

class Solution:
    def primePalindrome(self, N: int) -> int:
        def isPrime(n):
            if n<=1: return False
            else:
                return all(n%d for d in range(2,int(n**0.5)+1))
        def reverse(n):
            ans = 0
            while n:
                ans = 10*ans+n%10
                n = n//10
            return ans
        while True:
            if N==reverse(N) and isPrime(N):
                return N
            N += 1
            if 10**7<N<10**8:
                N = 10**8

class Solution:
    def primePalindrome(self, N: int) -> int:
        def is_prime(n):
            return n > 1 and all(n % d for d in range(2, int(n**.5) + 1))

        while True:
            if str(N) == str(N)[::-1] and is_prime(N):
                return N
            N += 1
            if 10**7 < N < 10**8:
                N = 10**8

class Solution:
    def primePalindrome(self, N: int) -> int:
        def is_prime(n):
            return n > 1 and all(n % d for d in range(2, int(n**.5) + 1))

        def reverse(x):
            ans = 0
            while x:
                ans = 10 * ans + x % 10
                x //= 10
            return ans

        while True:
            if N == reverse(N) and is_prime(N):
                return N
            N += 1
            if 10**7 < N < 10**8:
                N = 10**8

class Solution:
    def primePalindrome(self, N: int) -> int:
        # Brute Force with Mathematical Shortcut
        # Time  complexity: O(N)
        # Space complexity: O(1)
        def is_prime(n):
            return n > 1 and all(n % d for d in range(2, int(n**.5) + 1))

        def reverse(x):
            ans = 0
            while x:
                ans = 10 * ans + x % 10
                x //= 10
            return ans

        while True:
            if N == reverse(N) and is_prime(N):
                return N
            N += 1
            if 10**7 < N < 10**8:
                N = 10**8


def isPrimes(n):
    return n > 1 and all(n%d > 0 for d in range(2, int(sqrt(n)) + 1))

def reverse(x):
    ans = 0
    while x:
        ans = 10*ans + x%10
        x //= 10
    return ans

class Solution:
    def primePalindrome(self, N: int) -> int:
        while True:
            if N == reverse(N) and isPrimes(N):
                return N
            N += 1
            if 10**7 < N < 10**8:
                N = 10**8


class Solution:
    def primePalindrome(self, N: int) -> int:
        def isPrime(N):
            return N > 1 and all(N % d for d in range(2, int(N**0.5)+1))
        
        # N must be a palindrome with odd number of digits.
        # The return value will have odd number of digits too.
        def nextPalindrome(N):
            if N in [999, 99999, 9999999]:
                return (N + 1) * 10 + 1
            n = str(N // 10 ** (len(str(N))//2) + 1)
            return int(n + n[-2::-1])
        
        if N <= 11: 
            while not isPrime(N):
                N += 1
            return N
        
        if (digits := len(str(N))) % 2 == 0:
            N = 10 ** digits + 1
        else:
            n = str(N // 10 ** (len(str(N))//2))
            if (p := int(n + n[-2::-1])) >= N:
                N = p
            else:
                N = nextPalindrome(p)
                
        while not isPrime(N):
            N = nextPalindrome(N)
        return N

class Solution:
    def primePalindrome(self, N: int) -> int:
        def is_prime(n):
            return n > 1 and all(n % d for d in range(2, int(n ** .5) + 1))

        def reverse(x):
            ans = 0
            while x:
                ans = 10 * ans + x % 10
                x //= 10
            return ans

        while True:
            if N == reverse(N) and is_prime(N):
                return N
            N += 1
            if 10 ** 7 < N < 10 ** 8:
                N = 10 ** 8

class Solution:
    def primePalindrome(self, N: int) -> int:
        def is_prime(n):
            return n > 1 and all(n % d != 0 for d in range(2, int(n**.5) + 1))
        
        def reverse(x):
            y = 0
            while x > 0:
                y = y * 10 + x % 10
                x = x // 10
            return y
        
        while True:
            if N == reverse(N) and is_prime(N):
                return N
            N += 1
            if 10**7 < N < 10**8:
                N = 10**8


def isPrimes(n):
    return n > 1 and all(n%d > 0 for d in range(2, int(sqrt(n)) + 1))

def reverse(x):
    ans = 0
    while x:
        ans = 10*ans + x%10
        x //= 10
    return ans

class Solution:
    def primePalindrome(self, N: int) -> int:
        if N >= 9989900:
            return 100030001
        while True:
            if N == reverse(N) and isPrimes(N):
                return N
            N += 1
        


class Solution:
    def primePalindrome(self, N: int) -> int:
        def reverse(n):
            sm=0
            while n>0:
                r=n%10
                sm=sm*10+r
                n=n//10
            return sm
        
        def isprime(n):
            for i in range(2, int(n**.5)+1):
                if n%i==0:
                    return False
            return True
        
        if N==1:
            return 2
        
        while True:
            if N==reverse(N) and isprime(N):
                return N
            N+=1
            if 10**7 < N < 10**8:
                N = 10**8


class Solution:
    def primePalindrome(self, N: int) -> int:
        def reverse(n):
            sm=0
            while n>0:
                r=n%10
                sm=sm*10+r
                n=n//10
            return sm
        
        def isprime(n):
            for i in range(2, int(sqrt(n))+1):
                if n%i==0:
                    return False
            return True
        
        if N==1:
            return 2
        
        while True:
            if N==reverse(N) and isprime(N):
                return N
            N+=1
            if 10**7 < N < 10**8:
                N = 10**8

class Solution:
    def primePalindrome(self, N: int) -> int:
        def reverse(n):
            a=0
            while n>0:
                r=n%10
                a=a*10+r
                n=n//10
            return a
        def snt(n):
            for i in range(2, int(sqrt(n))+1):
                if n%i==0:
                    return False
            return True
        if N==1:
            return 2
        while True:
            if N==reverse(N) and snt(N):
                return N
            N+=1
            if 10**7 < N < 10**8:
                N = 10**8

class Solution:
    def primePalindrome(self, N: int) -> int:
        def isPrime(num):
            if num < 2 or num%2 == 0:
                return num ==2
            s_num = int(num**0.5)
            for i in range(3, s_num + 1):
                if num%i == 0:
                    return False
            return True
        
        
        if N>=8 and N <= 11:
            return 11
        
        for i in range(10 ** (len(str(N)) // 2), 10**5):
            s = str(i)
            s2 = s + s[::-1][1:]
            if isPrime(int(s2)) and int(s2)>= N:
                return int(s2)
        return N 

from math import sqrt

class Solution:
    def primePalindrome(self, N: int) -> int:
        def subgen(start, upper, odd):
            start = int(start)
            for i in range(start, upper):
                if odd:
                    yield int(str(i) + str(i)[:-1][::-1])
                else:
                    yield int(str(i) + str(i)[::-1])

        def is_prime(n):
            factors = []
            for i in range(1, int(sqrt(n))+1):
                if n % i == 0:
                    factors.extend([i, n // i])
                    if len(factors) > 2:
                        return False
            return len(factors) <= 2

        def generator(N):
            if N <= 10:
                for i in range(2, 10):
                    if is_prime(i): yield i
            if N <= 11:
                yield 11
            if N <= 1000:
                for i in subgen('10', 100, True):
                    if is_prime(i): yield i
            if N <= 10000:
                for i in subgen('10', 100, False):
                    if is_prime(i): yield i
            if N <= 100000:
                for i in subgen('100', 1000, True):
                    if is_prime(i): yield i
            if N <= 1000000:
                for i in subgen('100', 1000, False):
                    if is_prime(i): yield i
            if N <= 10000000:
                for i in subgen('1000', 10000, True):
                    if is_prime(i): yield i
            if N <= 100000000:
                for i in subgen('1000', 10000, False):
                    if is_prime(i): yield i
            if N <= 1000000000:
                for i in subgen('10000', 20000, True):
                    if is_prime(i): yield i

        for g in generator(N):
            if g >= N: return g


class Solution:
    def primePalindrome(self, N: int) -> int:
        
        def prime(n):
            # i = 2
            if(n == 1):
                return False
            for i in range(2 , int(n ** 0.5) + 1):
                if(n % i == 0):
                    return False
            return True
        
        
        def reverse(N):
            res = 0
            d = N
            while(N > 0):
                res = 10 * res + N % 10;
                N = int(N / 10)
            # print(d , res)
            return res
        
        while(1):
            if(N == reverse(N) and prime(N)):
                return N
            # print(N)
            N += 1
            
            if(10**7 < N < 10**8):
                N = 10 ** 8
        
        
        
        


class Solution:
    
    def check_prime(self,N):
        m = int(math.sqrt(N))
        for i in range(2,m+1):
            if N%i == 0:
                return(0)
        return(1) 
    
    def reverse_string(self,s):
        n = len(s)
        t = [s[n-i] for i in range(1,n+1)]
        t = ''.join(t)
        return(t)
    
    def rev(self,l,parity):
        l = [str(s) for s in l]
        if parity == 0:
            l = [s + self.reverse_string(s) for s in l]
        if parity == 1:
            l = [s[:-1] + s[-1] + self.reverse_string(s[:-1]) for s in l]
        return(l)    
    
    def gen_palin(self,k):
        m = k//2
        parity = k%2
        if k%2 == 0:
            l = list(range(10**(m-1),10**(m)))
        if k%2 == 1:
            l = list(range(10**(m),10**(m+1)))
        l = self.rev(l,parity)
        l = [int(x) for x in l]
        l.sort()
        return(l)    
    
    def primePalindrome(self,N):
        if N == 1:
            return(2)
        s = str(N)
        k = len(s)
        current = k
        x = 1
        while x:
            l = self.gen_palin(k)
            for a in l:
                if a >= N:
                    if self.check_prime(a):
                        return(a)
            k += 1        

def isPrime(val):
        if val==1:
            return False
        if val==2:
            return True
        if val%2==0:
            return False
        # print(floor(sqrt(val)))
        for i in range(3,floor(sqrt(val))+2,2):
            # print(i)
            if val%i == 0:
                return False
        return True
class Solution:
        
    def primePalindrome(self, N: int) -> int:
        if N>=8 and N<=11:
            return 11
        mn = 1e9
        print(isPrime(N))
        for i in range(1,10009):
            s = str(i)
            r = s[::-1]
            # print(r)
            r = r[1:]
            # print(r)
            t = int(s+r)
            # print(t)
            if t>=N and isPrime(t):
                mn = min(mn,t)
        return mn

def isPrime(val):
        if val==1:
            return False
        if val==2:
            return True
        if val%2==0:
            return False
        # print(floor(sqrt(val)))
        for i in range(3,floor(sqrt(val))+2,2):
            # print(i)
            if val%i == 0:
                return False
        return True
class Solution:
        
    def primePalindrome(self, N: int) -> int:
        if N>=8 and N<=11:
            return 11
        mn = 1e9
        # print(isPrime(N))
        for i in range(1,10009):
            s = str(i)
            r = s[::-1]
            # print(r)
            r = r[1:]
            # print(r)
            t = int(s+r)
            # print(t)
            if t>=N and isPrime(t):
                mn = min(mn,t)
        return mn

class Solution:
    def primePalindrome(self, N: int) -> int:
        def checkPrime(x):
            if x == 1:
                return False

            for i in range(2, int(math.sqrt(x) + 0.01) + 1):
                if x % i == 0:
                    return False
            return True
        
        def makePal(n):
            l = len(n)
            hn = n[:l // 2]
            s = hn

            if l % 2 != 0:
                s += n[l // 2]
            
            return s + ''.join(reversed(hn))
                
        def nextPal(n):
            ni = int(n) + 10 ** (len(n) // 2)
            return makePal(str(ni))
            
        beg = str(N)
        n = makePal(beg)
        if n < beg:
            n = nextPal(n)

        while True:
            if checkPrime(int(n)):
                return int(n)
            n = nextPal(n)