Background

Year after year under the peach tree,
Watching one become two.
Little wishes often gestured,
"Come true soon, please do!"
Yet unaware of his presence beneath the same tree.
Though "meeting" seems separated by the ends of the earth,
Around the corner, fate brings us together—
Oh, destiny, destiny!

Problem Description

This problem uses multiple test cases.

Xinxin has a sequence from $1$ to $n$ and wants to perform the following two operations:

Operation 1: Delete all elements at odd positions.
Operation 2: Delete all elements at even positions.

After performing $k$ operations, exactly one number remains. Given the sequence of operations, determine the final remaining number.

Input Format

• The first line contains a positive integer $T$, the number of test cases.
• For each test case:
  • The first line contains two integers $n$ and $k$.
  • The second line contains $k$ integers representing the operations (1 for Operation 1, 2 for Operation 2).

Output Format

Output $T$ lines, each containing the answer for the corresponding test case.

4
5 2
1 1
8 3
2 2 2 
8 3 
1 1 1
8 3
1 2 1

4
1
8
6

Hint

Explanation

Sample Explanation:
For the first test case, the sequence evolves as:
$\{1,2,3,4,5\} \to \{2,4\} \to \{4\}$.

Constraints

• For $30\%$ of the data: $n \leq 5 \times 10^5$.
• For $100\%$ of the data:
  • $1 \leq T \leq 10$,
  • $1 \leq n \leq 10^{18}$.
• It is guaranteed that exactly one number remains after $k$ operations for all test cases.