402823: GYM100889 G Gift Pack

You want to buy a gift pack for a party, and you figure what better than a fine collection of wine.

The wine cellar has gift packs containing three wine bottles each. But the old salesman does not remember the exact ages of the wine bottles. He only remembers that the first bottle in the pack is aged somewhere between L and R(both inclusive), the second bottle is at-most A years old and the third bottle is at-most B years old. Note that a bottle can be 0 years old too.

Being a wine connoisseur you know that if the age of first bottle is x, second bottle is y and third bottle is z, then the combined deliciousness of the gift pack will be

where '^' is bitwise XOR and '&' is the bitwise AND operator.

You want to know what can be the maximum deliciousness for each of the N gift packs. You have the information given by the salesman for each pack.

First line contains N(1 ≤ N ≤ 10⁴), the number of gift packs in the cellar. Next, N lines follow, i^th line describing i^th gift pack. Each line has four integers L, R, A and B(0 ≤ L ≤ R ≤ 10¹⁸ and 0 ≤ A, B ≤ 10¹⁸).

Print N lines, i^th line containing the answer for the i^th gift-pack.

2
0 1 1 1
0 2 2 2

3
8

Sample test case 1:

One possible answer is x = 0, y = 1, z = 1.

Sample test case 2:

One possible answer is x = 1, y = 2, z = 2.