Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

dp

games

two pointers

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Letter Picking

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputAlice and Bob are playing a game. Initially, they are given a non-empty string $$$s$$$, consisting of lowercase Latin letters. The length of the string is even. Each player also has a string of their own, initially empty.

Alice starts, then they alternate moves. In one move, a player takes either the first or the last letter of the string $$$s$$$, removes it from $$$s$$$ and prepends (adds to the beginning) it to their own string.

The game ends when the string $$$s$$$ becomes empty. The winner is the player with a lexicographically smaller string. If the players' strings are equal, then it's a draw.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if there exists such position $$$i$$$ that $$$a_j = b_j$$$ for all $$$j < i$$$ and $$$a_i < b_i$$$.

What is the result of the game if both players play optimally (e. g. both players try to win; if they can't, then try to draw)?

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

Each testcase consists of a single line — a non-empty string $$$s$$$, consisting of lowercase Latin letters. The length of the string $$$s$$$ is even.

The total length of the strings over all testcases doesn't exceed $$$2000$$$.

Output

For each testcase, print the result of the game if both players play optimally. If Alice wins, print "Alice". If Bob wins, print "Bob". If it's a draw, print "Draw".

Example

Input

2forcesabba

Output

Alice Draw

Note

One of the possible games Alice and Bob can play in the first testcase:

- Alice picks the first letter in $$$s$$$: $$$s=$$$"orces", $$$a=$$$"f", $$$b=$$$"";
- Bob picks the last letter in $$$s$$$: $$$s=$$$"orce", $$$a=$$$"f", $$$b=$$$"s";
- Alice picks the last letter in $$$s$$$: $$$s=$$$"orc", $$$a=$$$"ef", $$$b=$$$"s";
- Bob picks the first letter in $$$s$$$: $$$s=$$$"rc", $$$a=$$$"ef", $$$b=$$$"os";
- Alice picks the last letter in $$$s$$$: $$$s=$$$"r", $$$a=$$$"cef", $$$b=$$$"os";
- Bob picks the remaining letter in $$$s$$$: $$$s=$$$"", $$$a=$$$"cef", $$$b=$$$"ros".

Alice wins because "cef" < "ros". Neither of the players follows any strategy in this particular example game, so it doesn't show that Alice wins if both play optimally.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/08/2024 16:21:57 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|