Description

There are three integers $A, B, C$, where $N_{(2)}$ denotes the binary representation of $N$ (without leading 0s).

Let $L$ be the maximum length among $A_{(2)}, B_{(2)}, C_{(2)}$. You need to construct three positive integers $X, Y, Z$ that satisfy the following conditions:

1. The lengths of $X_{(2)}, Y_{(2)}, Z_{(2)}$ do not exceed $L$.
2. The number of 1s in $A_{(2)}$ equals that in $X_{(2)}$.
3. The number of 1s in $B_{(2)}$ equals that in $Y_{(2)}$.
4. The number of 1s in $C_{(2)}$ equals that in $Z_{(2)}$.
5. $X + Y = Z$.

Input Format

The first line contains a positive integer $T$, indicating there are $T$ test cases.

The next $T$ lines each contain three positive integers $A, B, C$.

Output Format

Output $T$ lines, one answer per line.

Output the minimal $Z$. If there is no valid $Z$, output $-1$.

4
7 6 9
1 1 1
1 1 4
3 3 9

10
-1
2
6

Hint

Constraints and Notes

• For 30% of the testdata, $1 \le A, B, C \le 100$.
• For 100% of the testdata, $1 \le T \le 10$, $1 \le A, B, C \le 2^{30}$.

Translated by ChatGPT 5