3
3 5
0 20 5
8 15 3
12 16 2
2 3 7 8 11
1 3
0 999999999999997 99999999999999
1 7 2
2 3
0 999999999999999 123456789
5 999999999999999 987654321
50000 99999 75008