lucky-numbers-3

After India vs South Africa Match , Ananth and Arpit  got bored and started playing  a Game. 

The Game goes as follows.
The Game consists of two players and are given 2 numbers P and Q in the beginning .
In each turn one of the player can select any of the two numbers and subtract K times the other number from the selected    number where  k>0 and replaces the selected number with the result.
If a player cannot play the step -2 without making any one of the 2 numbers ≤ zero then he will lose.

If the initial numbers are 5 and 3
Ananth will start the game . He will select 5 and replaces it with
   5-3k where k = 1 [ He cannot substitute the number with k = 2
   because 5-6 < 0 and he cannot select 3 because 3-5k ≤0 for all K >
   0 ]
Now the numbers are  2 and 3 Arpit selects 3 and replaces it with
   3-2*k where k = 1.
Now the numbers are 2 1 and Ananth selects 2 and replaces it with
   2-1*k where k = 1.
Now the numbers are 1 1 and Arpit Lose the game as he cannot make a
   move without making any one of the numbers ≤ zero

Here [5,3] is a winning position for Ananth. Given that Ananth always starts the game and [P1,P2] and [Q1,Q2], find the Number of winning positions of Ananth [P,Q]  such that P1 ≤ P ≤ P2 and Q1 ≤ Q ≤ Q2 

Input

First Line of the Input file contains T. Next T lines contains 4 numbers in each line P1 P2 Q1 and Q2

Output:

Print the result for each test case in  a new line

Constraints :

1 ≤ T ≤ 100.

1 ≤ P1 ≤ P2 ≤ 1000000.

1 ≤ Q1 ≤ Q2 ≤ 1000000. 

SAMPLE INPUT
2
5 5 3 3
5 5 8 8

SAMPLE OUTPUT
1
0

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: