Description

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 modify the value of $s$ to $x$, subject to the following conditions:

• It must satisfy $x < 2^n$;
• It must satisfy $s \cup x = 2^n - 1$, where $\cup$ denotes the bitwise OR operation;
• The cost you need to pay is $s \oplus x$, where $\oplus$ denotes the bitwise XOR operation.

You need to find the minimum sum of costs required to make $s = t$.

Input Format

Each test contains multiple test cases.

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

Each test case is given in a following line, containing three integers $n, s, t$.

Output Format

For each test case, output a single integer on a line, representing the minimum sum of costs required to make $s = t$.

3
2 1 2
3 1 1
5 1 4

3
0
57

Hint

Sample Explanation #1

For the first test case, since $1 \cup 2 = 3$, you can directly change the value of $s$ from $1$ to $2$, with a cost of $1 \oplus 2$, which is $3$. It can be proven that the minimum sum of costs required to make $s = t$ is $3$.

For the second test case, no operation is needed to satisfy $s = t$.

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$.

Subtasks are used in this task.

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