There are two integers L and R, you'll have to count how many odd numbers are there within the range from L to R inclusive.

All of you know what is an odd number. An integer that is not divisible by 2 is called an odd number.

Input

The first line will be a single integer T which denotes the test cases. Next T lines will contain L and R.

Constraints

1 <= T <= 10

1 <= L <= R <= 1000000000000000000

Output

For each case, print the count of odd numbers from L to R inclusive.

Example

Input:
3
1 1
1 3
2 3

Output:
1
2
1

[ Original Setter of this problem is Dhruba Mitra, RUET ]