5 3
1 1
2 1
1 2
3 1
1 3
124 13
9 53
9 48
9 45
239 17
656123 32767
123456789 987654321
17877019 739774528
316916535 645635236
777953686 501578876
771910531 344802412
366455240 765813441
1513656 146824633
6883317 103249755
9378439 731518241
1487215 92207331
4255769 336205752
2118488 74147079
286228 20608416
2246846 132563914
1109950 1109949
9258196 777688465
202189807 3314587
71742348 908131
268053127 2851629
59527395 692179
251698457 3813613
999999937 44
23 999999937
1000000000 1
1000000000 2
1000000000 3
1000000000 499999999
1000000000 500000000
1000000000 500000001
1 1000000000
2 1000000000
3 1000000000
499999999 1000000000
500000000 1000000000
500000001 1000000000
999999999 1000000000
1000000000 999999999
1000000000 1000000000