100
4 2
5 2
6 2
1000 1000
1000 1
500000000000000000 249999999999999999
1000000000000000000 500000000000000000
999999999999999999 423539247696576511
3 2
500000000000000000 144115188075855872
1000000000000000000 1
500000000000000000 288230376151711743
500000000000000000 249999999999999998
1 1
500000000000000000 1
999999999999999999 576460752303423487
500000000000000000 144115188075855871
1000000000000000000 2
3 1
1000000000000000000 399183725730293449
873309107078573157 851976531965116124
585760340027663524 581099224598866145
870100249904674276 769518619292060461
1000000000000000000 423539247696576512
500000000000000000 2
1000000000000000000 1000000000000000000
999999999999999999 999999999999999998
949274056015286408 807500214784773280
999999999999999999 403930300029886817
500000000000000000 211769623848288256
840072972595600864 718176248883769641
999999999999999999 423539247696576512
1000000000000000000 127
999999999999999999 2
416407871401756170 351898098174462150
999999999999999999 499999999999999998
1000000000000000000 499999999999999998
2 2
472763863683535383 361381331096253760
304944716032023666 247305904498592937
1000000000000000000 576460752303423488
1000000000000000000 288230376151711743
4 1
699930361278684534 592912314607216971
1000000000000000000 423539247696576513
500000000000000000 500000000000000000
999999999999999999 576460752303423488
561747139456337108 555644121080440564
999999999999999999 499999999999999997
937680825673347759 796132733881305670
1000000000000000000 288230376151711744
500000000000000000 141932481001550261
2 1
999999999999999999 127
660090250346031183 616566760573448196
999999999999999999 128
500000000000000000 211769623848288257
999999999999999999 288230376151711744
500000000000000000 204140119122773217
437726532442854338 364042886741040349
1000000000000000000 284872099388915157
572209370934137006 543385235223631378
1000000000000000000 128
500000000000000000 217302440639268485
1000000000000000000 999999999999999999
500000000000000000 250000000000000000
999999999999999999 1
715665411333797537 661098237399127760
685374303840178430 523043308995917115
966316187604576125 871298714402182862
654565251581449094 572265827025412186
1000000000000000000 499999999999999999
1000000000000000000 576460752303423487
526615610306187810 474437867894251481
5 1
596958440772108214 460190380232043893
508124771705411312 433200242288987011
920248680058038165 806596990732773246
500000000000000000 288230376151711744
797572546408518771 692559451499996211
999999999999999999 528332129927347903
500000000000000000 128
490647352522905448 483027390212853846
366633848859111292 326278824739890730
999999999999999999 288230376151711743
287722564158777742 249250986600580845
820269355774935802 721103772257795482
999999999999999999 499999999999999999
1000000000000000000 566978777245772063
500000000000000000 127
999999999999999999 281756288642574284
500000000000000000 499999999999999999
561123808224342011 501322504023465268
954811098888955643 859794142691090836
376499148875729451 345168368014170114
999999999999999999 999999999999999999
818350057598471143 676526463450842185
810529814585660739 745895520457231373
708089485103988730 536999786777083471
650701937524199729 556692397629582053