fork download
copy 
  1.  
  2. /**
  3.  *
  4.  */
  5. import java.io.*;
  6. import java.math.BigInteger;
  7. import java.util.*;
  8.  
  9. class UNICOURS {
  10.     void solve()
  11.     { //(2190 numbers)
  12.         long arr [] = {5L, 17L, 41L, 197L, 281L, 7699L, 8893L, 22039L, 24133L, 25237L, 28697L, 32353L, 37561L, 38921L, 43201L, 44683L, 55837L, 61027L, 66463L, 70241L, 86453L, 102001L, 109147L, 116533L, 119069L, 121631L, 129419L, 132059L, 263171L, 287137L, 325019L, 329401L, 333821L, 338279L, 342761L, 360979L, 379667L, 393961L, 398771L, 581921L, 642869L, 681257L, 687767L, 700897L, 754573L, 768373L, 782263L, 868151L, 935507L, 958577L, 1005551L, 1086557L, 1313041L, 1359329L, 1583293L, 1603597L, 1686239L, 1749833L, 1891889L, 2051167L, 2086159L, 2133121L, 2156813L, 2180741L, 2327399L, 2364833L, 2402537L, 2504323L, 2556187L, 2582401L, 2608699L, 3120833L, 3238237L, 3557303L, 3619807L, 3875933L, 3892271L, 3925069L, 3974497L, 4260917L, 4504663L, 4682791L, 4846279L, 4901431L, 4956893L, 4975457L, 5238847L, 5353841L, 5373133L, 5411839L, 5786369L, 6194983L, 6341509L, 6792629L, 7035851L, 7215643L, 7260961L, 7352129L, 7629497L, 7723363L, 7841507L, 8298467L, 8819087L, 9046711L, 9277559L, 9589843L, 9668761L, 9774463L, 10122583L, 10477567L, 10671137L, 10782509L, 10866521L, 11007383L, 11177987L, 11263949L, 11786759L, 11875079L, 12022789L, 12082111L, 12111829L, 12320863L, 12350911L, 12441349L, 12501809L, 12745127L, 12775691L, 12836899L, 13144939L, 13677347L, 13740599L, 13804103L, 14480027L, 14512699L, 14545409L, 14808439L, 14940979L, 15107537L, 15342473L, 15613501L, 16024483L, 16162921L, 16371569L, 16581403L, 16686853L, 16757311L, 17040973L, 17076637L, 17363261L, 17979887L, 18016477L, 18089737L, 18126431L, 18718961L, 19247401L, 19630493L, 19669019L, 20447179L, 21121091L, 21201083L, 21281203L, 21361477L, 21683951L, 21724433L, 21805547L, 22049837L, 22542739L, 23209673L, 23589143L, 23673869L, 23843797L, 23886427L, 24487103L, 24530267L, 24616667L, 24789911L, 25007461L, 25401449L, 25665929L, 27145477L, 27602411L, 27648347L, 27832487L, 27878581L, 28016999L, 28109489L, 29280487L, 29660437L, 30090637L, 30234709L, 30379093L, 30765407L, 30862373L, 31843219L, 31991989L, 33857959L, 34011707L, 34371803L, 34630291L, 34941769L, 35307017L, 35411737L, 36096149L, 36574171L, 37055309L, 37108963L, 37431617L, 37863971L, 38244601L, 38299159L, 38408407L, 38957773L, 39400667L, 39456181L, 39511721L, 40742917L, 42109763L, 42742891L, 42800701L, 43206623L, 43439621L, 44142229L, 44732153L, 45446221L, 45745769L, 46287803L, 47015497L, 47565601L, 47626949L, 48180901L, 48242629L, 48551891L, 48738029L, 50745151L, 50999083L, 51829993L, 52215799L, 52732483L, 54888679L, 55816511L, 56417357L, 57830977L, 57898697L, 59400511L, 60366437L, 61270369L, 62252287L, 62817247L, 63598313L, 63669533L, 63740881L, 64672973L, 67070449L, 67805597L, 68841029L, 69064067L, 69212951L, 70035061L, 70335203L, 71087801L, 71921429L, 72073579L, 72149731L, 73297559L, 73991461L, 74378377L, 74533339L, 74610889L, 74766137L, 76249399L, 76563413L, 77193461L, 77588689L, 77747119L, 77826409L, 79260569L, 80385421L, 82499377L, 82663159L, 86895299L, 86979311L, 88328917L, 88837591L, 89177293L, 89517599L, 90200441L, 90799757L, 91057289L, 91143203L, 91401173L, 92004763L, 94093211L, 94180781L, 94795297L, 96207019L, 98255723L, 98524553L, 98883599L, 99153311L, 99333301L, 99694073L, 100599073L, 100780543L, 100871359L, 104634823L, 106123999L, 106217393L, 108000913L, 108189619L, 109705909L, 111903541L, 113349667L, 113543293L, 113640179L, 115098101L, 115390823L, 115586131L, 117056539L, 119428427L, 120224497L, 123132109L, 124346093L, 124854151L, 124955891L, 125261387L, 125465273L, 126078089L, 128544413L, 129371371L, 130304953L, 131033471L, 131242061L, 133443139L, 134815829L, 135557971L, 135982909L, 136195603L, 137368603L, 138010963L, 139300069L, 140162839L, 140487091L, 141136999L, 143971171L, 144080723L, 144299971L, 144519449L, 144958993L, 145179007L, 145289107L, 147278359L, 148390343L, 148613159L, 149282663L, 150289277L, 150513491L, 150962387L, 152426447L, 153217567L, 153670549L, 156173153L, 156287357L, 157660753L, 159617693L, 160195547L, 161006297L, 163918837L, 165209141L, 166387453L, 166623577L, 168755527L, 168874351L, 170900501L, 171858619L, 171978649L, 174267287L, 176086403L, 177182377L, 178037479L, 178404827L, 179509597L, 179878597L, 183216587L, 183340847L, 184835347L, 185210203L, 185460283L, 186462389L, 187467563L, 188475673L, 188980871L, 189993841L, 196123969L, 197415191L, 198581371L, 198841039L, 199230907L, 199360963L, 199491049L, 199751371L, 200663531L, 204728291L, 204991859L, 206842067L, 210571709L, 212583823L, 213391169L, 213660737L, 219494903L, 221551129L, 223479259L, 223617319L, 223893629L, 224308481L, 225277951L, 225416663L, 229600727L, 230442539L, 231144983L, 232271269L, 234249047L, 234957761L, 236093443L, 236947063L, 237374509L, 239373349L, 240949759L, 242099699L, 247162249L, 248910769L, 250079551L, 252280579L, 252869249L, 254639261L, 254934947L, 255082859L, 255230831L, 257009971L, 258050549L, 260885759L, 261185117L, 264188599L, 264640709L, 265999403L, 267512897L, 272387473L, 273920659L, 275458597L, 277001423L, 277774379L, 279323501L, 280254629L, 281653859L, 282588811L, 283525591L, 283994621L, 284463979L, 284777147L, 285717967L, 287289797L, 288235177L, 289972817L, 292669343L, 293465071L, 294102287L, 294421133L, 294580679L, 296498089L, 296658149L, 296818271L, 301158691L, 302935891L, 303745423L, 304231597L, 307319381L, 308951497L, 309114907L, 310096447L, 311243663L, 312557083L, 312885889L, 314532349L, 315192287L, 318502307L, 321831997L, 323168821L, 323838341L, 326188493L, 327367067L, 327704183L, 329899481L, 330237889L, 330576523L, 331763051L, 332442247L, 337902193L, 342201257L, 342546397L, 343582639L, 344101297L, 344966591L, 345659803L, 346701269L, 346874999L, 348789607L, 350360161L, 350534903L, 351059437L, 351234391L, 351409391L, 354389381L, 354740747L, 358442701L, 364306693L, 364663573L, 366450761L, 367345967L, 368780227L, 371117203L, 371477273L, 371837483L, 372017627L, 375811291L, 376536287L, 377988643L, 378170431L, 383461619L, 386949977L, 387318179L, 392120387L, 393974591L, 394531559L, 394903043L, 395274731L, 396949703L, 397322389L, 400310117L, 401433491L, 404438767L, 405191797L, 406700369L, 409346789L, 410483797L, 411812179L, 412382231L, 412952717L, 413713829L, 414666143L, 416001083L, 417146981L, 417338111L, 418868819L, 420210473L, 423092993L, 423670777L, 425599817L, 430637521L, 433559047L, 433754179L, 434535047L, 438452099L, 441009251L, 441403247L, 442586477L, 443573857L, 444958091L, 445551803L, 447731981L, 448327499L, 449122307L, 450315967L, 453906577L, 455106761L, 458718443L, 459120569L, 464974397L, 468220019L, 474334873L, 475766791L, 478637629L, 479048447L, 479459569L, 480488291L, 481930711L, 483169177L, 483375829L, 487934417L, 488558033L, 489598009L, 490430683L, 490847263L, 491680951L, 493768661L, 496908697L, 498797093L, 499848079L, 500900497L, 502586467L, 511274513L, 511700201L, 512126033L, 514045153L, 516822751L, 517250707L, 517893067L, 519822547L, 520466641L, 520681531L, 520896451L, 525422617L, 529317739L, 529534573L, 531922933L, 535625131L, 536061467L, 536279699L, 536716259L, 539339459L, 539558351L, 541749457L, 544165277L, 545265067L, 546145933L, 548131631L, 548573537L, 548794541L, 551227993L, 557892949L, 559454447L, 559677707L, 562584073L, 563031853L, 563703911L, 564152231L, 564824987L, 567294803L, 568869527L, 570221363L, 570898117L, 571575419L, 572931091L, 573157157L, 573383249L, 578821153L, 579275701L, 587261627L, 587949121L, 589095643L, 589325047L, 593692999L, 595306721L, 600393421L, 607595491L, 614845057L, 616253311L, 616488179L, 617898469L, 620252729L, 624500621L, 624973589L, 627815711L, 628527437L, 631854109L, 639973199L, 642851189L, 644052193L, 647421787L, 651042803L, 651768053L, 652493603L, 652977467L, 654672409L, 655399607L, 656127341L, 658312397L, 661474421L, 662693243L, 667578721L, 671499839L, 681356989L, 682841723L, 683089343L, 685816403L, 687306469L, 689544481L, 690291317L, 691038571L, 691287749L, 693033599L, 693782303L, 696031331L, 698785523L, 701545337L, 704814167L, 708090661L, 708343033L, 710110861L, 714921191L, 717460607L, 717969199L, 718732519L, 719241577L, 720769711L, 721279579L, 722299951L, 722555149L, 724087037L, 729717269L, 730486927L, 736399831L, 737172923L, 744925273L, 746221013L, 747777533L, 748816421L, 749076277L, 750116221L, 754022617L, 757677337L, 760555309L, 766067999L, 768700601L, 774508919L, 776361977L, 778217393L, 779013211L, 779809351L, 781934161L, 782731811L, 782997749L, 791800447L, 793138849L, 795819781L, 796088129L, 799849301L, 800656583L, 803620859L, 806050691L, 814719379L, 821797127L, 822615593L, 824526601L, 828081209L, 830821003L, 832467193L, 834115127L, 836865053L, 837415637L, 842933027L, 846252377L, 848468779L, 849855299L, 852632411L, 853744909L, 861274663L, 870805259L, 871086367L, 876435293L, 879540073L, 880670341L, 881235743L, 884066087L, 884916041L, 885199409L, 885482813L, 889455121L, 894861029L, 902002349L, 905729557L, 923618093L, 926230717L, 926521289L, 927975053L, 929138803L, 929429827L, 930594281L, 930885517L, 937888673L, 946681067L, 947856751L, 953746357L, 955516759L, 956402597L, 956993371L, 957879883L, 959949917L, 963505457L, 968852233L, 969447251L, 971531369L, 971829251L, 979588553L, 980186593L, 982281049L, 983179501L, 987077639L, 988578947L, 989480231L, 989780717L, 994294333L, 995499893L, 995801441L, 1012758353L, 1013062409L, 1013366489L, 1014887639L, 1015192039L, 1015800941L, 1016410037L, 1023123043L, 1028325433L, 1032006737L, 1037233559L, 1041857501L, 1053309073L, 1057970453L, 1060772099L, 1063264859L, 1063576637L, 1064512529L, 1066385959L, 1074840517L, 1076096251L, 1082069957L, 1083014507L, 1088375741L, 1091219887L, 1099777697L, 1102002449L, 1105185337L, 1105822547L, 1107097561L, 1114122173L, 1117642451L, 1127595589L, 1134363577L, 1135009361L, 1137917597L, 1139534999L, 1146341333L, 1146666113L, 1152519773L, 1153822363L, 1156429601L, 1157408207L, 1175754791L, 1177399919L, 1182343651L, 1183003847L, 1192599217L, 1206905143L, 1207906501L, 1212918947L, 1215261533L, 1216936121L, 1219953887L, 1220289443L, 1220625053L, 1221968117L, 1222975981L, 1224320509L, 1224656779L, 1230044801L, 1234770659L, 1237814113L, 1238490989L, 1243912739L, 1247307449L, 1247986931L, 1249346393L, 1253088857L, 1257859279L, 1258882717L, 1260589483L, 1267769983L, 1276003979L, 1276347613L, 1280130799L, 1281508103L, 1282886039L, 1283575277L, 1284954263L, 1291859753L, 1292897153L, 1301561101L, 1306426697L, 1309210967L, 1317581813L, 1329843661L, 1334415037L, 1335118963L, 1337231659L, 1337583941L, 1343225869L, 1344990979L, 1345697251L, 1349584997L, 1351000163L, 1358798431L, 1372330021L, 1373044103L, 1376974559L, 1379120797L, 1383059231L, 1386644737L, 1387003537L, 1387362377L, 1393109189L, 1393468717L, 1402471229L, 1403914159L, 1408609591L, 1411142261L, 1417305391L, 1427124571L, 1428217421L, 1431133801L, 1434783793L, 1437706681L, 1440266777L, 1440632663L, 1447228039L, 1448328779L, 1452000293L, 1456413373L, 1463414917L, 1468955039L, 1486011041L, 1490847551L, 1494945587L, 1498303663L, 1500170869L, 1501291697L, 1515151091L, 1516653433L, 1517780777L, 1520789201L, 1521165551L, 1525685641L, 1529080367L, 1529835233L, 1533612403L, 1533990343L, 1535124473L, 1535502601L, 1536637523L, 1537772917L, 1540044967L, 1543076449L, 1549147867L, 1554090179L, 1561330259L, 1568587271L, 1574330011L, 1579315151L, 1580466793L, 1581234841L, 1596248081L, 1598563819L, 1599336043L, 1607844727L, 1608619421L, 1609394363L, 1611332347L, 1619484221L, 1654285639L, 1654678939L, 1657039513L, 1658220521L, 1658614273L, 1659401927L, 1672030637L, 1682723633L, 1685104543L, 1691064257L, 1696636171L, 1704614707L, 1708610903L, 1709010767L, 1713412709L, 1715014949L, 1717018741L, 1720227869L, 1722637249L, 1725852473L, 1728668479L, 1735114847L, 1735921501L, 1754929289L, 1755740629L, 1756958033L, 1758581833L, 1760206451L, 1779357397L, 1779766117L, 1783037293L, 1784674019L, 1790409541L, 1796154761L, 1797387209L, 1802731429L, 1803142853L, 1817161343L, 1817574389L, 1825433647L, 1838709331L, 1842867601L, 1843699811L, 1850364193L, 1867915939L, 1873365281L, 1874204351L, 1882604501L, 1883024939L, 1903685291L, 1904954011L, 1906223191L, 1907916163L, 1912151671L, 1920213401L, 1931705299L, 1936824079L, 1940667853L, 1944944047L, 1947511939L, 1949652893L, 1952652407L, 1961235721L, 1968546911L, 1972423969L, 1975442237L, 1985810797L, 1987541917L, 1996644173L, 1997078137L, 2003593897L, 2014912297L, 2016656959L, 2029767007L, 2030204699L, 2030642429L, 2039846141L, 2041162801L, 2045994127L, 2051709937L, 2058755357L, 2059196147L, 2060518769L, 2066697467L, 2078196847L, 2079969011L, 2081298679L, 2094173819L, 2094618503L, 2095063213L, 2100849713L, 2101740863L, 2118705781L, 2119153159L, 2122286423L, 2130355211L, 2139788533L, 2140688141L, 2142937949L, 2149694497L, 2150145253L, 2156461477L, 2158719481L, 2165048701L, 2168217187L, 2174561677L, 2185461637L, 2187281143L, 2189101223L, 2195020829L, 2196388459L, 2202320839L, 2220162881L, 2222913839L, 2224748831L, 2225207687L, 2239913869L, 2246822819L, 2254666237L, 2256051907L, 2276427421L, 2277355841L, 2279213353L, 2283396617L, 2284326769L, 2288049409L, 2301105803L, 2303909291L, 2309522297L, 2328282863L, 2328752807L, 2343346981L, 2345233991L, 2350900423L, 2361309149L, 2366048393L, 2366522573L, 2373166349L, 2375542333L, 2383154311L, 2385535483L, 2386488199L, 2395547831L, 2398412543L, 2404625341L, 2407974521L, 2420435263L, 2427638623L, 2428599917L, 2431966183L, 2440152151L, 2456565511L, 2458983701L, 2461886741L, 2462854703L, 2466728933L, 2484203443L, 2501744909L, 2502233159L, 2503698139L, 2507606831L, 2510050957L, 2517879251L, 2520817811L, 2522778043L, 2524739167L, 2530627741L, 2542425517L, 2543902393L, 2545872113L, 2547349837L, 2572044581L, 2577494027L, 2580468841L, 2580964831L, 2582453033L, 2585430451L, 2594869819L, 2596361767L, 2606817041L, 2607813931L, 2614298647L, 2620791527L, 2623291039L, 2632801891L, 2641832393L, 2642836667L, 2644845769L, 2655907277L, 2669010361L, 2670019657L, 2673048743L, 2675574533L, 2676585313L, 2677090771L, 2677596269L, 2679618857L, 2686704301L, 2688224411L, 2697352939L, 2703954257L, 2719732133L, 2720751799L, 2744764417L, 2750399243L, 2757580559L, 2767859099L, 2773006213L, 2774036173L, 2779189417L, 2788995071L, 2799852317L, 2813842667L, 2818514917L, 2821631713L, 2822151349L, 2823710563L, 2824230443L, 2830993511L, 2836202491L, 2848723931L, 2851336549L, 2851859233L, 2854996381L, 2857612111L, 2861799581L, 2870185693L, 2872808899L, 2880685849L, 2885417419L, 2899110091L, 2906496577L, 2912834867L, 2916006829L, 2919710207L, 2920768777L, 2937201151L, 2938262911L, 2941980511L, 2944106059L, 2946764089L, 2952083759L, 2972876789L, 2973945199L, 2977686143L, 2983569023L, 2991062339L, 3005538007L, 3006075043L, 3017363887L, 3029210363L, 3031366717L, 3039460817L, 3041621437L, 3054059131L, 3076294027L, 3084994657L, 3087172043L, 3087716473L, 3089350009L, 3097522873L, 3098613487L, 3102432479L, 3104070029L, 3105707953L, 3109531199L, 3118280609L, 3127593809L, 3129238729L, 3135822611L, 3141865651L, 3145713913L, 3152316311L, 3153417451L, 3154518791L, 3155620343L, 3167197441L, 3169957079L, 3170509109L, 3173822153L, 3180453607L, 3185431687L, 3185985067L, 3189306577L, 3189860293L, 3197063369L, 3197617823L, 3202055287L, 3204275563L, 3212608319L, 3215945023L, 3216501313L, 3219283423L, 3222623773L, 3225408943L, 3232655243L, 3239909597L, 3244378847L, 3245496769L, 3252767633L, 3253327303L, 3257246617L, 3258927083L, 3267336329L, 3268458503L, 3276318211L, 3278565473L, 3282499663L, 3285874063L, 3288124507L, 3288687217L, 3290375663L, 3300515951L, 3311799137L, 3315753043L, 3323669023L, 3329329151L, 3332160841L, 3334427557L, 3346342919L, 3370237183L, 3380502161L, 3394787261L, 3395931433L, 3403948693L, 3406240997L, 3409107473L, 3414270287L, 3424609543L, 3436119221L, 3437271557L, 3439577083L, 3452271611L, 3475990003L, 3488750479L, 3490492549L, 3496883447L, 3506770937L, 3510264127L, 3514924519L, 3515507263L, 3528925459L, 3529509523L, 3540616813L, 3543542801L, 3568173289L, 3572876441L, 3580525651L, 3583469353L, 3591719519L, 3602931529L, 3605885149L, 3607066921L, 3612980353L, 3618306521L, 3627784903L, 3633122497L, 3647373871L, 3648562889L, 3655702073L, 3658678769L, 3661656923L, 3662848523L, 3665232359L, 3668213293L, 3677163697L, 3688518619L, 3693305639L, 3695700457L, 3709486013L, 3717890993L, 3720294157L, 3724501687L, 3728109901L, 3735932693L, 3744366641L, 3750396823L, 3752810209L, 3755828129L, 3756431873L, 3758243351L, 3763076341L, 3775781293L, 3786688441L, 3796396319L, 3797003423L, 3800039543L, 3813412793L, 3815846959L, 3823763077L, 3831077249L, 3839007737L, 3841449721L, 3846946993L, 3853670599L, 3857340601L, 3858564379L, 3861624959L, 3883083173L, 3891682901L, 3895371187L, 3897831233L, 3901522819L, 3913227431L, 3915077351L, 3916927811L, 3934220753L, 3939787253L, 3942262573L, 3947834567L, 3950312351L, 3951551563L, 3953410829L, 3955270703L, 3957131081L, 3961473821L, 3964577471L, 3965198357L, 3967061257L, 3975138949L, 3981358111L, 3981980371L, 3983847443L, 3988828637L, 3990697619L, 3996307327L, 4011912413L, 4018162571L, 4021289443L, 4023791831L, 4033809821L, 4038823387L, 4045095121L, 4059537019L, 4062679637L, 4102390219L, 4115672237L, 4117571413L, 4120104437L, 4120737809L, 4123905259L, 4128975421L, 4134048731L, 4142299913L, 4149923587L, 4154373637L, 4157553721L, 4169012161L, 4171560643L, 4190698313L, 4197726019L, 4198365163L, 4199643551L, 4209238021L, 4223328283L, 4228458149L, 4229741129L, 4246439611L, 4252870957L, 4260595303L, 4268971079L, 4276710463L, 4286394649L, 4288332901L, 4294797491L, 4295444249L, 4304504297L, 4314224021L, 4316817863L, 4320061423L, 4321359157L, 4322008057L, 4329148973L, 4340845937L, 4357768687L, 4359071737L, 4364937763L, 4378642157L, 4381908571L, 4397606063L, 4398260743L, 4400880023L, 4402189907L, 4402844891L, 4409396963L, 4419233837L, 4422515147L, 4423828187L, 4431053131L, 4433024821L, 4440916261L, 4454085803L, 4470575449L, 4476519011L, 4480483453L, 4487095469L, 4497684761L, 4503647201L, 4516910807L, 4532853491L, 4562161979L, 4566833527L, 4568836249L, 4579526543L, 4592908409L, 4600946969L, 4606980089L, 4609662991L, 4617716767L, 4618388239L, 4623090067L, 4623761977L, 4627122641L, 4628467213L, 4667543789L, 4674298007L, 4677676859L, 4679028707L, 4681733333L, 4682409653L, 4696620587L, 4697297777L, 4701362441L, 4724436091L, 4735997051L, 4744848491L, 4766671171L, 4794021971L, 4799501279L, 4809784561L, 4815274511L, 4818020671L, 4818707293L, 4821454207L, 4835200813L, 4848967589L, 4855169261L, 4861375457L, 4869656063L, 4898700047L, 4901470727L, 4903549097L, 4919496821L, 4925744933L, 4950082129L, 4957047091L, 4962622429L, 4968200849L, 4976575259L, 4978670069L, 4981463891L, 4987752851L, 4994745103L, 5004542597L, 5011547279L, 5024871641L, 5031189217L, 5036105257L, 5043835271L, 5062835353L, 5079048259L, 5086811683L, 5088223909L, 5091048923L, 5092461679L, 5117928701L, 5125722577L, 5128557883L, 5147007101L, 5159799179L, 5161221473L, 5176881197L, 5181869761L, 5187574493L, 5193283577L, 5195425399L, 5206856269L, 5210431381L, 5223309829L, 5232621997L, 5234055269L, 5238356551L, 5241942413L, 5242659749L, 5243377121L, 5248399747L, 5253424531L, 5258451511L, 5259169831L, 5259888209L, 5270669819L, 5272827481L, 5282184067L, 5285785867L, 5300929481L, 5308872511L, 5314653481L, 5331290537L, 5337083371L, 5345053471L, 5386454257L, 5396647681L, 5397376219L, 5409038821L, 5414145173L, 5418524261L, 5439714187L, 5441908513L, 5463145033L, 5489564453L, 5504269777L, 5505005497L, 5514575389L, 5516784997L, 5518995137L, 5527103383L, 5527840849L, 5535218501L, 5540386373L, 5561828803L, 5571456139L, 5573679103L, 5593708811L, 5594451413L, 5596679411L, 5608570777L, 5611546103L, 5618987707L, 5620476751L, 5625689621L, 5636123107L, 5659258481L, 5660005609L, 5662247441L, 5664489751L, 5668976297L, 5675709283L, 5686190621L, 5711686237L, 5715439573L, 5719945211L, 5721447419L, 5752290449L, 5755304279L, 5781708719L, 5790776707L, 5791532771L, 5793801379L, 5795314009L, 5802880253L, 5815755119L, 5816512939L, 5820302681L, 5822577091L, 5824851917L, 5839269889L, 5858268167L, 5859028757L, 5862071489L, 5864354129L, 5867398441L, 5896364171L, 5899417411L, 5900944349L, 5918521267L, 5920051297L, 5921581507L, 5926938559L, 5943789937L, 5952992611L, 5955294413L, 5956061753L, 5976029237L, 5978335117L, 5999879759L, 6004501751L, 6005272279L, 6016836101L, 6018378689L, 6032272391L, 6033817037L, 6046954409L, 6047727641L, 6053915177L, 6060881243L, 6067851403L, 6068626171L, 6075601949L, 6092673467L, 6098110607L, 6103550581L, 6130009631L, 6130788731L, 6141701107L, 6145600607L, 6154964051L, 6156525371L, 6167458841L, 6170584669L, 6172929463L, 6176056637L, 6187790447L, 6197969053L, 6200319337L, 6212861519L, 6218352391L, 6235623349L, 6237194693L, 6238766173L, 6241123783L, 6245053993L, 6267871361L, 6269446297L, 6274960411L, 6287574043L, 6327869371L, 6331035587L, 6336578993L, 6337371133L, 6341332663L, 6343710187L, 6354811273L, 6365129087L, 6384996781L, 6386587651L, 6428018381L, 6428816507L, 6439196059L, 6449584201L, 6453581663L, 6456780641L, 6466382693L, 6471987107L, 6476793269L, 6478395839L, 6484808303L, 6535433959L, 6537849931L, 6585463033L, 6612176089L, 6623527481L, 6624338687L, 6647071633L, 6650322733L, 6651135713L, 6652761751L, 6655201099L, 6660080941L, 6664963183L, 6667405369L, 6675549787L, 6681253399L, 6690221281L, 6717159719L, 6731876383L, 6734330699L, 6743334527L, 6750705679L, 6778588429L, 6781051351L, 6788442877L, 6794194741L, 6805706477L, 6813935731L, 6831232019L, 6844423493L, 6859281967L, 6863412767L, 6872504657L, 6875812939L, 6876640123L, 6881604629L, 6887399039L, 6892367843L, 6893196131L, 6901481819L, 6904797329L, 6905626319L, 6908942857L, 6916407457L, 6933007883L, 6938823211L, 6957947897L, 6958779991L, 6967937143L, 6976266623L, 6981267049L, 6999621137L, 7009642847L, 7017999493L, 7024688107L, 7033890109L, 7048961537L, 7050637019L, 7074115303L, 7075793693L, 7080830221L, 7089228919L, 7101837823L, 7103519749L, 7107725497L, 7115299487L, 7128774959L, 7129617647L, 7134674803L, 7136360873L, 7140577331L, 7144794661L, 7155767183L, 7165058011L, 7165902949L, 7168438273L, 7182814031L, 7203979199L, 7205673653L, 7224326771L, 7231964099L, 7241304949L, 7245552869L, 7259154211L, 7263407387L, 7268512763L, 7273620121L, 7277878291L, 7280433613L, 7300896223L, 7301749627L, 7306017119L, 7311139601L, 7317118051L, 7322244661L, 7325663417L, 7355611771L, 7374469703L, 7387343947L, 7390779059L, 7397651137L, 7404525829L, 7432055921L, 7436362979L, 7449289751L, 7458775847L, 7463952593L, 7473448679L, 7476903341L, 7492457537L, 7502835187L, 7519280941L, 7552225763L, 7556566331L, 7576548403L, 7581765727L, 7627922807L, 7647997703L, 7678601629L, 7684730447L, 7685606237L, 7696997569L, 7718929919L, 7721563853L, 7722441997L, 7725955267L, 7730348293L, 7740896929L, 7744414679L, 7765537333L, 7774346911L, 7784924671L, 7788452333L, 7805219311L, 7807868597L, 7815819419L, 7824658823L, 7827311647L, 7845007879L, 7845893281L, 7848549767L, 7850320921L, 7852977901L, 7856521339L, 7860951601L, 7863610283L, 7867155707L, 7874248457L, 7875135277L, 7885780681L, 7892881723L, 7915980791L, 7927542647L, 7947128317L, 7978345987L, 7995322507L, 8014109869L, 8015900441L, 8022169277L, 8039197249L, 8064330779L, 8076012899L, 8076911831L, 8078710043L, 8079609179L, 8092202567L, 8094902489L, 8095802537L, 8124628079L, 8131841573L, 8135449183L, 8142667171L, 8155307767L, 8156211097L, 8164342817L, 8205975859L, 8237736809L, 8243188073L, 8245005557L, 8268654001L, 8278669963L, 8285957473L, 8297806123L, 8300541817L, 8314227359L, 8325184729L, 8343462707L, 8348035363L, 8350779539L, 8359014533L, 8359929827L, 8370001463L, 8381913979L, 8404849927L, 8434253281L, 8450819471L, 8461873967L, 8497851899L, 8505243053L, 8518186793L, 8525587757L, 8538546773L, 8540399159L, 8545031393L, 8555226059L, 8556153113L, 8562644147L, 8564499191L, 8617447537L, 8632336409L, 8634198611L, 8641649921L, 8666823983L, 8669623643L, 8679893809L, 8682696083L, 8707002407L, 8712615673L, 8726656241L, 8733212113L, 8742582581L, 8749144289L, 8753832587L, 8769782977L, 8790448327L, 8793268387L, 8802671777L, 8822432789L, 8823374269L, 8834676239L, 8870514637L, 8886570821L, 8899805641L, 8906427199L, 8907373457L, 8909266103L, 8910212491L, 8913051877L, 8920625899L, 8924413921L, 8928202571L, 8941470613L, 8981332291L, 8988935377L, 9004150499L, 9009859193L, 9014617529L, 9020328833L, 9031756333L, 9038426153L, 9047005567L, 9066086767L, 9089972201L, 9127297103L, 9133045639L, 9134962373L, 9139754941L, 9200254339L, 9206989249L, 9220465691L, 9275441891L, 9296705771L, 9305411911L, 9318962603L, 9335431207L, 9338339117L, 9379114529L, 9399541117L, 9404407603L, 9466810693L, 9491240443L, 9494174153L, 9496130227L, 9498086551L, 9501999809L, 9548042573L, 9555890969L, 9563742413L, 9590266883L, 9603050687L, 9620766721L, 9629632367L, 9632588443L, 9647376527L, 9650335451L, 9667110727L, 9679949567L, 9695763089L, 9696751853L, 9698729501L, 9701696491L, 9711589457L, 9712578937L, 9716537273L, 9766085221L, 9772039159L, 9788919809L, 9795875839L, 9801840187L, 9805817393L, 9807806419L, 9820739429L, 9842644843L, 9856599229L, 9864577753L, 9872559497L, 9882541219L, 9894525617L, 9912515209L, 9925518269L, 9932523199L, 9941533289L, 9943536173L, 9954555593L, 9997689707L, 10005726611L, 10010751809L, 10021811893L, 10023823553L, 10041940087L, 10046975531L, 10051004773L, 10058058113L, 10071163367L, 10083268229L, 10088314333L, 10090333091L, 10093361879L, 10101440621L, 10103460761L, 10106491201L, 10112553149L, 10127715553L, 10131760627L, 10138841227L, 10145925001L, 10172260391L, 10185440803L, 10206751843L, 10212845231L, 10219956641L, 10238255113L, 10245375641L, 10246393139L, 10249446043L, 10255553167L, 10259625451L, 10263698759L, 10264717261L, 10296315847L, 10301416691L, 10306518731L, 10332049633L, 10350453229L, 10375015711L, 10396537457L, 10400639393L, 10408845637L, 10435536401L, 10446839567L, 10470493193L, 10472551319L, 10496234953L, 10500357337L, 10505511707L, 10528207489L, 10541630207L, 10545761711L, 10548860821L, 10555060277L, 10568498389L, 10570566563L, 10576772179L, 10579875569L, 10580910097L, 10581944663L, 10596433531L, 10638921659L, 10640996627L, 10643071693L, 10644109297L, 10645146913L, 10672144891L, 10677340679L, 10685656763L, 10689816139L, 10693976273L, 10702299473L, 10707503173L, 10729372847L, 10739795189L, 10743965599L, 10748136689L, 10769003533L, 10772135159L, 10778400011L, 10783622119L, 10794069919L, 10830680207L, 10870504433L, 10884147539L, 10910406889L, 10928280763L, 10938801529L, 10940906269L, 10945116319L, 10946168923L, 10960911293L, 10981987363L, 11008362179L, 11063334703L, 11064393247L, 11076040919L, 11121634157L, 11122695569L, 11139684709L, 11142871757L, 11164132897L, 11175836263L, 11196066031L, 11208851413L, 11218445479L, 11237646241L, 11239781029L, 11248322177L, 11262207547L, 11269687817L, 11273963651L, 11317844203L, 11325345641L, 11327489447L, 11340356239L, 11343573919L, 11352156509L, 11368256891L, 11372552053L, 11382218429L, 11384367031L, 11429544649L, 11464029089L, 11474816189L, 11480212127L, 11481291467L, 11509375391L, 11527757147L, 11542907731L, 11611209733L, 11614467407L, 11640544709L, 11642719181L, 11667738763L, 11687341381L, 11688430981L, 11699329711L, 11724419101L, 11732060917L, 11737520863L, 11738613001L, 11745166841L, 11756094023L, 11757187139L, 11788911479L, 11816294977L, 11821775951L, 11854689071L, 11867866397L, 11878853281L, 11911844531L, 11939374121L, 11942679787L, 11955906527L, 12013312639L, 12019946149L, 12035431493L, 12043178083L, 12060893513L, 12088600427L, 12100803037L, 12110790569L};
  13.         long n = inpi();
  14.         if(n < 5)
  15.             out.println(0);
  16.         else
  17.         {
  18.         int x = Arrays.binarySearch(arr, n);
  19.         if(x >= 0)
  20.         {
  21.             out.println(x + 1);
  22.         }
  23.         else
  24.         {
  25.             out.println(Math.abs(x + 1));
  26.         }
  27.         }
  28.     }
  29.  //use this to generate the range if needed for testing. else not used in program code
  30.     void solveforN() {
  31.         long sum = 2;
  32.         ArrayList<Long> list = new ArrayList<>();
  33.         for(int i = 3; i < 555000; i++)
  34.         {
  35.             if(isPrime(i))
  36.             {
  37.                 sum += i;
  38.                 if(isPrime(sum))
  39.                 {
  40.                     System.out.print(sum+"L, ");
  41.                     list.add(sum);
  42.                 }
  43.             }
  44.         }
  45.         System.out.println(list.size());
  46.     }
  47.  
  48.     public boolean isPrime(long n) {
  49.         return BigInteger.valueOf(n).isProbablePrime(5);
  50.     }
  51.     //------------> Solution 
  52.     InputStream obj;
  53.     PrintWriter out;
  54.     String check = "";
  55.  
  56.     public static void main(String[] args) throws IOException {
  57.         new UNICOURS().main1();
  58.     }
  59.  
  60.     void main1() throws IOException {
  61.         out = new PrintWriter(System.out);
  62.         obj = check.isEmpty() ? System.in : new ByteArrayInputStream(check.getBytes());
  63.         solve();
  64.         out.flush();
  65.         out.close();
  66.     }
  67.     byte inbuffer[] = new byte[1024];
  68.     int lenbuffer = 0, ptrbuffer = 0;
  69.  
  70.     int readByte() {
  71.         if (lenbuffer == -1) {
  72.             throw new InputMismatchException();
  73.         }
  74.         if (ptrbuffer >= lenbuffer) {
  75.             ptrbuffer = 0;
  76.             try {
  77.                 lenbuffer = obj.read(inbuffer);
  78.             } catch (IOException e) {
  79.                 throw new InputMismatchException();
  80.             }
  81.         }
  82.         if (lenbuffer <= 0) {
  83.             return -1;
  84.         }
  85.         return inbuffer[ptrbuffer++];
  86.     }
  87.  
  88.     boolean isSpaceChar(int c) {
  89.         return (!(c >= 33 && c <= 126));
  90.     }
  91.  
  92.     int skip() {
  93.         int b;
  94.         while ((b = readByte()) != -1 && isSpaceChar(b));
  95.         return b;
  96.     }
  97.  
  98.     String inps() {
  99.         int b = skip();
  100.         StringBuilder sb = new StringBuilder();
  101.         while (!(isSpaceChar(b))) {
  102.             sb.appendCodePoint(b);
  103.             b = readByte();
  104.         }
  105.         return sb.toString();
  106.     }
  107.  
  108.     int inpi() {
  109.         int num = 0, b;
  110.         boolean minus = false;
  111.         while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
  112.         if (b == '-') {
  113.             minus = true;
  114.             b = readByte();
  115.         }
  116.         while (true) {
  117.             if (b >= '0' && b <= '9') {
  118.                 num = num * 10 + (b - '0');
  119.             } else {
  120.                 return minus ? -num : num;
  121.             }
  122.             b = readByte();
  123.         }
  124.     }
  125.  
  126.     long inpl() {
  127.         long num = 0;
  128.         int b;
  129.         boolean minus = false;
  130.         while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
  131.         if (b == '-') {
  132.             minus = true;
  133.             b = readByte();
  134.         }
  135.         while (true) {
  136.             if (b >= '0' && b <= '9') {
  137.                 num = num * 10 + (b - '0');
  138.             } else {
  139.                 return minus ? -num : num;
  140.             }
  141.             b = readByte();
  142.         }
  143.     }
  144. }
  145.  
Success #stdin #stdout 0.06s 4386816KB
comments (?)
stdin
copy 
1011223211
stdout
copy 
802
https://ideone.com/wNA761
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!