20
1000000000 100000
1 1 0 2
186 75
68 16 539 186
28 21
6 5 1 85919
66 39
35 2 589 66
1000000000 100000
1 1 1 1000000000
1000000000 100000
99999 1 99999 100000
78 51
3 5 5 51230
497151700 96511
9 7 6 999919625
198 81
8 5 7 83495
59 26
14 19 681 59
110 53
7 7 1 64417
1000000000 100000
999999999 1 999999999 1000000000
1000000000 1
12 7 74 12
98 59
6 30 524 98
254 99
1 8 9 74990
714311129 39521
9 5 9 999998192
46 18
7 11 9 46
693840425 90561
2 6 7 999957328
177 73
7 7 5 56401
22 21
1 4 869 22