B1. Palindrome Game (easy version) 博弈论

B1. Palindrome Game (easy version)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The only difference between the easy and hard versions is that the given string ss in the easy version is initially a palindrome, this condition is not always true for the hard version.

A palindrome is a string that reads the same left to right and right to left. For example, "101101" is a palindrome, while "0101" is not.

Alice and Bob are playing a game on a string ss (which is initially a palindrome in this version) of length nn consisting of the characters '0' and '1'. Both players take alternate turns with Alice going first.

In each turn, the player can perform one of the following operations:

1. Choose any ii (1≤i≤n1≤i≤n), where s[i]=s[i]= '0' and change s[i]s[i] to '1'. Pay 1 dollar.
2. Reverse the whole string, pay 0 dollars. This operation is only allowed if the string is currently not a palindrome, and the last operation was not reverse. That is, if Alice reverses the string, then Bob can't reverse in the next move, and vice versa.

Reversing a string means reordering its letters from the last to the first. For example, "01001" becomes "10010" after reversing.

The game ends when every character of string becomes '1'. The player who spends minimum dollars till this point wins the game and it is a draw if both spend equal dollars. If both players play optimally, output whether Alice wins, Bob wins, or if it is a draw.

Input

The first line contains a single integer tt (1≤t≤1031≤t≤103). Then tt test cases follow.

The first line of each test case contains a single integer nn (1≤n≤1031≤n≤103).

The second line of each test case contains the string ss of length nn, consisting of the characters '0' and '1'. It is guaranteed that the string ss is a palindrome and contains at least one '0'.

Note that there is no limit on the sum of nn over test cases.

Output

For each test case print a single word in a new line:

• "ALICE", if Alice will win the game,
• "BOB", if Bob will win the game,
• "DRAW", if the game ends in a draw.

Example

input

Copy

2
4
1001
1
0

output

Copy

BOB
BOB

Note

In the first test case of the example,

• in the 11-st move Alice has to perform the 11-st operation, since the string is currently a palindrome.
• in the 22-nd move Bob reverses the string.
• in the 33-rd move Alice again has to perform the 11-st operation. All characters of the string are '1', game over.

Alice spends 22 dollars while Bob spends 00 dollars. Hence, Bob always wins

0个0平局

当偶数个0时

0 0  先手必须填上1个，后手借势翻转，先手无法翻转，自认倒霉填上个1

0 0 0 0  先手必须填上1，后手顺势填上1，构成两个0局面，先手被迫重蹈覆辙，必输

0 0 0 0 0 0 先手必须填上1，后手顺势补上1，构成四个0局面，先手说为什么倒霉蛋总是我，输掉

一旦是奇数

0 先手说奇数也不给我点脸色看，输掉

000 先手填上中间的1，留给后手偶数局的烂摊子，后手必输

00000 先手填上中间的1并说了声风水轮流转，后手接到4的烂摊子输掉

以此类推即可

#include<iostream>
#include<string>
#include<vector>
#include<string.h>
#include<set>
#include<algorithm>
#include<queue>
#include<map>
#include<stdio.h>
#include<math.h>
using namespace std;


int main()
{

              int t;
              
              cin>>t;
              
              while(t--)
              {
                  int n;
                  
                  string s;
                  
                  cin>>n>>s;
                  
                  int cnt=0;
                  
                  for(int i=0;i<n;i++)
                  {
                      if(s[i]=='0')
                        cnt++;
                  }
                  
                  if(cnt%2==0)
                  {
                      if(!cnt)
                      {
                          cout<<"DRAW"<<endl;
                      }
                      else
                      {
                          cout<<"BOB"<<endl;
                      }
                  }
                  else
                  {
                      if(cnt==1)
                      {
                          cout<<"BOB"<<endl;
                      }
                      else
                      {
                          cout<<"ALICE"<<endl;
                      }
                  }
              }
   

    return 0;
}