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≤T≤5
1≤F1,S1,F2,S2≤109
1≤q≤105
1≤l,r≤109
l<r
3≤r−l
Self-explanatory
