D. sumaXOR
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

We have an infinite matrix $$$A$$$ defined as: $$$A_{i,j} = i + j$$$ for all $$$i, j$$$ such that $$$0 \le i, j$$$.

An infinite matrix $$$B$$$ is defined as: $$$\forall i,j$$$ such that $$$0 \le i$$$ and $$$1 \le j$$$ we have $$$B_{i,j}$$$ $$$=$$$ $$$A_{i,j-1}$$$ $$$\oplus$$$ $$$A_{i,j}$$$ $$$\oplus$$$ $$$A_{i,j+1}$$$.

Here $$$\oplus$$$ denotes the bitwise XOR operator.

If you are unfamiliar with XOR, please make sure to check out Esomer's XOR ultimate guide.

You are now given $$$q$$$ queries of the type $$${a, b, c, d}$$$. You are asked to find the total sum of all $$$B_{i,j}$$$ such that $$$a \le i \le c$$$ and $$$b \le j \le d$$$.

Input

First line contains $$$q$$$, the number of queries $$$(1 \le q \le 2 \cdot 10^5)$$$.

Each query contains four numbers $$$a, b, c, d$$$, respectively. $$$(0 \le a \le c \le 2 \cdot 10^5)$$$, $$$(1 \le b \le d \le 2 \cdot 10^5)$$$.

Output

Output for each query the total sum of all $$$B_{i,j}$$$ contained in the range.

Example
Input
6
1 1 1 1
2 2 2 2
3 3 4 4
2 3 5 6
0 1 2 3
1 3 5 10
Output
0
2
28
128
29
380