Background

それぞれの好きを守るため / To protect the things we each love

君と防空壕で呼吸する / Breathing with you in the air-raid shelter

Given three integers $n, s, t$, where $0 \le s, t < 2^n$.

You can perform several operations. In each operation, you can choose a non-negative integer $x$ and change the value of $s$ to $x$, subject to the following requirements:

• $x < 2^n$ must be satisfied;
• $s \lor x = 2^n - 1$ must be satisfied, where $\lor$ is the bitwise OR operation;
• You incur a cost of $s \oplus x$, where $\oplus$ is the bitwise XOR operation.

Find the minimum total cost required to make $s = t$. It can be proven that it is always possible to make $s$ equal to $t$.

Input

This problem contains multiple test cases.

The first line of input contains a positive integer $T$, representing the number of test cases.

Each test case consists of a single line containing three integers $n, s, t$.

Output

For each test case, output a single integer representing the minimum total cost required to make $s = t$.

Examples

Input 1

3
2 1 2
3 1 1
5 1 4

Output 1

3
0
57

Note 1

For the first test case, since $1 \lor 2 = 3$, you can directly change the value of $s$ from $1$ to $2$. The cost is $1 \oplus 2$, which is $3$. It can be proven that the minimum total cost to make $s = t$ is $3$.

For the second test case, no operations are needed as $s = t$ is already satisfied.

Constraints

For all test cases, it is guaranteed that:

• $1 \le T \le 100$;
• $1 \le n \le 30$;
• $0 \le s, t < 2^n$.

This problem uses bundled testing.

• Subtask 1 (12 points): $s = t$.
• Subtask 2 (15 points): $n = 1$.
• Subtask 3 (20 points): $s + t = 2^n - 1$.
• Subtask 4 (10 points): $t = 2^n - 1$.
• Subtask 5 (18 points): $t = 0$.
• Subtask 6 (25 points): No special restrictions.