Problem Statement

There are $K+1$ piles of stones. The $i$-th pile has $A_i$ stones. Alice and Bob play a game. In this game, they alternately take turns with Alice moving first. On each turn, the following operation is performed exactly $K$ times.

• Choose a pile with one or more stones, and remove one or more stones from it. Here, the same pile may be chosen multiple times within the same turn.

The player who is unable to perform the operation $K$ times on their own turn loses the game. Which player wins when both players play optimally?

You are given $T$ test cases; solve each of them.

Constraints

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq K \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• The sum of $K$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case $\mathrm{case}_t$ is given in the following format:

K
A_1 A_2 \dots A_{K+1}

Output

Output $T$ lines. The $i$-th line should contain Alice if Alice wins when both players play optimally for the $i$-th test case, and Bob if Bob wins.