We all know what a fibbonacci series is for those who don't it is a series of numbers where first number = 0; second number = 1; and then every number is a sum of previous two numbers.

Now we introduce a fibb-XOR and fibb-XNOR series.
A fibb-XOR series is a series in which first two numbers are given and then every number in the series is XOR of previous two numbers.

For example:-  first = a; second = b; then third = XOR(a, b) fourth=XOR(third, b),, ... n = XOR((n-1), (n-2))

Similarly, a fibb-XNOR series is a series such first two numbers are given and then
everyone number in the series is XNOR of previous two numbers.

For example: if first = a; second = b; then. third = XNOR(a, b) fourth = XNOR(third,b)
... n = XNOR((n-1), (n-2))

You will be given the first two numbers of the fibb-XOR series and also the first two numbers of the fibb-XNOR series.
Then you will be having  $q$  queries.
Each query comprises of two integers, $l$ and $r$ and you are supposed to find $sum1$ and $sum2$
1. $sum1$: sum of elements of the fibb-XOR series between the positions $l$.and $r$ (inclusive)(1-based positioning)
2. $sum2$: sum of elements of the fibb-XNOR series between the positions $l$ and $r$ (inclusive)(1-based positioning)
The answer to the query will be the number of powers of $2$ that sums to (sum1 & sum2) where & is the bitwise AND operation.

For example: 
7 can be represented as 3 powers of 2 ; 4+2+1
23 can be represented as 4 powers of 2; 16+4+2+1

Input:

The first line contains one integer $T$, the number of testcases. 

Second line contains two integers $F1$ and $S1$ denoting the first and second terms of fibb-XOR seires.

Third line contains two integers $F2$ and $S2$ denoting the first and second terms of fibb-XNOR seires.
Fourth line contains one integer $q$, denoting the number of queries.
Each of the next $q$ lines contains two integers $l$ and $r$

Output: 

Output to each test case contains $q$ lines. Each ot these lines contains one integer, denoting the number of powers of 2.

Constraints:

$1 \leq T\leq 5$
$1 \leq F1, S1, F2, S2 \leq 10^9$
$1 \leq q \leq 10^5$
$1 \leq l, r \leq 10^9$
$l < r$
$3 \leq r - l$