#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;typedef long long LL;
int T,n,m,x,y,i,j,A,B;LL ans;
int V1[]={3275884,8495860,16311378,27345852,38444692,56562144,74636782,97188816,121066098,145274178,175925516,205461368,244528662,281025620,320161028,363094294,400651536,458403036,506880548,560990190,617838162,669815456,733458074,796858362,870647680,935743426,6389075,83026861,143575893,244796021,324141729,406816711,498315891,575798809,678692479,773466063,878383355,977931833,74211744,184620242,284304814,412981986,524094528,639044444,759402158,862917026,12107059,132189917,268523899,403250929,8495860,19416016,28776204,50637676,70643060,97540466,124202696,163976336,204963040,231133244,289753268,339992276,390954008,449676876,515984568,585756190,624022788,730212174,813251386,876882592,975726188,62064749,157899447,240012313,367846257,477159199,555769465,697702023,796566971,934821225,56879062,193888660,343130352,422805372,613038228,771151278,898009066,64598107,223351881,392904213,511170405,737191215,922900759,52369626,269707318,437738418,646132918,819888232,47097955,268299079,16311378,28776204,38701008,73088426,100616286,127906842,163969520,223409230,266260288,292814398,380348602,442692612,494081956,576190900,670357456,740759280,779370314,937284174,30469297,94496905,236891991,352043671,448233023,550015889,735304805,850764069,929800299,136141698,263929694,402566748,567553126,762983374,915050856,995112388,273553535,457680221,584915147,819936389,34979190,204912094,342193494,670555340,870542794,446955,313325245,531491141,740275789,967339471,291674656,518934114,27345852,50637676,73088426,115428788,143321358,171058720,217580022,301809386,369497352,422013488,520558134,583359434,635227484,743917434,875492652,982913844,59621761,229710737,323286167,387729685,576131583,740213221,884769743,40979826,233963098,349864716,429360830,702804968,889278358,102428339,324451001,522309395,674775231,755246535,125341180,393541080,602771376,893553104,108996055,279344217,435962261,875052771,170085878,395431344,755995336,974555116,183743085,466265459,904828543,240489610,38444692,70643060,100616286,143321358,171941516,200078952,258200202,359448870,449559028,512332126,611342156,674561896,726942548,862128490,12352325,159183995,245526661,416033089,509976211,574818861,808319877,988717633,191127248,355027006,548432016,664737984,744730374,83776927,282543279,575409619,799651527,997905829,150764316,231618226,688071686,2106215,271441457,562611447,778504429,949303355,125827970,654675450,17411541,291018739,651978807,870920831,80553672,420015736,928864670,360315487,56562144,97540466,127906842,171058720,200078952,229042064,299556932,434231734,536297334,599495612,698993426,762673796,815467742,978839208,178374239,335427713,422136937,593083967,687422525,752732361,35141786,277868360,486676088,651012098,844844224,961751954,42253123,453511725,724617629,20519424,245146716,443817878,597042606,678291404,236961321,625868879,895573679,187170310,403506638,574783146,771664668,430581905,850345137,124341402,485710442,705079836,915211658,311943279,957736145,432379952,74636782,124202696,163969520,217580022,258200202,299556932,391311872,538509044,641015986,704704226,804694980,869000994,922254802,116332909,348359353,526814547,637131529,832369525,951397853,42762688,375510544,625610716,834833616,999628876,193979883,311370899,392336115,883266457,189950346,522703758,784289252,19440105,212182901,333435207,963913563,353192684,623331246,915353212,132154703,303857695,521458055,289605276,758947218,82303139,492375243,764734877,27499086,508919724,200515343,675557581,97188816,163976336,223409230,301809386,359448870,434231734,538509044,686725336,789592878,853680194,954157242,18926497,72618471,297274017,571928711,801919503,944378041,208139712,376279152,522992640,863323774,114006155,323634211,488986415,683791013,801638031,883068827,451948272,803451026,242875501,576151641,887164667,169524548,350132428,981158496,370920411,641533657,933993763,151348580,323493874,562146848,455225269,19168928,441568118,967094796,312069511,721043089,244021194,936141440,411623067,121066098,204963040,266260288,369497352,449559028,536297334,641015986,789592878,893536380,958011318,58902701,124162317,178343147,435954505,755025049,13608736,156405264,487575468,703056994,856392254,197184521,448350041,658345169,824217607,19484778,137912464,219986726,867309702,278735719,747809495,132954778,518194160,857993074,38978805,670479607,60618250,331670658,624517078,842372504,14950217,275298203,286700624,935382044,363751205,998764175,435093138,888975812,412351339,104914186,580867054,145274178,231133244,292814398,422013488,512332126,599495612,704704226,853680194,958011318,23686501,124989855,190776585,245495589,537963827,885999725,144944692,288131978,685145706,907672250,61434963,402639037,654350541,864810391,31094058,226842694,345879396,428570910,154133097,587780505,57213684,496196906,937114996,277296541,458706933,90653766,481216516,752642404,45873165,264215529,437256631,719710885,839322924,495169055,923928393,666932468,141499391,595788493,119583192,812631094,289085743,175925516,289753268,380348602,520558134,611342156,698993426,804694980,954157242,58902701,124989855,227618069,293842521,349032219,676508867,80868330,395486628,595353512,999812102,222779041,376966707,718706907,970934119,181827420,348550422,544721752,664175932,747358610,550790197,63794342,637815240,136902511,578227151,918815761,100655524,733061808,124035617,395856947,689494567,908341751,81895908,386815880,638153081,415673544,965117588,745196191,220249794,674963912,199240031,892799699,369717086,205461368,339992276,442692612,583359434,674561896,762673796,869000994,18926497,124162317,190776585,293842521,361446625,417150649,782170281,219781406,588294982,795237054,200126161,423503297,578186051,920387049,173030084,384402590,551679976,748238196,868144512,951816164,843683035,383398878,41566473,541032003,982819123,323859574,506164766,139005203,530638409,802902317,97143136,316650988,490710816,818452794,184400688,48575041,641680811,422228420,897791012,352970655,877697229,571748802,49114155,244528662,390954008,494081956,635227484,726942548,815467742,922254802,72618471,178343147,245495589,349032219,417150649,474349225,878086819,376602186,751979542,959351896,364676229,588623009,743812641,86483108,339623292,551773092,719689922,916713274,37090597,121197763,103881756,712737778,371275341,871182335,313402716,654903784,837643408,470900041,862981875,135662674,430357548,650350066,824860260,175920809,689527752,597063907,190585690,971546474,447560667,903180995,428388216,122941493,600812727,281025620,449676876,576190900,743917434,862128490,978839208,116332909,297274017,435954505,537963827,676508867,782170281,878086819,328923418,834791446,210585105,418384675,824239093,48598800,204266644,547474574,801119000,13881203,182226477,379725689,500573279,585109763,659640088,325886091,52828740,616672172,121182643,535052619,785750285,487537864,954810722,299387577,668338371,966947295,217400630,654498006,213661566,121577983,715502563,496900724,973333554,429385321,955090203,650243006,128567681,320161028,515984568,670357456,875492652,12352325,178374239,348359353,571928711,755025049,885999725,80868330,219781406,376602186,834791446,342324971,718500915,926671019,332982638,557751498,713802698,57469731,311758957,525021075,693775379,891712939,13021912,98001988,264392329,966611919,811750634,450708391,31311204,541748418,840424726,660479609,205034850,649899616,117201581,481842683,852733023,333231816,893089971,801722930,396416863,178410958,655219774,111662327,637782021,333389498,812277730,363094294,585756190,740759280,982913844,159183995,335427713,526814547,801919503,13608736,144944692,395486628,588294982,751979542,210585105,718500915,96399872,304949822,711637182,936819422,93318129,437398323,692266409,905912967,75298500,273695050,395471410,480962204,736665773,521879444,385534161,85502640,761490544,321157809,620200523,557300586,199075945,650158085,206669340,681692136,88356271,569250981,129747543,38804458,634108022,416505063,893675289,351077472,877890214,574038319,53366218,400651536,624022788,779370314,59621761,245526661,422136937,637131529,944378041,156405264,288131978,595353512,795237054,959351896,418384675,926671019,304949822,515322548,922370516,147978337,304941951,649448681,904716243,119043940,288888480,487715724,610023030,696096190,41395276,840764472,704838499,466416230,192505315,752531209,51962218,100786229,750488325,201960082,847298046,361178351,768244371,249575946,810721877,720639580,316387279,99209338,576801662,35122907,562467255,259144128,739042254,458403036,730212174,937284174,229710737,416033089,593083967,832369525,208139712,487575468,685145706,999812102,200126161,364676229,824239093,332982638,711637182,922370516,331356709,557357635,714740635,59694304,315391616,530176238,700438302,899707242,22582189,109335055,560092558,458820893,475165208,297180627,23692834,584137562,884020328,75679724,866804130,467119739,158322526,672704800,80225053,562012541,123557497,33909210,630069642,413305761,891310369,350079780,877899044,575087939,55501210,506880548,813251386,30469297,323286167,509976211,687422525,951397853,376279152,703056994,907672250,222779041,423503297,588623009,48598800,557751498,936819422,147978337,557357635,785345353,943122421,288482012,544666892,759903326,930744726,130431533,253753157,341156101,897151120,848981679,933704244,756105235,483022242,43906889,344243091,666945138,545451191,186877988,878526796,393399099,801404895,283615888,845539021,756453352,353102823,136754380,615290884,74522865,602803037,300497834,781369474,560990190,876882592,94496905,387729685,574818861,752732361,42762688,522992640,856392254,61434963,376966707,578186051,743812641,204266644,713802698,93318129,304941951,714740635,943122421,103008202,448757512,705384468,921150810,92541365,292929219,416880759,504756627,162288087,166766248,251876555,74683910,802056632,363396693,664145175,117405221,41677012,683520434,375577819,890894687,299337290,782040460,344363312,255909873,853243073,637621084,116624871,576370061,105155318,803305192,284779717,617838162,975726188,236891991,576131583,808319877,35141786,375510544,863323774,197184521,402639037,718706907,920387049,86483108,547474574,57469731,437398323,649448681,59694304,288482012,448757512,796696082,53779883,270034157,441915349,642855415,767383327,855757383,618449723,707118980,896452757,816262316,638600213,303529040,701366600,197580654,122300401,764528113,457098684,972862212,381788733,864970413,427830871,339805882,937960602,722814667,202263200,662512786,191740069,890346183,372328512,669815456,62064749,352043671,740213221,988717633,277868360,625610716,114006155,448350041,654350541,970934119,173030084,339623292,801119000,311758957,692266409,904716243,315391616,544666892,705384468,53779883,313143747,529809097,702084183,903402881,28346668,117295732,982494153,95304199,409542914,405262573,292736524,61968347,495237631,991943272,917102243,559823036,252922465,769164197,178537470,662372040,225728736,138220845,736934987,522363918,2373295,463081817,992807283,691810504,174227761,733458074,157899447,448233023,884769743,191127248,486676088,834833616,323634211,658345169,864810391,181827420,384402590,551773092,13881203,525021075,905912967,119043940,530176238,759903326,921150810,270034157,529809097,748848363,921524033,123389252,248788568,338186444,303172744,521436923,843492038,906453357,912200876,723300819,156970624,654095297,579777130,222931699,916469405,433144722,842968388,327267087,891154828,804073023,403242880,189139189,669602285,130758870,661147004,360580763,843420195,796858362,240012313,550015889,40979826,355027006,651012098,999628876,488986415,824217607,31094058,348550422,551679976,719689922,182226477,693775379,75298500,288888480,700438302,930744726,92541365,441915349,702084183,921524033,96639168,298991790,424945786,514833352,602238288,864704337,226802951,378816546,431578687,243086176,677194734,174869224,100964169,744519829,438567940,955907110,366195007,850976795,415374675,328897638,928456942,714908317,195903232,657731582,188572741,888416361,371735038,870647680,367846257,735304805,233963098,548432016,844844224,193979883,683791013,19484778,226842694,544721752,748238196,916713274,379725689,891712939,273695050,487715724,899707242,130431533,292929219,642855415,903402881,123389252,298991790,503870516,630215176,720610268,926937516,267310118,792280965,984645154,37925500,849892860,284452589,782616364,709207433,353270970,48005703,565947295,976839939,462131810,27030450,941069242,541097497,328451086,810437376,272862669,804432775,504747688,988579026,935743426,477159199,850764069,349864716,664737984,961751954,311370899,801638031,137912464,345879396,664175932,868144512,37090597,500573279,13021912,395471410,610023030,22582189,253753157,416880759,767383327,28346668,248788568,424945786,630215176,759278648,850104952,168219883,585398012,160379528,353169323,406934268,219387735,654362957,153041953,80064428,724650002,419936973,938334015,349706750,835451006,400877270,315363875,916031729,704172462,186735141,649605813,182080434,882903590,367195833,6389075,555769465,929800299,429360830,744730374,42253123,392336115,883068827,219986726,428570910,747358610,951816164,121197763,585109763,98001988,480962204,696096190,109335055,341156101,504756627,855757383,117295732,338186444,514833352,720610268,850104952,943718964,381737547,841712538,417102346,610309383,664523620,477384371,912886865,412010705,339685382,984719756,680460707,199412556,611303358,97500077,663373776,578485575,179688368,968255764,451847449,915202379,448150248,149411647,634236695,83026861,697702023,136141698,702804968,83776927,453511725,883266457,451948272,867309702,154133097,550790197,843683035,103881756,659640088,264392329,736665773,41395276,560092558,897151120,162288087,618449723,982494153,303172744,602238288,926937516,168219883,381737547,856527741,316888609,892688742,86352158,140970081,954260617,390185666,889898363,818018432,463468255,159649444,679118448,91421805,578076639,144864845,60427234,662057724,451055259,935408339,399202578,932634340,634436045,119745052,143575893,796566971,263929694,889278358,282543279,724617629,189950346,803451026,278735719,587780505,63794342,383398878,712737778,325886091,966611919,521879444,840764472,458820893,848981679,166766248,707118980,95304199,521436923,864704337,267310118,585398012,841712538,316888609,780190356,356417450,550517497,605549718,419242007,855584571,355759297,284474662,930296202,626855763,146827994,559577082,46697273,614136988,530603589,132721538,922302040,407178549,871396327,405417952,107759823,593636679,244796021,934821225,402566748,102428339,575409619,20519424,522703758,242875501,747809495,57213684,637815240,41566473,371275341,52828740,811750634,385534161,704838499,475165208,933704244,251876555,896452757,409542914,843492038,226802951,792280965,160379528,417102346,892688742,356417450,935648883,130177669,185621412,999778098,436531317,937090974,866223391,512616194,209597087,729953487,143169474,630820384,198676976,115691139,718649565,508976350,994292216,458939067,993387993,696196704,182504845,324141729,56879062,567553126,324451001,799651527,245146716,784289252,576151641,132954778,496196906,136902511,541032003,871182335,616672172,450708391,85502640,466416230,297180627,756105235,74683910,816262316,405262573,906453357,378816546,984645154,353169323,610309383,86352158,550517497,130177669,327809498,383638305,198178280,635355744,136311442,65822647,712685509,410107084,930971844,344697773,832837439,401155943,318873284,922707756,713443029,199310284,664627360,199544463,902814553,389685082,406816711,193888660,762983374,522309395,997905829,443817878,19440105,887164667,518194160,937114996,578227151,982819123,313402716,121182643,31311204,761490544,192505315,23692834,483022242,802056632,638600213,292736524,912200876,431578687,37925500,406934268,664523620,140970081,605549718,185621412,383638305,442662160,257590789,695225243,196628241,126640518,773886318,471836905,993222949,407535736,896152078,465031866,383260161,987590473,778740048,264986229,731189217,266892340,970672288,458022433,498315891,343130352,915050856,674775231,150764316,597042606,212182901,169524548,857993074,277296541,918815761,323859574,654903784,535052619,541748418,321157809,752531209,584137562,43906889,363396693,303529040,61968347,723300819,243086176,849892860,219387735,477384371,954260617,419242007,999778098,198178280,257590789,75873290,513907674,15729630,946149812,593867395,292304210,814304208,229098875,718285745,287606317,206223188,811003258,602993129,89764996,556495612,92932863,797170109,284944044,575798809,422805372,995112388,755246535,231618226,678291404,333435207,350132428,38978805,458706933,100655524,506164766,837643408,785750285,840424726,620200523,51962218,884020328,344243091,664145175,701366600,495237631,156970624,677194734,284452589,654362957,912886865,390185666,855584571,436531317,635355744,695225243,513907674,955303334,457506102,388420899,36645612,735603866,258062617,673461091,163176556,732961187,652116110,257317891,49915138,537738742,4996107,541828569,246508568,734784848,678692479,613038228,273553535,125341180,688071686,236961321,963913563,981158496,670479607,90653766,733061808,139005203,470900041,487537864,660479609,557300586,100786229,75679724,666945138,117405221,197580654,991943272,654095297,174869224,782616364,153041953,412010705,889898363,355759297,937090974,136311442,196628241,15729630,457506102,963182197,894496688,543175227,242539468,765449600,181293241,671493387,241864589,161469452,767133638,560217477,48606914,516297070,53564231,758739395,247492352,773466063,771151278,457680221,393541080,2106215,625868879,353192684,370920411,60618250,481216516,124035617,530638409,862981875,954810722,205034850,199075945,750488325,866804130,545451191,41677012,122300401,917102243,579777130,100964169,709207433,80064428,339685382,818018432,284474662,866223391,65822647,126640518,946149812,388420899,894496688,829373035,478440002,178234635,701625785,117955094,608600024,179455206,99677781,705818269,499358984,988295282,456418949,994189951,699839904,189003755,878383355,898009066,584915147,602771376,271441457,895573679,623331246,641533657,331670658,752642404,395856947,802902317,135662674,299387577,649899616,650158085,201960082,467119739,186877988,683520434,764528113,559823036,222931699,744519829,353270970,724650002,984719756,463468255,930296202,512616194,712685509,773886318,593867395,36645612,543175227,478440002,131134113,831306131,355161602,771989188,263172053,834496924,755162373,361933532,155973787,645356333,113942790,652225820,358267507,847870849,977931833,64598107,819936389,893553104,562611447,187170310,915353212,933993763,624517078,45873165,689494567,97143136,430357548,668338371,117201581,206669340,847298046,158322526,878526796,375577819,457098684,252922465,916469405,438567940,48005703,419936973,680460707,159649444,626855763,209597087,410107084,471836905,292304210,735603866,242539468,178234635,831306131,535238994,59494193,476799691,968501121,540277055,461491956,68737987,863270923,353144420,822230788,361316257,67989192,558025564,74211744,223351881,34979190,108996055,778504429,403506638,132154703,151348580,842372504,264215529,908341751,316650988,650350066,966947295,481842683,681692136,361178351,672704800,393399099,890894687,972862212,769164197,433144722,955907110,565947295,938334015,199412556,679118448,146827994,729953487,930971844,993222949,814304208,258062617,765449600,701625785,355161602,59494193,587593851,5365552,497546690,69806404,991530848,599222265,394262498,884710646,354413505,894001003,601632788,92563361,184620242,392904213,204912094,279344217,949303355,574783146,303857695,323493874,14950217,437256631,81895908,490710816,824860260,217400630,852733023,88356271,768244371,80225053,801404895,299337290,381788733,178537470,842968388,366195007,976839939,349706750,611303358,91421805,559577082,143169474,344697773,407535736,229098875,673461091,181293241,117955094,771989188,476799691,5365552,427081908,919663856,492381514,414538529,22712104,818207274,309315509,779545937,319745012,28054033,519467569,284304814,511170405,342193494,435962261,125827970,771664668,521458055,562146848,275298203,719710885,386815880,818452794,175920809,654498006,333231816,569250981,249575946,562012541,283615888,782040460,864970413,662372040,327267087,850976795,462131810,835451006,97500077,578076639,46697273,630820384,832837439,896152078,718285745,163176556,671493387,608600024,263172053,968501121,497546690,919663856,416252069,989387052,912050637,520754894,316883515,808472051,279372808,820097788,528877711,21246418,412981986,737191215,670555340,875052771,654675450,430581905,289605276,455225269,286700624,839322924,638153081,184400688,689527752,213661566,893089971,129747543,810721877,123557497,845539021,344363312,427830871,225728736,891154828,415374675,27030450,400877270,663373776,144864845,614136988,198676976,401155943,465031866,287606317,732961187,241864589,179455206,834496924,540277055,69806404,492381514,989387052,566595916,489636897,98756762,895385816,387361641,858759739,399904380,109100339,601908397,524094528,922900759,870542794,170085878,17411541,850345137,758947218,19168928,935382044,495169055,415673544,48575041,597063907,121577983,801722930,38804458,720639580,33909210,756453352,255909873,339805882,138220845,804073023,328897638,941069242,315363875,578485575,60427234,530603589,115691139,318873284,383260161,206223188,652116110,161469452,99677781,755162373,461491956,991530848,414538529,912050637,489636897,416839910,26428797,823511259,315913508,787734738,329326365,38956276,532192454,639044444,52369626,446955,395431344,291018739,124341402,82303139,441568118,363751205,923928393,965117588,641680811,190585690,715502563,396416863,634108022,316387279,630069642,353102823,853243073,937960602,736934987,403242880,928456942,541097497,916031729,179688368,662057724,132721538,718649565,922707756,987590473,811003258,257317891,767133638,705818269,361933532,68737987,599222265,22712104,520754894,98756762,26428797,640369243,437895548,930742302,403058953,945087335,655143958,148826459,759402158,269707318,313325245,755995336,651978807,485710442,492375243,967094796,998764175,666932468,745196191,422228420,971546474,496900724,178410958,416505063,99209338,413305761,136754380,637621084,722814667,522363918,189139189,714908317,328451086,704172462,968255764,451055259,922302040,508976350,713443029,778740048,602993129,49915138,560217477,499358984,155973787,863270923,394262498,818207274,316883515,895385816,823511259,437895548,239780153,733034153,205801586,748325194,458946359,953064149,862917026,437738418,531491141,974555116,870920831,705079836,764734877,312069511,435093138,141499391,220249794,897791012,447560667,973333554,655219774,893675289,576801662,891310369,615290884,116624871,202263200,2373295,669602285,195903232,810437376,186735141,451847449,935408339,407178549,994292216,199310284,264986229,89764996,537738742,48606914,988295282,645356333,353144420,884710646,309315509,808472051,387361641,315913508,930742302,733034153,230714434,703918832,246854531,958126983,452857780,12107059,646132918,740275789,183743085,80553672,915211658,27499086,721043089,888975812,595788493,674963912,352970655,903180995,429385321,111662327,351077472,35122907,350079780,74522865,576370061,662512786,463081817,130758870,657731582,272862669,649605813,915202379,399202578,871396327,458939067,664627360,731189217,556495612,4996107,516297070,456418949,113942790,822230788,354413505,779545937,279372808,858759739,787734738,403058953,205801586,703918832,181729655,725044681,436746458,932136570,132189917,819888232,967339471,466265459,420015736,311943279,508919724,244021194,412351339,119583192,199240031,877697229,428388216,955090203,637782021,877890214,562467255,877899044,602803037,105155318,191740069,992807283,661147004,188572741,804432775,182080434,448150248,932634340,405417952,993387993,199544463,266892340,92932863,541828569,53564231,994189951,652225820,361316257,894001003,319745012,820097788,399904380,329326365,945087335,748325194,246854531,725044681,273035784,985195366,481064973,268523899,47097955,291674656,904828543,928864670,957736145,200515343,936141440,104914186,812631094,892799699,571748802,122941493,650243006,333389498,574038319,259144128,575087939,300497834,803305192,890346183,691810504,360580763,888416361,504747688,882903590,149411647,634436045,107759823,696196704,902814553,970672288,797170109,246508568,758739395,699839904,358267507,67989192,601632788,28054033,528877711,109100339,38956276,655143958,458946359,958126983,436746458,985195366,702071941,198335866,403250929,268299079,518934114,240489610,360315487,432379952,675557581,411623067,580867054,289085743,369717086,49114155,600812727,128567681,812277730,53366218,739042254,55501210,781369474,284779717,372328512,174227761,843420195,371735038,988579026,367195833,634236695,119745052,593636679,182504845,389685082,458022433,284944044,734784848,247492352,189003755,847870849,558025564,92563361,519467569,21246418,601908397,532192454,148826459,953064149,452857780,932136570,481064973,198335866,699448126};
int V2[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,5,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,5,5,5,5,5,6,6,7,7,7,7,8,8,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,4,4,4,4,4,5,5,5,6,6,6,6,7,7,8,8,8,8,9,9,10,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,3,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7,7,8,8,9,9,9,10,10,11,11,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,3,3,3,3,3,3,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,10,10,10,11,11,12,12,13,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,4,4,4,4,5,5,6,6,6,7,7,8,8,8,8,9,9,10,10,11,11,12,12,13,14,14,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,6,6,6,7,7,8,8,8,9,9,9,9,10,11,11,12,13,13,14,14,15,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,4,5,6,6,7,7,7,8,8,9,9,9,9,10,10,11,12,12,13,14,14,15,15,16,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,3,3,3,3,4,4,4,4,4,4,5,6,7,7,7,8,8,9,9,9,10,10,10,10,12,13,13,14,14,15,15,16,17,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,3,3,3,4,4,4,4,4,5,5,6,6,7,7,8,8,8,9,9,10,10,10,10,11,12,13,14,14,15,15,16,17,17,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,7,8,8,9,9,9,10,10,11,11,11,12,12,14,15,15,16,16,17,17,18,19,0,0,0,0,1,1,1,1,1,1,2,2,2,2,3,3,3,4,4,4,5,5,5,5,5,6,6,7,7,8,9,10,10,10,11,12,12,13,13,13,14,15,16,17,18,18,19,19,20,20,0,0,0,0,1,1,1,1,2,2,2,2,2,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,8,9,10,10,11,11,12,13,13,14,14,15,15,17,18,18,19,19,20,20,21,22,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,4,4,4,5,5,5,5,6,6,6,6,6,8,8,9,10,11,11,12,13,13,14,14,15,15,16,17,18,19,20,20,21,21,22,22,0,0,0,1,1,1,1,2,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,6,6,7,7,8,9,10,11,12,12,12,14,14,15,16,16,17,17,19,20,20,21,21,22,22,23,24,0,0,1,1,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,6,7,7,7,8,9,10,11,12,13,13,14,15,16,16,17,17,18,19,20,21,22,22,23,23,24,24,0,0,1,1,1,1,2,2,2,3,3,3,3,4,4,5,5,5,5,6,6,6,6,7,7,7,7,9,10,11,12,12,13,13,15,16,16,17,17,18,18,20,21,21,22,23,23,24,24,25,0,0,1,1,1,2,2,2,3,3,3,3,4,4,5,5,5,6,6,6,6,7,7,7,7,7,7,9,10,11,12,13,14,14,16,17,17,18,18,19,19,21,22,22,23,24,24,25,25,26,0,1,1,1,1,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,7,8,8,9,11,12,13,14,15,15,16,17,18,19,19,20,20,22,23,23,24,25,25,25,26,27,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7,8,8,8,10,11,12,13,14,15,16,17,18,19,19,20,20,21,22,23,24,25,25,26,26,27,27,0,1,1,2,2,2,2,3,3,4,4,4,4,5,5,6,6,6,6,7,7,7,7,8,8,8,8,10,11,13,14,15,16,16,18,19,19,20,20,21,21,23,24,24,25,26,26,27,27,28,0,1,1,2,2,2,3,3,4,4,4,4,4,5,5,6,6,6,7,7,7,7,8,8,8,8,8,10,12,13,14,16,16,17,18,19,20,21,21,21,22,24,24,25,26,26,27,27,28,28,0,1,1,2,2,2,3,3,4,4,4,4,5,5,6,6,6,7,7,7,7,8,8,8,8,8,8,11,12,14,15,16,17,17,19,20,20,21,21,22,22,24,25,25,26,27,27,28,28,29,1,1,1,2,2,3,3,3,4,4,4,4,5,5,6,6,6,7,7,7,7,8,8,8,8,8,8,11,12,14,15,16,17,17,19,20,20,21,22,22,23,24,25,26,26,27,27,28,29,29,1,1,2,2,3,3,3,4,4,5,5,5,6,6,7,7,8,8,8,9,9,9,10,10,10,11,11,13,15,16,18,19,19,20,21,22,23,24,24,25,25,27,28,28,29,29,30,30,31,32,1,1,2,2,3,3,4,4,5,5,6,6,6,7,7,8,8,9,9,10,10,11,11,11,12,12,12,15,16,18,19,20,21,21,23,24,24,25,26,26,27,28,29,30,30,31,31,32,33,33,1,1,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,16,18,19,21,22,22,23,24,25,26,27,27,28,28,30,31,31,32,32,33,33,34,35,1,2,2,3,3,4,4,5,6,6,7,7,7,8,9,10,10,11,11,12,12,13,13,14,14,15,15,18,19,21,22,23,24,24,26,27,27,28,28,29,29,31,32,32,33,34,34,35,35,36,1,2,2,3,3,4,5,5,6,6,7,7,8,9,10,10,11,12,12,12,13,14,14,15,16,16,16,19,20,22,23,24,25,25,27,28,28,29,29,30,30,32,33,33,34,35,35,36,36,37,1,2,2,3,4,4,5,6,6,7,7,8,8,9,10,11,11,12,13,13,14,15,15,16,16,17,17,19,21,22,24,25,26,26,28,28,29,30,30,31,31,33,34,34,35,36,36,37,37,38,1,2,2,3,4,4,5,6,7,7,8,8,8,9,10,11,12,12,13,13,14,15,16,16,17,17,17,20,21,23,24,25,26,26,28,29,30,30,31,31,32,33,34,35,36,36,37,37,38,38,1,2,3,4,4,5,5,6,7,8,8,9,9,10,11,12,13,14,14,15,16,16,17,18,18,19,19,21,23,24,26,27,28,28,29,30,31,32,32,33,33,35,36,36,37,38,38,39,39,40,1,2,3,4,5,5,6,7,8,8,9,9,9,10,12,13,13,14,15,16,17,17,18,19,19,20,20,22,24,25,27,28,28,29,30,31,32,33,33,34,34,36,37,37,38,38,39,39,40,41,1,2,3,4,5,5,6,7,8,8,9,9,10,11,12,13,14,15,16,16,17,18,19,19,20,20,20,23,24,26,27,28,29,30,31,32,33,33,34,34,35,36,37,38,39,39,40,40,41,41,1,3,3,4,5,6,6,7,8,9,9,10,10,11,13,14,14,16,16,17,18,19,19,20,21,21,21,24,25,27,28,29,30,30,32,33,33,34,35,35,35,37,38,39,39,40,40,41,42,42,2,3,4,5,5,6,7,8,8,9,9,10,10,11,13,14,15,16,17,17,18,19,20,20,21,21,22,24,26,27,28,29,30,31,32,33,34,35,35,36,36,38,38,39,40,40,41,41,42,43,2,3,4,5,5,6,7,8,9,9,10,10,10,12,13,15,15,17,17,18,19,20,20,21,21,22,22,25,26,28,29,30,31,31,33,34,34,35,36,36,36,38,39,40,40,41,41,42,43,43,2,3,4,5,6,6,7,8,9,9,10,10,11,12,14,15,16,17,18,18,19,20,21,21,22,22,23,25,27,28,29,30,31,32,33,34,35,35,36,36,37,38,39,40,41,41,42,42,43,44,2,3,4,5,6,7,8,9,10,10,11,12,12,14,15,17,17,19,19,20,21,22,22,23,24,24,24,27,28,30,31,32,33,33,35,36,36,37,38,38,38,40,41,42,42,43,43,44,45,45,2,3,4,6,7,7,8,10,10,11,12,13,13,15,16,18,18,20,20,21,22,23,23,24,24,25,25,28,29,31,32,33,34,34,36,37,37,38,38,39,39,41,42,43,43,44,44,45,46,46,2,4,5,6,7,8,9,10,11,11,12,13,14,15,17,18,19,20,21,21,22,23,24,24,25,25,26,28,30,31,32,33,34,35,36,37,38,39,39,40,40,42,43,43,44,44,45,45,46,47,2,4,5,6,7,8,9,10,11,12,13,14,14,16,18,19,20,21,22,22,23,24,25,25,26,26,26,29,30,32,33,34,35,36,37,38,39,39,40,40,41,42,43,44,45,45,46,46,47,47,2,4,5,6,7,8,9,11,12,13,14,14,15,16,18,19,20,21,22,23,24,25,25,26,26,27,27,29,31,32,34,35,36,36,38,38,39,40,40,41,41,43,44,44,45,46,46,47,47,48,3,4,5,7,8,8,10,11,12,13,14,15,15,17,19,20,21,22,23,23,24,25,26,26,27,27,27,30,31,33,34,35,36,37,38,39,40,40,41,41,42,43,44,45,46,46,47,47,48,48,3,4,5,7,8,9,10,12,13,14,15,15,16,17,19,20,21,22,23,24,25,25,26,27,27,28,28,30,32,33,35,36,37,37,39,39,40,41,41,42,42,44,45,45,46,47,47,48,48,49,3,5,6,7,8,9,11,12,14,14,15,16,17,18,20,21,22,23,24,24,25,26,27,27,28,28,29,31,33,34,35,36,37,38,39,40,41,42,42,43,43,45,46,46,47,47,48,48,49,50,3,5,6,8,9,10,11,13,14,15,16,17,17,19,20,22,22,24,24,25,26,27,27,28,28,29,29,32,33,35,36,37,38,38,40,41,41,42,43,43,44,45,46,47,47,48,48,49,50,50};
int main(){
    for(scanf("%d",&T);T--;){
        scanf("%d%d",&n,&m);ans=0;
        if(n>=300&&m>=300)ans+=1ll*V2[((n/300)-1)*50+m/300-1]*1000000007+V1[((n/300)-1)*50+m/300-1];
        A=(n/300)*300;B=(m/300)*300;
        for(i=1;i<=n;i++)for(j=B+1;j<=m;j++)ans+=__gcd(i&j,i|j);
        for(i=A+1;i<=n;i++)for(j=1;j<=m;j++)ans+=__gcd(i&j,i|j);
        for(i=A+1;i<=n;i++)for(j=B+1;j<=m;j++)ans-=__gcd(i&j,i|j);
        printf("%I64d\n",ans);
    }
}