P9532 [YsOI2023] Prefix Sum

A warm-up problem for Ysuperman’s template test. Watch out for “Liqiu”, watch out for “Qiuli”.

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.

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

#### 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