You are given two integers A and B. Count how many numbers are there from A to B which are odd.

Input

First line contains an integer T – number of the test case. Next T lines contain two integers each, values of A and B.

Output

For each test case output the desire answer.

Example

Input:
5
1 1
1 2
2 2
2 3
1 3

Output:
1
1
0
1
2