1000000000
10
1 100000000 even
100000001 200000000 even
200000001 300000000 even
300000001 400000000 even
400000001 500000000 even
1 500000000 even
1 1000000000 odd
100010001 200200000 odd
200000001 404000000 even
1 404000000 odd