Alice and Bob's Stone Game

Alice and Bob are playing a game with n piles of stones. The i-th pile initially contains a_i stones and the piles are arranged in non-decreasing order, i.e. a_i \le a_i+1 for all 1 \le i < n.

The players take turns making a move. In each move, a player may choose a pile i (with the convention that a₀ = 0) such that \[ a_i > a_{i-1}, \] and remove one stone from that pile. Note that if the chosen pile is not the last one, this effectively transfers a stone to the right, since the condition may then become available for the next pile; any move on the n-th pile removes a stone permanently from the game.

Alice moves first, and both players play optimally. Determine who will win the game.

inputFormat

The first line contains an integer t (1 \le t \le 10⁴), the number of test cases.

Each test case begins with an integer n (1 \le n \le 10⁵), the number of piles.

The next line contains n integers a₁, a₂, ..., a_n (1 \le a_i \le 10⁹), given in non-decreasing order (a_i \le a_i+1 for 1 \le i < n).

outputFormat

For each test case, output a single line containing the winner's name: either Alice or Bob.

sample

3
1
1
2
1 1
2
1 2

Alice
Bob
Alice