题目描述
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-2k where k = 1.
Now the numbers are 2 1 and Ananth selects 2 and replaces it with
2-1k 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
输入格式
见题面
输出格式
见题面