Problem Background

This is a practice problem for Ysuperman's template testing.

Beware of the beginning of autumn, beware of Qiuli.

Problem Description

Liqiu has an array \(a\) of length \(n\), where all numbers are positive integers, and every number except the first one is equal to the sum of all preceding numbers.

For example, the array \([1, 1, 2, 4, 8, 16]\) could be an array Liqiu has, because every number after the first one is the sum of all preceding numbers, such as:

• The second number \(1 = 1\).
• The third number \(2 = 1 + 1\).
• The fourth number \(4 = 1 + 1 + 2\).
• The fifth number \(8 = 1 + 1 + 2 + 4\).
• The sixth number \(16 = 1 + 1 + 2 + 4 + 8\).

Now, Liqiu has told Qiuli that the number \(x\) exists in this array, and Qiuli wants to know the minimum possible value of \(a_n\), or the last number in the array.

Input Format

This problem contains multiple sets of test data.

The first line of input is a single number \(T\) indicating the number of test cases.

The next \(T\) lines each contain two positive integers \(n\) and \(x\).

Output Format

Output consists of \(T\) lines, each representing the answer for a corresponding test case.

For each set of data \(n\) and \(x\), output a single positive integer representing the minimum possible value of \(a_n\).

Sample Input and Output

Sample Input #1

3
2 2
3 2
4 2

Sample Output #1

2
2
4

Sample Input #2

3
3 1
3 2
3 4

Sample Output #2

2
2
4

Sample Input #3

3
2 6
3 6
4 6

Sample Output #3

6
6
12

Sample Input #4

3
3 3
3 6
3 12

Sample Output #4

6
6
12

Notes

Explanation of Sample 1

• For the first set of data, the only possible array is \([2, 2]\), so the answer is \(2\);
• For the second set of data, there are two possible arrays, \([2, 2, 4]\) and \([1, 1, 2]\), so the answer is \(2\);
• For the third set of data, there are two possible arrays, \([2, 2, 4, 8]\) and \([1, 1, 2, 4]\), so the answer is \(4\).

Explanation of Sample 2

• For the first set of data, the only possible array is \([1, 1, 2]\), so the answer is \(2\);
• For the second set of data, there are two possible arrays, \([1, 1, 2]\) and \([2, 2, 4]\), so the answer is \(2\);
• For the third set of data, there are two possible arrays, \([2, 2, 4]\) and \([4, 4, 8]\), so the answer is \(4\).

Data Range

For the first \(30\%\) of the data, \(x\) is odd, meaning \(2\) is not a factor of \(x\).

For another \(30\%\) of the data, \(x\) is divisible by \(2^{n-2}\), meaning \(2^{n-2}\) is a factor of \(x\).

For another \(20\%\) of the data, \(x \leq 1000\), and it can be proven that the answer can be stored in an int variable within this range.

For \(100\%\) of the data, \(1 \leq T \leq 10^4\), \(2 \leq n \leq 20\), and \(1 \leq x \leq 10^9\).

见题面 Input 部分

见题面 Output 部分