Input
4
10 2 3 7
100 51 51 51
1234 1 100 199
1000000000 1 1 1000000000
Output
3
0
1134
0