Problem:


Score : 400 points

Problem Statement

We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.

You are given Q queries.

In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.

Sample Input 1

1
3 7

Sample Output 1

2

3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.

5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.

7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.

Thus, the response to the first query should be 2.

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

6
1 53
13 91
37 55
19 51
73 91
13 49

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Accepted

Solution code:
q=int(input())
l=[]
for i in range(q):
  l.append(list(map(int,input().split())))

prime = 20004431578450209924122229157546428808229338876349363337712943556090125072384871497695345072489101393547267891759735666839929207695180917301865873794525122225182211506209763555542487868921815027723989950182220595606019802924850644626598293997281041153041196718955950385756366976651806643001670880273285886653359815793252908149930220705736800279927272581947704503288135153151299836388868731102639526367859455618586209502648255289943588285697456832282180927287990706936716130610792327350165304941421061693327876648898509481393922838454847678310279130911072847584981735380414481264878427722160441259018780537636967669631407018960811146625900578579187643251553438517531747779193346659938961128847389313292814395447314866129728588377716953291488170774298539361268664112855266648908496219201074550876763432996445803007965315787039361356304535160562539056529998026822261111120422883047092293138589313989108183887219720953080504917392155286760811782618238370113134123220938932092931620728841185227087188799115091534479460557917471787498301931376520921825009265509258240436095168723509749161435339378135657430420799467932065407670955512546932492449343665155862941831161973845936044595731007014129633197853345693750614145477115164082236149014781000170072814093094518207225420445018008567287369969819609902831125362501627425077734193271841946347409603319195604400303495629786093793181682057666502395934996661997671616803110560574021357820743397942472865237346931305299970807121973933223942532800682621271705834567161266884439599669406824199048484368831423214427338944584681166447421449536820877233336043323789998747423016759265899197638201619840220513795198538752922319881601626249154911019418947082459528415405869550958527510913061601131916920260935784569084266870085662335783984759698039161979318181152557935904767777847530076788249104015137566567115764057439656610762935409531774590290338759540701992966308841103298883242629051581082670587575758203352796606763778243868323259731030733987734702452716016016263623849253651977591556238789878592540584660051762130513404060700776809078156663827396589715960702323947484531225153774196427901165792646050553046195854756189395198789568842730507237598682453070974706804170825990619088672558750956678423394742172499922299923814796807911818787366383773763031785326540342816768810644058480075953968266934828614022856553181824228267365747647741453175881112245735621924152508595145913822736952077857501160096776801888012639160504533012171834125729859068177381613631150221077060458082196956074837658463238206771974999664491011118955053921303639486377514228772042276694418998772086595583755779684171443884723559151996743996002589106945562955935322684870458963094859134882269154719102838657784634890481648973621637351446093186792912477935774687908381404831707616782251924711538266638018614227700185430800142748371479675316878479428478484609981575534970167389590679730120764785951910756324290653523389496216390580916648625894666198778618770318423344982110714948586522716524855939828214788056238244173729138693407870797830595152853904650996937626621286140481153694958384661549904265573078566218911348948630566103607653880738122325230732229484494892855659221904207632855042153976651456425366315813260642041216082928355188596201972339334994818600591532087276388124539150770306759178269075370433860332169553114971095396904762378414083289873863193690563311469765338916731838327262613881668693042273858902340235551399208433711313369864335505505352004068156128947513073001142547072314921608427116791068838137718799163474756715954520025257876632773908145201983916649330987719345772652716812553131870759596119645171624325894205716268346789913416934314684647100665375208577150954304058192263972329897503546533683534301264910242561187780676891123403137615941984528124312559156581568518583382486253998799887924447799587527522534887667864988527869796360498899903938708384161863226531092480925609621114903822065765209218481861769707520378842080240334963366424996646533613505231161188712642932897082579958265905868662782657941523629955794932203776085611087882885849137467632364378470063602943428071697275354992378421530165984910225647010541792398905558121817066410336193091441027039423363397515681374867820446044382128091749816961347943541999729114490782652767466519679393195962566493568876820220539645729595605430445918622275212508446323011514669810886559233565976781813179581375773837566545847736601430068292968383122625019519868108162738262802904733262054042531780614101549623390426497716343143734434256597210708235286556389658785172851816488376374518971347156772016762154464767041962560547194180641523668073413724790426651315048025217400732965735903730330430826437510973679888184166871352558254142054712362051405353973312606634506544285107519065487199921951542535815330000366060485485172511153357851832503510385994614494677229681049757560307330437444801121741151557476886219443733852384976968295562797145796518190834247372391177209368182456334363656746636625651498272468613728269412256227007491352537129410675018216828425405368725562962712790529218805176381574598106420897288853047766100559436275337803826768081307712274498840938710557795310143082691040760450993256863822351585112665946574364916505339393713913625842742120297077507298004416668982729223354833480568205912680446270382288507531724937951054476119699796534118991218590426003436735467381529072094361356488682254018899186934429196341775815871221412344971506688310180211946709365729289690977156444688541026134634464141606314398381725986770937515475351159357306010592653975369278993500837310077150194871503079402114485311966987637258629412825254420334351996647626412455256454242345706050026149661929302704669172767015698750353381447528368563954100750226399095237610021823944262513132588177821819799821800790207704836639548767368413104483860913075523780690310207654536460533280908065458227315539807853109206819439561719266731615848979298119869578061104417789504704015525084679112412937229538067615582049344322424866843058598934638388914093252871244193681901251273884589611884273058166022223571112664184318356997136754942659694142254897526534390848113654886135628679228726266763939900272856635536628387471217690696145590313184748136687863105319047308687559865390785687247976540354993058685138236022274144128059675202071676261173059652810311498903907350054667645299341171173143562989126374374118921425635551228390274700457949460143349705877914790819541629521335975176404811045467314058935630078387853966244995573810375001474510421730711063364189694691199567632324306284681784372623215761556142050907507371978727516945354053074583805065344707547246263939789131057903938781872322904489578565582312861362510872372347738081628102089282120720456139765962942568321382885852413904357109540668927634140023895194940078736444829269201666737233093936148395885986384827227282180401293144554432022093572313098453949160982123476130697446741102121966399852205870772281994319053343887332968029455552380478196052391618967560996178686861414946820079160711855674856823944799082061686169330553987004478802965510590634211966489929418846463772813252330337564073318189878980672966795258014587458993106124680580235237591444167236812686361127859368842446307741351827020921609557006334737278670938638433861334999778861527095464904135401149549593912424200095744124560062704001484280890517233322780921856946860561208980814054623060360189680864444296344728781363630831479512962495994503769681739638973999614614251383081271333720024029195258414412003446862471989135985681620333133325156264098786331401726094154334384562798432526757256576759891838213314532920013095928409445068210788847814598185933537015682877286040836261078773006079054101267548918394535837380696717690210948151738706654220868425712210739873400731576861219217953321976071941973091043973036239760079091530574416389277901404332027630958422561744893098697843478437987208852454224408246705120606642718149145352845542735945618431674192953355399941188911793768228716381068930328567392399395857434006750304184357230908540498647063675717083814596897567489935942725901742952492658090453055589348335879255064198208799001943743792144437746802363605401650871040442247410497971388374883102031745463252120630231413789938613748237456102797612693992482497367232501394695567041547553767593328754647825975776326569016381192870681677606744413417075703077242622496786927241453987401049968015657566637863079316921496492108670830967923373334317564622255685812883907370202310739088964126348209244632629660211486549455945565777401556245313614799355128509790898944933231529027055218501761590170006852776336238673276473003865528913510870167104678843185476705615199079603923345906701314803262865115746870278597174268414041349908293535716783108674784215912348724003608561793689323209839428094438588590694321357187779281999906393041766166450709390837450632898756100298045863251575702914330058248321274954797031211904382252953874210533827889990385625994859892627242402033456041578518061076247767117188838595070935262773488290181548247829757203849576603867383449886110463662339719064473555204314057526420720334998427581421310270220287176050305369518715971602594535217850075666652536071778190142081088314026858101031414761709121765165907054420850605249140361339145556234129622528103720996325783475340086067432578255892928368969397181042150229681805170821781033941446967770035281392610199402199083843320147785203094333068031715304404734790508093759854446562445863006280619457543953516198163285361411452704613819405474489702823281166980224275989062717375285375447477756752793682611960906058355371527685280556507946088975527858506829718513008114696241854957145815944829754429796654809585490366953440183757825877351428729941894422146747458727693810345456866086266010174113192779119121942377767898928656379160735857404041714060603478030738968673525440766888331428019547826319239063873405448736131662252900941622856254158717486765909918803647545023264188171079275465826314683497376385455726479529954106490612956489373298880410824439381162389990089361975435346017712795560193262302359481228817605506330069171794627837732339693995375439064110339957480276278921624587020862542964652060539727479327278079642733266086800905149340822822115143893376281285192309686327027747516029746136832865610590129622162206240271623203156075905654580983461126369793225377674172259556072872984458431810721721355471487958629095709908274169449218733546791654215337558406896390824151665460392820089998204076676543926604183351277806954189574655760574083740673410906647167467298879704498949804409365373614959220565900431246202562816530769128741874632121287225821359370879873199548057723155540569447748698874208964560515392627004788185357384777836474788614448561029507578746827858145113758461611425228437164934386205704868240600034606038922348180206443665345055508201763255404197919528207985198216655444161030863114365634440228042000798788750991868427481982199052014609517872050379437051612707053988049957223281311639113766366369178363393867208333323795426458850588022810015281434602619790587473937492814586828325291857180636231575893439139184643156210152072270068546118501622538399594772988009163036416125856957050409861359354883673867287295186039430939327676146225026161857841488301797129743455671567894442953762938592394658089118744661107137778611901215803797724341965170349383162230378647871093140066858030962412799847247523666962291256376800050972637418798418864145301553146188349392171401668346885716907367074593221841258466875406896898046136334284303974165456825010155417283624323885742817342380155685032304308983543885800108054845202926885953769095671103826897831044825833812228160080314453193523979776506202461548533374804540379280435742484899996580127894133019791670309076399605642769703698240980218808506043775832586007982126761685703607605619443721985935688677804356350970252413323487427399971865463946990243395843510269000757328122706427590064997859563576036805497946667709639656510928202906902092153244946691959316291051751144748375245485305809194941860055725688463142259247937365864292097374760731283115456125144314403287389689811848533798497172854139263106403970970767832914389284825232983770269569326602610769852938213063991314457512600262077044556607247686004815225197519849064630194602072411153611548816617976629611161774076058387991499180879313098171135000104607088057390566113583481813562318167795690752408577251436557075651796625321412380804461834522110861453914589283389102140842423158075499062130790557709584920892555686784184015736935021414084659353500786805438459607010451454710375617614803779000824796711417212371651035814944655741836978628135031954174346803979279895880597376089592477431007524439786005572276522117125366659018731557956314581357118429905532385306718989428506059208951123403130187203583497279587600717314137325659690255223102329137657582616836630924986125612372902293296531767351652472728404967380085418342078889531575933033789654861810973119737709538294934167268707717207490147599502482002191365161650428408085205746630697911633589296058437330176763968566026644476976211671661663597016167221101561350390779332289412438655889773023586856243107499850750091368065526027183058848952449854006839365504996436753440550774817246388983096332339653828683635220253206607295503695573075421329946281340395110084995324109123813067549142891076945946303797389150118525629781319975015246402534924870009020272812544519972411195349070476440849675964616315032613870456353896015686552232140202029058601683914987549225643400977213064816383539361946347214515184421442725118303688640909210851968044415085993479335471237893128970110860999644050929225591128577977697110795886812008728102058336083987457371041014291041787639881067721251256322828879763720048199867188989626187681003739359201548420777760813571749264565473277572314409184305463539788669820366625181155579158517102630401592193974024062944700874611935417112811387824805024645714976677689502450172140905423269237126615360364146264582398196248239052232560379355262424361900443169181409289830883817146607514747288640163883825188893498339778961971048441935575423392134610448025611428287751559602620762064282904135610590021946452351103570973584347781388108686089246109821613642473903662003780498635494007788791306397777156529950199741528775574352335831947520638483670566315813773737937718287681176791230927961926403590894864179786612144929612701094191399041561302709595462884580702698734417734747667308308474445610655701847450850880677326788880988659737134541709353706869851508197810071642874596377652491225622783625124809779655300010196804168445863947458478126532866142418139638636169619784241201025104103569162661850697233137658161545845238664874278481582955146796238744085258345691773138947241760426446842347382077687148770884928422528788462859781740721154196826651276658715201687303544780432944882605874083012045419900670542434339576257940801646369629866771035113316275611252510542297173678182355356307891337369712273494438924240363976561398949720791096486177476638943144041365683880905308996854002632518849704279330740850507372349552447454780647602079357472698229280955028276224810344348781613014268953034057799703474943894645298495287398368509407425444311239035909507049958224697954431727836844597218706519431827986687368773259428144374474196243619778938452567277929257701942979413842994813124640356422288194040098198622006424193223319480771602308300031949037034039949500039093577821159066779108401355923296271059338446841824887202256551637391650273178663656831429176465925229431253556139101849451697188093569033724361538707091808551619552203637238752165656880898582733632358160868663941515691309835061467644576896579162446958278426567439769796925609825924327907274082126317131863574701835156000546450561014355508203046978940715759816249867498161821108146369989919085037286403925596355015582233132843095001509513409195549271958526197372282884674525448877487585354872014260324645020584867246325201401081500380501657402844000946314188707094172292486953881532298897913024640188411615745456953761533296543771935431050098610081585478622861530290847625163239443645435265033836809735608013463271023667698807526333037636762445516813188574394779504543608373333548714059245040546259562297467655760741811663574785155161435651117976867602991468657245461967739498369262991900543445165573975790516233180921075358481170831150811514399070068054154794992447079758138166852700005098019170786807055172249621289353929044748791117421903002787673969421527220220808766828368891980734568931327785181768706389439770844788761194609170390970737537079297574217787248028652064958171151309863182041615903576165331436746470510706143937789498803365145853871893699577476364275281756972600671098427258791088865632122743412721957501587891274845238362770663119097803991064908058027246352269349731838171144027349239914043366831290060423824640440889894226387214352674346178327480875356343489907052206037543429628760570800063208149809695120446282221462284324140286737411723172424797661512319495758524859420509643389028479005641434154612543380404487862299158663375380559166073948625021253489276928893325716126562062752600023297255548849330262272096643609265485527045178482949410719882908093146256400469588214433142939150832046498096109896061676805209129488950106520989100057888793608416359289051341174259017439272693094408422913822568264217633678186221487674458836626329088560224221723916502761792456519454411192456522487484967689369349690335086047526673950875407301097890218318057755301436268139785632060708702073710620598908208015879967100125257464984598330711861013313552934335928113400770666702721275465742744920381019868334571648485977042560461868607481438007552694732531470834055848064029529259675650554536167919504037600167947950386071878860456333976915934634837345236546379088476147615615459063989148058017492066658541112900465024981043541301655524822805748578646343137919218381362488368513259466553679769984521198564021587336537799040692892370384163979200655189851527197744580336435312980278391611034601368104047062955830166229190939565143759142949823191834363125187901738149384541748875749767556097773597002759450961693450797528783203852820947202775881984897220465435970795131285013244739560168257177840004157395059279747529923733625641773003006891011879669677193282961208150851440908814820158427305275254773944268328970764772672439200701439704009746434436498415068182356694735689334587858146836026976870096182258126370033567438086201303683025479214085768164442505963478764466690422532594646974710413441162571968368707356880731305292741825149759165056759344690132975335660809876529462298679621189957546090520640189069959439276946581352572121178964391885224883485829627587776509150775314386342364471754262430480771056110173630847111269460039505720131785286793799071675247603072880384977435858057341137411120316857391947115429087067929915619760731989562774296324376170409737896233441672750618164617086450070548992158341152655745909860032437955396322670067820077982320173909155542526312017526538602745866467900070601618737213914661840141269389117656591895756253196328869136076553623651927845019384026758856646029345722780912263262683106004892179354767255699194354289059909720923836339031964994298640807665538032439707156034687052077566915162042379010970706470077151171105874582148888832135005494027875186448121145499408680614639006049434607757886521425446439023132339401026732145964173139320211543150191485510647887512012713226455633720311075497443248273099702964006897537077474988094115968802169010800105576928847931700343882977478233063772813297061444760155680692559456031048927201631808957205969484363867182787313940189562978160086919982124240822442509544171890830986034675024048048197169138229615228746692006885704388058374912170541091926271680055118577928945005389240070742918710372250735956019519663926863900142554953882652667736501053429142449412789039850577095272223324957405787929103942022026271317362713784884245249544805014649022305252172744289772005143566508589924714751674626581149462311621386513667198094501923682687205424879147764072029913784887938215899771637951364413837920122080302613593776032770671624588681587763636091683680193511626472920048227002623437586069556163769190022067238016798256183194039214467067104971873626832135265578264057094511926993863869552500826621542004157954267675066607850839738780909725723626508352263696999703542361235787339462578519541288744225378189081968991979260690815749850374355998073613639816273244471958944889526463553637495294756427390763433871509653873113833934880352885248646863734622078563701478512189369638516657548640232693762749301646431586262641120056755271755543535181558520293968100392441436336097332821081859280522213903632469095124289601031361190018606461111819989589084561634045051001864977972512982867516249344999341485518094239374470295692988628046709719959127852115722621026880224818039404978102023462511935095104824355188343099626999842050429206449217803733132957897246879357320939658274672624676556467730326786770388422042856073825551677162314751845575896240703317323223548303939123078850266720589294391082945063696072762666380739965676716042606331069221187171719586133116342413676132187437012750501049672655839017533542883674769010321311925304646911706266746944390551986089521361439545118938332871473830920673478246607645997369454235407311205216221649055346997323045447969596097048387738633898055282666349605114134938918893657034707042016275742905652313283591802082344169679253082562535843230421221735383624956718038225710787873527645991998933691138347157399720980460666306507864469624823235093648986360689499832355239387853766358722408225365456813418135374495595528341256567636067872854705393856361454761406504590467853374635171834065789190491253633099700220249981909342887514933778073891563520769629704650247827940825539842661069884283538627450497936206549626099276054370948233872049946201580620886898461567773718239146581080069097871536614407306227777607295309347456613259678495569777130156731937902255809702655702008025003876832974244482542606531134206252357256828072141183057146893161939534819767120320720023417470073488022137859788212826339409656106237323836902327645319545717419425507886803975774261075015084889240316731141017361880030828474946656370131406713167351735085280320364051028982463290700450777283212739284737615471251034004904730384316380853934771058886458462067897146902382598097850013767284154810259289317095518698146026499318562192966000022175222085867524168896110563087282224606191032606486391527079730091690153394559533348798123395602201861869596338422050854228372444562288019570119000227915004017152420371670781007753083584461275427710361663375105207157908607066604054582044167896483674044837813364178534961740636362814223802069100260835377623024714713253635785031675609183263549309900264478758620635862156330417552779128497596328409861426500847503118609673040224802761157512061475778004389764307189632825333701394009567337127230473839113921392701997295812529512478244982743609035787688876962353249828762313240303358804467005240316761174454711974303205448077467187204283489913398940383723241272601210168716093783275436844953360189164151685953182375472596014359025761523129115883168326389658022826317676704747192614572320632757597789677380690557530697027190915092206894799073677936457101580266054239650404455122559403410587189647653456393283908830766849175454508029334482226381608319460739025979138319951700877975123223009551189578244411454336878786953926428476854554138521038732309308756976919632575407935491448232244652886567801615308461451932683404922351753651609613273971587414253537918464855545620090892286559489965633025644193689767775930294491175655219258784634060491883009585057309226364171142960646396197828128907388380925497567706721263868676875110509577694823948417448101058037301415776461505032018708000228208379041848846743986408625333381202808176242705544384058248695315736382568958810232245385489789441899445284280766337255894141005002657945168130643759370539217652267628793571052120263515882548209539773325131837719276999630020589165211115251288750077287383745705934913547273575369248159912414809041156679316768118971965238253278208977996761084225206578246143936698558401070698996503108245195812081536326979684723337421655385577222305096853550370109740353721335858963553913690858602442626908133708383197761465703450899912676845556710101211203584754369367702676339764158583040935519394406869528360670351669968394613270031700499642351121802303702345748681473972237103175569921518045823605673604641108744081784300599342033268129608826340145036752318336930127092685536211204651047549851396843824179764272599001967260750861137528875699547101495263245730610851360324590653055708859928778218513760531088869455157998995865741011882714441291612932684071649640764403139164019348287118098355037404535251159421187337781232676543973384496805286230630153905358751624105022080233367484973418419410996429081008205682519211265811683033652282965133609929938283146163982006761195324292047608035613534618023315740278356716055521595293700099266355656725444723043693287954034815957358024181639798201031064305820522736259774305557214470930275041195817833554351417805905208444583637607469442218411805346893372217141439724069105491378606390318123968893070958915086597883918378059092609173982227065183262463111703080642344921511947017769545836467470459951336999711554659047592129171089238721369380502414752103572474663316671494601248748560757155277026359038076034313805182259605129690112116368899475925063921983721890853396228153255675857121753739399499035990997610223941428066239763913885451055038914606462095781984101167384377123886669342222722628048073632473211661943379349995185740599061214801931850484047954148939373762717744944144072385896657451465781568485645892664006083458822004712992536629978779365461803749014650409241677586696956145973472750290229443536400782397037183192721983351416988065138790250502111598971019238153114806536643350277117947640694210888033424522615099443526763859727592680035764979493439782908225404339781831249859655148687787535695072012809893682303482646870318702207338283488151345202931628396366793009309691970128280735172447586164109433466787126419738682721862978217981621755957197633605070493882943469750536657174197968026284712844238358458845315776930303473174162643575927102849280198263707299736246882529793423847506386763367232242683628793299044264879814211568990996070708503944555749414969265450797229474933982077951261766030105011511121775222613431040619756564182040694086186372198192319182045145987219617484916796015599226726766012548758206385975705445296869343064169333977365516651589816331829528519856898113624928615127234992426020479813993721077104871629141004936310092324700311721977546892809466929032833415803662003569651212256374155401273275891220302553752497191215704740760707498204997808371417259420089004549212631121704062115872980946878536933670014923667699146819029381944949982176346464153614362928972708334774453798325267994483090523726811855956412946239715437161483452409527649939769410923263575518110305691309558269450879208140670546845723292001276797968980956238099128003590445854907697561188374046108914078633787671255808929865482089135207798234640508973416850465903313317119145962608213144962714360413585229370905149381305272146208675920527173950598975528738315639257345130375199410417740965828248504836129013509960157494986397997453351066813806946282296948654132755598717478574858588698951730800540282049393827108454258134098808389583110365861713115441570552472292807897973493108216747521990290942199928874285294311486567656707840410383762039901360639142804972336573952628211844631482288454842883983597752332878799685371636572511862416707966127690913996038844874015753100135481825310373437729442730909551975713172350462477393245606014472455378023394918238248854983366685152881967918333950947288122209361423249756671569522611528387346733691687120289648676090456811276149038152674722164896698170189316926967014586656821344780068376380296683098574879733343395300821702840658960239904083155336402607815783198436741706263447783791223962022030850313570347976113975954234004672797206194372986783662307912852486559837374790878374854013733128065274228261329271074559976668496789658671949469897423686815560486768683703186715662853427357387777709984537428815946205206998711348777010524981923031225572565442744858294735069733378800811204768320657751753798765265608250161557331942780837510395635678325135572775870412252218165674668342587538467705779500015877886086341999660586896939319760671379350428053542207080048448754160968982534757686690033381193921526188275864112952366001507816110885031937457631337269642422865772505812985794618874928142714188952998542220413571384786223000977948566856195021814728937816149526407509026825564145524096785628044998286886150421344201470721658953677740011128880835413601104445226919694958398920535074669759821563119558691962760914981171671365695450252571919651339129999297061183619718101275712235623530886979246704667242502421486190100717542812904752527361997511352187767074513601103830122067736520665184925452656049980909072148918477592309836203336410638607889046003346839711985766932788729285241675886453821988383553667254741264371223440674131790097226867005473823817296135693943288092190863079421825779476179851054611185688587178494486778858945461313496029650064415587419657475719117991956298777491466284290958562103583055998668068298592168088584213972066282691496589598743040677186382274457126251929983967159891074230770081456469036538575093843422984162293807882676117676436815612814961010407026778291149738591113027816756568315765328409749470028128272846675173492051262694654605411591353222109599689326438510041719770650732018729275872278891976878053067199255653243837784164262478418501863164913916250361773861115531023162668507983373540612742997073968245917071191154693437043861375454381040994020065922548963047040984092303777949565905491434113186387669020137677274565398991224251934820278813537793022571399970089315522560432067617698846352709973106527481275880226827431106972524285150315623384933503632223788892312536486933797539443428750403756

a=[0,0]
c=[0,0]
for n in range(2,pow(10,5)+1):
  if 1<<n & prime and 1<<int((n+1)/2) & prime:
    a.append(1)
  else:
    a.append(0)
  c.append(c[n-1]+a[n])
for i in range(q):
  print(c[l[i][1]]-c[l[i][0]-1])