Cafeforces is a large online competition platform where each user has a rating that fluctuates based on their performance in each contest.

Specifically, if an account has a rating of $x$ before a contest and the performance rating in that contest is $y$, the account's rating after the contest becomes $\lceil{\frac{x+y}{2}}\rceil$, where $\lceil a\rceil$ denotes the smallest integer not less than $a$.

You have two accounts, both with an initial rating of $s$, and you have decided to participate in the next $n$ contests (you cannot choose to skip any).

Through your predictive ability, you know your performance rating for each of the upcoming contests in advance, where the performance rating for the $i$-th contest is $p_i$.

Please arrange which account participates in each contest to maximize the larger of the two accounts' ratings after the $n$ contests, and find this maximum value.

Input

The input contains multiple test cases.

The first line contains an integer $t$ ($1 \leq t \leq 2\times10^5$), representing the number of test cases. For each test case:

• The first line contains two integers $n$ and $s$ ($1 \le n \le 2\times10^5$, $0 \le s \le 10^9$).
• The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\times 10^5$.

Output

For each test case, output a single integer representing the answer.

Examples

Input 1

5
2 3
1 5
3 3
2 6 1
4 5
5 5 5 5
5 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000
10 100
97 135 103 130 147 89 93 215 175 261

Output 1

4
5
5
1000000000
219

Note

For the first test case, you can use the first account for the first contest and the second account for the second contest. The ratings of the two accounts will be $2$ and $4$, respectively, with the maximum being $4$. It can be proven that no better strategy exists.

For the second test case, you can use the first account for the first and second contests, and the second account for the third contest. The ratings of the two accounts will be $5$ and $2$, respectively, with the maximum being $5$.

For the third test case, regardless of the strategy chosen, the ratings of the two accounts will not change, so the answer is $5$.