G. Maximum Xor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Thomas is trying to do his math homework! Tired of Thomas constantly solving his homework too quickly and having fun in class, his math teacher has decided to assign him a large number of easy problems to keep him busy. Thomas could finish his homework first, but his stamina is capping in Honkai Star Rail. As a result, he has asked you to help him finish his math homework!

There are $$$t$$$ ($$$1\leq t\leq 2\cdot 10^5$$$) math problems that Thomas must solve. Each can be expressed as $$$3$$$ integers, $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1\leq x,y,z\leq 10^8$$$). For each problem, Thomas must find the maximum value of $$$(v+x)\oplus (v+y)$$$, where $$$0\leq v \lt z$$$ and $$$\oplus$$$ denotes the bitwise XOR operation.

Input

In the first line, there is the single value $$$t$$$. In each of the following $$$t$$$ lines are $$$3$$$ integers, denoting $$$x$$$, $$$y$$$, and $$$z$$$ in that order respectively.

Test cases are enumerated from $$$1$$$ to $$$20$$$. Note the the data will not include samples.

Tests $$$1$$$-$$$5$$$: $$$x,y,z\leq 100$$$

Tests $$$6$$$-$$$8$$$: $$$x,y,z\leq 1000$$$

Tests $$$9$$$-$$$20$$$: No additional constraints.

Output

Output $$$t$$$ lines, the $$$i$$$-th line containing one integer denoting the solution to the $$$i$$$-th problem.

Examples
Input
5
7 5 5
5 6 8
3 3 3
1 3 2
5 1 5
Output
14
15
0
6
12
Input
5
7 3 4
7 2 2
4 7 8
2 5 3
0 4 5
Output
12
11
15
7
12
Note

For the first multitest of the first sample, $$$x=7$$$, $$$y=5$$$, and $$$z=5$$$. The possible values for $$$v$$$ are $$$0,1,2,3,$$$ and $$$4$$$. The values of $$$(v+x)\oplus (v+y)$$$ for each value of $$$v$$$ are $$$2$$$, $$$14$$$, $$$14$$$, $$$2$$$, and $$$2$$$ respectively. The minimum value among them is $$$2$$$, and it is the answer to this multitest.