2
5 2 1
0 3
1234567890 3
3154510113 3
180000000000 3
359999999999 3
5 10 1
90000000000 8
180000000000 7
260000000000 9
260000000001 1
260000000002 1