Bita has learned bitwise-operations recently. She is doing some experiments with these operations now. Whenever she becomes happy, she frees doves. At this moment, she becomes happy when the following equation becomes correct for some integers a, b and k: (a & b) & (1 << k) ≠ 0
where ‘&’ is bitwise AND operator, ‘<<’ is bitwise left-shift operator.
You’ll be given a, k, L and R. Find out the values of b in the range [L, R] for which Bita becomes happy. Calculate the summation of those b values. If Bita never becomes happy, the summation is 0. Since Bita dislikes printed numbers, you have to tell whether this summation is odd or even.
Input
Input will start with an integer T, the number of test cases.
In each test case, there will be 4 integers a, k, L, R in a line.
Constraints:
1 <= T <= 105
1 <= a, L, R <= 109
0 <= k <= 30
L <= R
Output
For each test case, if the summation described in the statement is odd, print "Odd", otherwise print "Even" in a single line.
Sample
| Input | Output |
|---|---|
2 5 2 1 6 5 0 14 17 | Odd Even |
In the first case, the valid values of b are 4, 5, 6. The summation is: (4+5+6) = 15, which is odd. | |
Notes:
The '&' (bitwise AND) operator takes two numbers as operands and does AND on every bit of two numbers. The result of AND is 1 only if both bits are 1, otherwise the result of AND is 0.
For example, (16 & 11) = 12. It will be understandable if the numbers are converted to binary: (1110(2) & 1011(2) ) = 1010(2)The '<<' (bitwise left-shift operator) takes two numbers, left shifts the bits of the first operand, the second operand decides the number of places to shift.
For example, (1 << 3) = 8. Because, the binary form of 1 is 1(2) and after shifting it 3 places to left, it will be 1000(2), which is 8 in decimal.
