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.