100
4 2
5 2
6 2
1000 1000
1000 1
269639213832377145 218587941046017697
1000000000000000000 999999999999999999
3 2
999999999999999999 499999999999999999
4 1
668341121334534581 591831111931901869
843981288894233951 836118714517585228
945682405453310331 930137152964936188
1000000000000000000 515967293261010268
2 2
999999999999999999 2
999999999999999999 1
557773365873651863 433657597269936048
470357284687624961 465272805884932703
859339772011689605 850470686637380285
1000000000000000000 423539247696576513
885654231297338110 868783668763557338
500000000000000000 144115188075855871
475107990807880016 423838645740559881
500210432495132500 475218035771004752
1000000000000000000 288230376151711744
712434934486126209 655441552681487773
517898442890704467 510739807188874235
500000000000000000 211769623848288257
492408943224446400 449913890046268385
1000000000000000000 576460752303423488
500000000000000000 1
436799301461228071 334458662975501327
551725169707420240 447544064593549517
999999999999999999 315688400457403789
999999999999999999 281199860788757469
1000000000000000000 500000000000000000
783316230712782086 595777393360210055
1000000000000000000 1
1000000000000000000 285820433199623439
335491074737669100 334330472279997369
1000000000000000000 2
500000000000000000 249999999999999999
671128818681845645 657162671176557143
1000000000000000000 128
621848267382355875 513061740851211765
620709114489069689 561052157631120549
1000000000000000000 576460752303423487
754351791313269511 662492955343788084
999999999999999999 423539247696576512
260222518013235646 200825789885773025
999999999999999999 128
500000000000000000 127
999999999999999999 288230376151711744
500000000000000000 211769623848288256
500000000000000000 499999999999999999
500000000000000000 192574160422978183
1 1
533283560088006067 420767236738818234
5 1
500000000000000000 249999999999999998
284333970464112733 281881333309083400
500000000000000000 276797978694361766
1000000000000000000 127
606396682546681871 552445695279163753
999999999999999999 423539247696576511
629638422545821907 616905742791965238
467163576877400343 453353183346155900
1000000000000000000 499999999999999999
984169059153767404 919650541763890568
500000000000000000 288230376151711743
459303330549253103 354258733377361820
706421450595222891 577383454797323910
500000000000000000 288230376151711744
500000000000000000 144115188075855872
999999999999999999 999999999999999999
596762737424636988 549296365800254767
999999999999999999 542880209398027072
745466796740962662 566438651515174493
771714791233584502 586624946725800577
2 1
999999999999999999 499999999999999997
999999999999999999 999999999999999998
999999999999999999 576460752303423488
500000000000000000 250000000000000000
999999999999999999 576460752303423487
500000000000000000 144023652154826936
999999999999999999 288230376151711743
963604811278562488 871383857349021475
999999999999999999 499999999999999998
500000000000000000 2
1000000000000000000 423539247696576512
500000000000000000 500000000000000000
1000000000000000000 288230376151711743
1000000000000000000 1000000000000000000
3 1
1000000000000000000 414586384712426690
500000000000000000 128
1000000000000000000 499999999999999998
999999999999999999 127