import sys,io,os
try:Z=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
except:Z=lambda:sys.stdin.readline().encode()
Y=lambda:map(int,Z().split())
from fractions import Fraction as F
from math import gcd, comb, factorial as fact

def lcm(a,b):
    return a*b//gcd(a,b)

N=10000; depth=6; C=8

def P(n):
    b=[0,n+1]
    while b[1]-b[0]>1: M=sum(b)>>1; b[M*(M+1)>n+n]=M
    return b[0]

def low(n):
    v=P(n); return (v-1)*(v+2)>>1

def makeQ(n):
    Q=[0,1]
    for i in range(1,n): Q.append(Q[-1]+Q[P(i+1)])
    return Q

Q=makeQ(N)

B=[1,F(1,2),F(1,6),0]

def getB(n):
    while len(B)<=n:
        m=len(B); s=0
        for i in range(m): s+=comb(m,i)*F(B[i],m-i+1)
        B.append(1-s)
    return B[n]
    
def I(p):
    q=[0]*(len(p)+1)
    for i in range(len(p)):
        if p[i]:
            q[i+1]+=F(p[i],i+1); q[i]+=F(p[i],2)
            for j in range(2,i+1): q[i-j+1]+=p[i]*F(getB(j),i-j+1)*comb(i,j)
    q[0]=0; return q

def add(p,q):
    if len(p)<len(q): q,p=p,q
    r=p[:]
    for i in range(len(q)): r[i]+=q[i]
    while r and r[-1]==0: r.pop()
    return r

def mult(p,q):
    r=[0]*(len(p)+len(q)-1)
    for i in range(len(p)):
        for j in range(len(q)): r[i+j]+=p[i]*q[j]
    return r

def exp(p,n):
    if n<1: return [1]
    return mult(p,exp(p,n-1))

def sub(p,q):
    r=[0]*((len(q)-1)*(len(p)-1)+1)
    for i in range(len(p)):
        if p[i]: r=add(r,mult([p[i]],exp(q,i)))
    return r

def nextpoly(p):
    q=I(I(p)); vh=[-1,F(3,2),F(1,2)]; vl=sub(vh,[-1,1])
    return add(sub(q,vh),mult([-1],sub(q,vl)))

def norm(p):
    g=1
    for i in range(len(p)):
        if p[i]!=int(p[i]): g=lcm(g,p[i].denominator)
    return ([int(i) for i in mult([g],p)],g)

Ipolys=[([0,3,1],2),([0,-48,38,63,33,9,1],48),([0,196608,-216704,-309120,-84280,138852,239330,221355,144165,68775,23989,5985,1015,105,5],215040),([0,-8170034429952,9446602309632,13242813382656,3253644066816,-6814703960064,-11551688372224,-11177988636672,-8527949958528,-6088306580928,-4102334794272,-1270985674608,2960507670120,7394031433404,10146637706634,10266044556339,8277846830253,5500296704331,3063593886925,1443192205455,577195107489,195981385743,56298123141,13586106105,2723375655,445846401,58134615,5810805,418275,19305,429],9068756336640),([0,4993163141485427710512133570560,-6217622334732426907008525926400,-4609926401874229401674475110400,1891617398949620243054544814080,-11754978917324288673017902399488,-21539100476135705477799645020160,25035604374378117950572729466880,85940693873442956194295788339200,43975728479055941507209305784320,-86565205141255594304375133044736,-129399141352374654373595310981120,-5727283934809365706514607636480,128989365837438626734077420503040,103796036791621745133448467578880,-36006614658366126317062733168640,-115795641774153829214485308211200,-66368561875528789156871815741440,25180642419980212196056267939840,58248723401413133715909135175680,27417827023340007547922593536000,-10589443479491089540427889085440,-19231064496042186015873576921600,-7340787368764289713611180460800,1584793748818901727757739088000,-1183386499005395961974232505152,-8808099454930529573113015179360,-12527030250570651011726204782800,-9848993074700132408229848714040,-3378754191500916819017614606980,3380310016548994085677034615250,8308930356281917865550452379975,10758118260909866055250210594425,10950060159924870982009819097655,9534256299930016922675732804025,7312326939974688885093110909535,5003849686444456682430640732545,3076959288404874633370780682655,1708459756295157517865711322825,859711967087470947703442612115,393213337381125402312794089005,163834279927069501186808079555,62285446412121755642035815885,21627946094512650663872782395,6862370043748399800644370645,1989246239339267317347522675,526407239074138693156787265,126988644307925154448819125,27868749374808824057851275,5548296038989566014734725,998410440350486176984971,161644514276377714564125,23410006654177533890115,3010827244251961610685,340768600407022000235,33550091132004294705,2830568660587562895,200600129478299265,11616683414482575,527975490267225,17663648880735,386795230965,4159088505],5853022083023334024780605030400),([0,-2566588288561817259470083872073123890213077475843660980994464855489474514124800,-855529429520604302178675905490346167102337045811084537311106442125572571136000,37996816602861161236867877932219298297889898613398471834553497592329811515146240,37996816602861160449145117606190242904307586292841322165580902693141866809917440,-156090491232655616813170055325906348280098555077953938449347540004752271609954304,-279852871774428111935784705021447581489139267440033743203503930317082434071429120,169398064820582221155743073882226253825684218961996651964323530438780079466086400,770275699619008893726338561326508708851166779594385118472932483023680502570680320,382047218442479705129085512899246873250267333814398481836461562700325734171279360,-858981137284384712212610883203188064411118094567680894325381852076112571413823488,-1251477572352125128465209275191439602715947650874717520263788812553245555939082240,-35304606401550866914072711856430273640315530437485209266957608583590540895846400,1288900224487977590054064100906451016012477436075824818711851898227802077396992000,1067406539345285098583934831939479255563539546096971339381113911414222483609354240,-271140215923170778142611023471498955588938646406583379848834502566848898772500480,-1047598545317377407565117859548575578264171953042533296288666039052831188834058240,-591265022687936538852940245072594541752614591392113955278499573480320867898490880,266004200191946944133553304497634064283857150199860053176416896782188296997437440,560162585324423227524104658977741742499429593394201001925760760547259365206261760,242102036689037647827590024989448947534437993144558758282817956177552151108648960,-136951995000532647463878477677628313208402903856887446614213364092376962658467840,-217604178421213603641692763392264935237495298030618332218175064906585478518538240,-79759988356279267851384654720013717662396171700124828908288146035673223806320640,46966182347461777851331815618393922346351201030852345331735964542102348245237760,65097970626235202120153060361247800611420360597660225690843089796081825605484544,22184567173419532732113575247747926757160388129370068888888730822047711792988160,-11654375522156411235386649621085392205040994426127576036665816251858448820469760,-15547886206515097580687072404218665050476423941448382728139570406240715999805440,-5302984103774886231477423751161549286154554653658985068114257931876605634805760,2159666332859083521382206296952806012930790058605014577625740509256616488468480,3032444416916990026475233159450361235317633750521894737233068622386566896025600,1089676013740772187431093936961016854830213479224482201856222960149841995366400,-296553604012339254101519387198052340736085978854047980309041290967426971729920,-489729630327160363696675565268747184613684619112491449659676111368095793152000,-191607996646907540263972798660131992899564869617912556364271102212127336693760,27663417648455382234013744820184928375522644411555505479415020363139199795200,65984732824568670901118415506784260559467958556822845207296997315974686310400,28749559489698429998457883536976519039271084490292360167287729269447411630080,-953417118735677071476752257442363838480601338910914952466208816902355025920,-7430971176118058238743563474405701664423701337459737865381238832688823009280,-3680300646505073088294510425271648761894132334093064186103201450271115837440,-225880025840161845044917199844250109222591270207073171104321987482086277120,695618592779196442212920869686944107772210548055512666136790468431031828480,402472667509940438939215859136656166571931477934999057266130722873191956480,57548103380679016575883348044943593721080759223850391622752347363998433280,-53116969864636696486265815598195722693399095617051063231738803849767813120,-37641334421560063190103799263932279148051019754723911775607631924575928320,-8158693854453518042144371837547043928280009960002561294150343176318648320,3138242566618607010469895608741756583143315430534945866124061810367610880,3008109693930452661389898357270269841118184981588758514892514495756197888,868127888868067081624289087322740123887595957188487760967578457433395200,-118424009335267839505987468976660833543167763830151343781506065630095360,-204351950002611658227203235853448946182109721192652344219176095866506240,-74886784249294537641483039257496930535720889149591375160828542991546880,-878692041742812190453018005924685984717358005348207335935283576840960,11636327772708714593021992566280237124305581664240291415265879423239040,5401611044363706070975137597738774571961248771177903769655571068486720,629361264283000129128705350762950678782637303040237289525469195377120,-536098779797084314942285139601465598776737499768416912578440702681840,-330006361118833531308283188588018082332312730948076731819639604176200,-66732285824092818742611523131382105139685508846405668625189919305500,18014665675641355709588493485928861974657432994251864342928712458350,17099048039714456782366915032851501242194652100237259617569126990185,4830683568866296240253539887876319285128048955412792705852286829335,-275165402328950619932046969979595169837959882623992829742382616695,-775064253686429839398140898785233637958366647438492278839332064105,-299778398692102208187700219311335637120845075446638571959492963015,-28175914781630346876842206341617927004805878635004823181660783865,29481039424522505783994143381989947821909393005052015805766201785,22320796417390030150022798039388527875444208790895620572265794295,13284474810191899394922255104633688471104625653625810584388477585,9979780720332223987382314091281022748210984171486315427252631535,8429737839120767619453140659092479223800369298901886297541969585,6679212030322704738941041846581043633425448924046701529690978735,4774782897061651875652085272228908830532159169150576215380605185,3122706789324073814483289641293963819485614616402289577945820255,1902345707046999849663461051626297865331332137450441965579890385,1092028925048081376315220446781708470355170494179094381481987175,593976754253600317116825479385107050075147866433174177262677725,306797228253989237671834896194971926386635927264162097734407075,150622872228602928282336043431143929367174162135057299189838205,70338976783181960014947392307722107196321902787306692649238435,31267351453742859878667348912353205358811181394144431177703725,13240092895627823022218126564586984093885942764279844561001875,5343761574330538434044887275831915191554005561213258025216365,2056423820394764383261101487079917530594356377683554406773475,754637719247033104243867554839807415329329746364141668669525,264051734831348426278670388374590197717624564194687735244075,88077883164625301140585477327185464464921725456812830142325,27998672469764627758404090074659092617697028595183892065835,8479054351006413097557584746796047810344051312208096109925,2445321739762589837845744761729773550980631082783341532875,671335331138647899418394220616542719179543331755000595325,175384321903694631812440508825191472188634690950874633775,43582822348461364117164172721620424739855335854519376475,10297354907348953433016437649619696976059313472452741925,2312141215806452561781423189972760108212983335674457275,493113793948492836562387553231511539487824913236636325,99828853054718235381217369092635306553559265993760075,19170461968852676854495421194458574863399939237938805,3489158990637609638952448664944906698879323243573835,601326881422685771419259949497226166632034365869445,98023666411546505209252241939556830336685869351475,15095297664604695908282452180549473457327190280525,2192933604767129766729757528991465524817052300435,300039220280234984095787752240354441763166480525,38591952111903983796625809630012684539156287875,4656583415883775814418560533355514216334370525,525832916181995330488759680591565061637001875,55417618426420071337111603579884418985572645,5433816721215322451979688006215610431926175,493915447859682928519317852032156177990625,41445784246558207140643028246760464258175,3195082949536938447361208392919591769825,225002534603705235901215646865812076175,14377006398894279279879519570260495025,826822041755176898289025739722925775,42377622774579589888179863119670625,1912154276778086922319178401393575,74782557938426577097882617819225,2483565348133005692112232050375,68103455374231779231651346425,1480472593709114491236325575,23921154553059695936829825,255385991669676469076475,1351248633172891370775],1104962513089831776440375381747201460808082315588714467688448000)]
IIpolys=[([0,5,6,1],6),([0,-656,350,1925,1260,406,70,5],1680),([0,86814720,-113832576,-351455104,-127927800,161741580,301170870,283277709,184864680,88256740,31026996,7944846,1441440,175560,12870,429],276756480),([0,-905341889933381468160,1207818390986293248000,4068955850050932572160,1173097364371960135680,-2955658636354104705024,-3402708993156409896960,-2329552750127898746880,-2555561083222869321600,-2382428512550300202560,-1234532564570197807200,-185223366376908210000,888260585793234053400,2171248941727973317140,3049340966630514952110,3094814740048479550905,2487839932417028389200,1651711806337356209160,920752268806510569000,433900242837274072860,173465663215464940320,58879745991980902560,16916788876089447540,4083576008411749590,818695943130265200,134233348190496984,17642226375635400,1809251038886060,139246283147400,7558067731500,257863487310,4159088505],2725525797821271244800),([0,-185513373222304899356269106788099169824975759933452582912000,-57345018049317073786529827518023012764876800,1220629069877195589126277261311851851297125963118571075665920,39111374833917655297449082781687218805145600,-2409425208031516344535517314048289484990983149304810016079872,-448312909153003124436707126716977369631948800,2264768917836523787947081506947020501787944246416423077806080,1746340978906617318219885832732465422139392000,-1241798515496095400051418713945914328323430499043042740142080,-1761486809695626028942802886075689642470932480,445674912502051986889941028647496896419725313336479737446400,-113812805470294518447447368398816228776345600,-112785514817571474180483322485763897244046452490276448501760,2119555884178171228821722223318278402840985600,21202826922335558877850759513512246963112446193819346534400,-2369935367946911948999960850798469670660505600,-3077404616298770793906018378403284214806836351729913937920,516420842136444786550262492621381966379212800,355237030936168183879509740553005297205770387741737881600,560999907145381077779025448965400012189440000,-33390942513980593924163010634835694680272766831131724800,-393733566257683685502600610699438106441280000,2605180973684904242291557739624453937664838491779360000,32471454775695009479364463793694878513040000,-171414037390400694065245234342204613439145228237723968,-180278582450399817676184074009198004864546400,9639821610147383113307613155390111168132580148019760,-201593416805684924208220413253694334847534200,-468676070714233656021776531393656063486699072729860,69188373710373553749994695477325399239599250,19895424807531083733284398899669045011756855486615,220198496869369045426987831058752599103240800,-743557288111541502747457539642722418881790959760,195148162982844013088388000892674507894673200,24824722605565722452550119650199549416143559560,102419317030036236577754229654810331948795200,-668350834836520602164526806417410902789026560,34968935813509036349741747242321010635519800,37078298485106375114896201661055965872432900,8048332473316048278030483546595701416920800,2884411868591755235209211906885418333777840,1274865080438599220365569196883846710525200,452934457107695586920433869799479338834200,140459710981569394533856052759548221171600,40511705276648742222589086275148924743640,10774560174588364534618836824125816070700,2602949821452859698188521097094747957450,570420621689586696581514297973008372000,113500447360572814860525025404091506000,20435544203376829205232095415944550480,3309515212235112474878254452603384120,479155837805254636980490188834336000,61612074798286998432081442335343200,6975214915324078315882820308431800,687061465039062621702967031644420,57993146332453689277101064884000,4117695410942418401683210338000,240435519589063491558483618000,11214232106619861507684295800,401126264249171840762783400,10325223080328121871805900,170257327779784312717650,1351248633172891370775],119800275720703824264840485074035284115456000)]

def polyval(n,p,d):
    s=0
    for i in range(len(p)): s+=p[i]*n**i
    return s//d

ID={}
def Ipolyval(n,layer):
    if(n,layer) in ID: return ID[(n,layer)]
    v=polyval(n,*Ipolys[layer]); ID[(n,layer)]=v; return v

IID={}
def IIpolyval(n,layer):
    if(n,layer) in IID: return IID[(n,layer)]
    v=polyval(n,*IIpolys[layer]); IID[(n,layer)]=v; return v

def val(H,L,layer):
    if H<C:
        s=0
        for i in range(H): s+=Q[P(i+1)]*Ipolyval(i,layer)
        return Q[H]*L-s
    nH=P(H)
    bulk=Ipolyval(nH-1,layer+1)
    rem=IIpolyval(H-1,layer)-IIpolyval(low(H)-1,layer)
    nL=bulk+rem
    return getQ(H)*L-val(nH,nL,layer+1)

D={}
def getQ(n):
    if n<N: return Q[n]
    if n in D: return D[n]
    v=val(P(n),n,0); D[n]=v; return v

O=[]
for _ in range(*Y()): O.append(str(getQ(*Y())))
print('\n'.join(O))