Alice and Bob are (again) playing a game. This time they are playing with Binary arrays.  A binary array is an array of integers whose elements can be either 0 or 1.  At the start of the game, each player would be given one identical binary array.

According to the game rules a player is allowed to perform exactly one type of operation. In each operation, (s)he can choose any element of his/her array and replace it with either 0 or 1. A player can perform this operation any number of times. 

The goal of the Alice is to obtain a representation where every 0’s will be further to the right than any of the 1’s; whereas the goal of Bob is to get every 1’s further to the right than any of the 0’s. The one who achieve this with minimum number of moves wins. 

Your task is to determine the winner along with the number of toggle operations he/she performed.

Input

The first line of the input is an integer t (1 <= t <= 1024), then t test cases follows. Each test case begins with an integer n (0 <= n <= 512), denoting the length of the binary array. The next line contain the binary array of length n.

Output

The winner name followed by the minimum number of operations he/she performed to win the game. In case of a draw just output "Draw" (Quotes for clarity).

Example

Input:

3
5
11100
7
0001111
9
011010010
Output: 

Alice 0
Bob 0
Alice 3