CDGOLF1 - Alice and Bob plays again

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

Added by::(){ :|: & };:
Date:2013-08-23
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2015-02-10 10:44:05 mehmetin
Is there a classical version of this problem?

Last edit: 2014-09-15 18:10:26
2015-02-10 10:44:05 RTJ


Last edit: 2014-02-12 07:08:37
2015-02-10 10:44:05 Mitch Schwartz
Limits on t and n?

Re:(debanjan) Updated. The current test cases are not that exhaustive, I will add more test cases (without changing the constraints) soon.

Last edit: 2014-02-14 05:09:59
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.