Home » Problems (easy) » Open the Dragon Scroll

Open the Dragon Scroll

Problem code: DRAGNXOR

All submissions for this problem are available.

Did you ever hear about 'Dragon Food' ? Its used to refer to the chocolates bought for your loved ones :). Po offers dragon food to master Shifu, who is a famous cook in the valley of food. In return, Shifu hands over the dragon scroll to Po, which is said to hold the ingredients of the secret recipe. To open the dragon scroll, one has to solve the following puzzle.

1. Consider a N-bit integer A. We call an integer A' as shuffle-A, if A' can be obtained by shuffling the bits of A in its binary representation. For eg. if N = 5 and A = 6 = (00110)2, A' can be any 5-bit integer having exactly two 1s in it i.e., any of (00011)2, (00101)2, (00110)2, (01010)2, ...., (11000)2.

2. Given two N-bit integers A and B, find the maximum possible value of (A' xor B') where A' is a shuffle-A, B' is a shuffle-B and xor is the bit-wise xor operator.

Given N, A and B, please help Po in opening the dragon scroll.

Notes
1. xor operator takes two bit strings of equal length and performs the logical XOR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 OR only the second bit is 1, but will be 0 if both are 1 or both are 0. For eg: 5 (0101) xor 3(0011) = 6(0110). In most languages it is represented using ^ symbol. 5 ^ 3 = 6.
2. If the integer actually needs less than N bits to represent in binary, append sufficient number of leading 0 bits. For eg. as shown in the problem statement for N = 5, A = 6 = (00110)2

Input

First line contains an integer T ( number of test cases, around 100 ). T cases follow, each having N A B in a single line, separated by a space. ( 1 <= N <= 30, 0 <= A,B < 2N )

Output

For each case, output the maximum possible value of (shuffle-A xor shuffle-B) in a separate line.

Example

Input:
3
3 5 4
5 0 1
4 3 7


Output:
7
16
14

Explanation:

Case 1: 5 and 4 as 3-bit binary strings are (101)2 and (100)2 respectively. After shuffling, xor can be maximum for (110)2 ^ (001)2 = (111)2 = 7
Case 2: Maximum Possible result can be for (00000)2 ^ (10000)2 = (10000)2 = 16
Case 3: Maximum Possible result can be for (0011)2 ^ (1101)2 = (1110)2 = 14

Date:2011-08-02
Time limit:1s
Source limit:50000B
Languages:All


Comments

Loading Comments...

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

Loading Submissions...

RECENT ACTIVITY FOR THIS PROBLEM:

Loading Recent Activity...

HELP

Program should read from standard input and write to standard output.

After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

If you are still having problems, see a sample solution here.