Neo-Nim#13019

Neo-Nim

2 seconds
512 megabytes
Very hard

There are piles of stones. The -th pile initially contains a_i stones. Additionally, an integer is given.

Ana and Bob play a game with these stones, alternating turns with Ana going first. The moves are defined as follows.

The player who cannot make a move loses. Determine the winner assuming both players play optimally.

Input

The first line contains an integer – the number of test cases.

The first line of each test case contains two integers and – the number of piles and the maximum limit for Ana’s move.

The second line of each test case contains integers a_i – the number of stones in each pile.

1 \le n \le 10^5,

2 \le k \le 10^5,

1 \le a_i \le 10^5,

the sum of over all test cases does not exceed 3 \cdot 10^5.

Output

For each test case, output Ana if Ana wins, and Bob if Bob wins.

Examples

Example

Loading
Loading

Note

In the first sample, n = 3, k = 2, a = (2, 5, 8).

One of the possible game scenarios could be as follows.

  • Ana removes two stones from the third pile. After this move becomes (2, 5, 6).

  • Bob removes one stone from the first pile. After this move becomes (1, 5, 6).

  • Ana removes two stones from the second pile. After this move becomes (1, 3, 6).

  • Bob removes one stone from the third pile. After this move becomes (1, 3, 5).

  • Ana removes two stones from the third pile. After this move becomes (1, 3, 3).

  • Bob removes one stone from the third pile. After this move becomes (1, 3, 2).

  • Ana removes two stones from the second pile. After this move becomes (1, 1, 2).

  • Bob removes one stone from the third pile. After this move becomes (1, 1, 1).

  • It is Ana’s turn now, but she cannot make a move. Ana loses and Bob wins.

In the first sample, Bob wins.

In the second sample, Bob wins.

In the third sample, Ana wins.