Background

A warm-up problem for Ysuperman’s template test.

Watch out for “Liqiu”, watch out for “Qiuli”.

Problem Description

Liqiu has an array $a$ of length $n$. All numbers are positive integers, and except for the first number, every other number equals the sum of all previous numbers.

For example, the array $[1,1,2,4,8,16]$ could be an array Liqiu has, because except for the first number $1$, every following number is the sum of the previous numbers, for instance:

• 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 tells Qiuli that the number $x$ exists in this array. Qiuli wants to know what the minimum possible value of $a_n$ is, i.e., the minimum possible value of the last number of the whole array.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases.

The next $T$ lines each contain two positive integers $n,x$.

Output Format

Output $T$ lines in total, each being the answer for one test case.

For a test case $n,x$, output one line with one positive integer, representing the minimum possible $a_n$.

3
2 2
3 2
4 2

2
2
4

3
3 1
3 2
3 4

2
2
4

3
2 6
3 6
4 6

6
6
12

3
3 3
3 6
3 12

6
6
12

Hint

Explanation for Sample 1

• For the first test case, the only possible array is $[2,2]$, so the answer is $2$.
• For the second test case, there are two possible arrays: $[2,2,4]$ and $[1,1,2]$, so the answer is $2$.
• For the third test case, there are two possible arrays: $[2,2,4,8]$ and $[1,1,2,4]$, so the answer is $4$.

Explanation for Sample 2

• For the first test case, the only possible array is $[1,1,2]$, so the answer is $2$.
• For the second test case, there are two possible arrays: $[1,1,2]$ and $[2,2,4]$, so the answer is $2$.
• For the third test case, there are two possible arrays: $[2,2,4]$ and $[4,4,8]$, so the answer is $4$.

Constraints

For the first $30\%$ of the testdata, $x$ is not divisible by $2$, i.e., $2$ is not a factor of $x$, i.e., $x$ is odd.

Another $30\%$ of the testdata satisfies that $x$ is divisible by $2^{n-2}$, i.e., $2^{n-2}$ is a factor of $x$.

Another $20\%$ of the testdata satisfies $x\le 1000$. It can be proven that under this constraint, the answer can be stored using an int variable.

For $100\%$ of the testdata, $1\le T\le 10^4$, $2\le n\le 20$, $1\le x\le 10^9$.

Translated by ChatGPT 5