Alice 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".


-----Examples-----

Input
2
forces
abba
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.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Amortized analysis

Game theory

Constructive algorithms
Skill types: Dynamic programming

Amortized analysis

Starter code:

Solutions:
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	s = input()[:-1]
	n = len(s)
	(l, r) = (0, n - 1)
	while l < r:
		if s[l] == s[r]:
			l += 1
			r -= 1
		else:
			break
	s = s[l:r + 1]
	res = 'Draw'
	for i in range(1, len(s), 2):
		if s[i] != s[i - 1]:
			res = 'Alice'
			break
	print(res)


N = int(input())
for _ in range(N):
	S = input()
	ans = 'Draw'
	f = 0
	while len(S) != 0 and S[0] == S[-1]:
		S = S[1:-1]
	for i in range(len(S) // 2):
		if ord(S[2 * i]) != ord(S[2 * i + 1]):
			ans = 'Alice'
			print(ans)
			f = 1
			break
	if f == 0:
		print('Draw')


t = int(input())
for i in range(t):
	s = input()
	while s and s[-1] == s[0]:
		s = s[1:-1]
	d = 1
	for j in range(len(s) // 2):
		if s[j * 2] != s[j * 2 + 1]:
			d = 0
	if d:
		print('Draw')
	else:
		print('Alice')


for _ in range(int(input())):
	s = input()
	while s and s[-1] == s[0]:
		s = s[1:-1]
	d = 1
	for j in range(0, len(s), 2):
		d *= s[j] == s[j + 1]
	print(['Alice', 'Draw'][d])


for _ in range(int(input())):
	s = input().strip()
	ans = 'Draw'
	while len(s) != 0 and s[0] == s[-1]:
		s = s[1:-1]
	for i in range(len(s) // 2):
		if s[2 * i] != s[2 * i + 1]:
			ans = 'Alice'
	print(ans)


for _ in range(int(input())):
	n = input()
	while n and n[-1] == n[0]:
		n = n[1:-1]
	x = 1
	for i in range(0, len(n), 2):
		x *= n[i] == n[i + 1]
	print(['Alice', 'Draw'][x])


for _ in range(int(input())):
	l = input()
	while l and l[-1] == l[0]:
		l = l[1:-1]
	m = 1
	for i in range(0, len(l), 2):
		m *= l[i] == l[i + 1]
	print(['Alice', 'Draw'][m])


import sys
rd = sys.stdin.readline
for _ in range(int(rd())):
	s = rd().strip()
	while s and s[-1] == s[0]:
		s = s[1:-1]
	m = 1
	for i in range(0, len(s) - 1, 2):
		m *= s[i] == s[i + 1]
	if not m:
		print('Alice')
	else:
		print('Draw')


def solution(string):
	n = len(string)
	(left, right) = (0, n - 1)
	while left < right and string[left] == string[right]:
		left += 1
		right -= 1
	flag = False
	for i in range(left, right + 1, 2):
		if string[i] != string[i + 1]:
			flag = True
			break
	if flag:
		print('Alice')
	else:
		print('Draw')
t = int(input())
for _ in range(t):
	string = input()
	solution(string)


def solve(s):
	while len(s) and s[0] == s[-1]:
		s = s[1:len(s) - 1]
	for i in range(len(s) // 2):
		if s[2 * i] != s[2 * i + 1]:
			return 'Alice'
	return 'Draw'
t = int(input())
for _ in range(t):
	s = input()
	print(solve(s))


for i in range(int(input())):
	strn = input()
	while strn and strn[-1] == strn[0]:
		strn = strn[1:-1]
	d = 1
	for j in range(0, len(strn), 2):
		d *= strn[j] == strn[j + 1]
	print(['Alice', 'Draw'][d])


def f(s) -> int:
	while s != '' and s[0] == s[-1]:
		s = s[1:-1]
	while s != '' and s[0] == s[1]:
		s = s[2:]
	if s == '':
		return 1
	else:
		return 0
n = int(input())
ans = ['Alice', 'Draw']
for _ in range(0, n):
	s = input()
	print(ans[f(s)])


for _ in range(int(input())):
	s = input()
	l = 0
	r = len(s) - 1
	c = 0
	while l < r and s[l] == s[r]:
		l += 1
		r -= 1
	for i in range(l, r, 2):
		if s[i] == s[i + 1]:
			continue
		c = 1
	if c == 0:
		print('Draw')
	else:
		print('Alice')


import sys
sys.setrecursionlimit(6100)
test = int(input())

def solve(i, j, last, turn):
	ans = False
	if i > j:
		return True
	if (i, j, last, turn) in dp:
		return dp[i, j, last, turn]
	if turn == 0:
		a = solve(i + 1, j, s[i], turn ^ 1)
		b = solve(i, j - 1, s[j], turn ^ 1)
		if a and b:
			ans = True
	else:
		if s[i] == last:
			ans |= solve(i + 1, j, s[i], turn ^ 1)
		if s[j] == last:
			ans |= solve(i, j - 1, s[j], turn ^ 1)
	dp[i, j, last, turn] = ans
	return ans
while test:
	test -= 1
	s = input()
	pal = True
	(i, j) = (0, len(s) - 1)
	while i <= j:
		if s[i] != s[j]:
			pal = False
			break
		i += 1
		j -= 1
	if pal:
		print('Draw')
		continue
	dp = {}
	if solve(0, len(s) - 1, '', 0):
		print('Draw')
	else:
		print('Alice')


def get_lst_pos(beg, ed, lst_pos):
	if lst_pos == 0:
		return beg - 1
	else:
		return ed + 1

def solve():
	s = list(input().strip())
	n = len(s)
	dp = [[0 for j in range(n)] for i in range(n)]
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			dp[i][i + 1] = 1
	for s_len in range(4, n + 1, 2):
		for beg in range(0, n - 3):
			ed = beg + s_len - 1
			if ed >= n:
				break
			if dp[beg + 1][ed - 1] == 1 and (dp[beg + 2][ed] == 1 or (dp[beg + 2][ed] == 0 and ord(s[beg]) < ord(s[beg + 1]))):
				dp[beg][ed] = 1
			elif dp[beg + 1][ed - 1] == 1 and (dp[beg][ed - 2] == 1 or (dp[beg][ed - 2] == 0 and ord(s[ed]) < ord(s[ed - 1]))):
				dp[beg][ed] = 1
			elif dp[beg + 1][ed - 1] == 0 and s[beg] != s[ed]:
				dp[beg][ed] = 1
			else:
				dp[beg][ed] = 0
	print('Alice' if dp[0][n - 1] == 1 else 'Draw')
t = int(input().strip())
for _ in range(t):
	solve()


def codeforces(s):
	n = len(s)
	dp = [0 for i in range(n - 1)]
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			dp[i] = 1
	x = n // 2
	for i in range(2, x + 1):
		tp = [0 for i in range(n - 2 * i + 1)]
		for ind in range(n - 2 * i + 1):
			a = ind + 2 * (i - 1)
			x = dp[ind + 1] or s[ind] < s[a + 1]
			y = dp[ind] or s[a + 1] < s[a]
			z = dp[ind + 2] or s[ind] < s[ind + 1]
			p = dp[ind + 1] or s[a + 1] < s[ind]
			tp[ind] = x and z or (y and p)
		dp = tp
	return dp[0]
t = int(input())
for test in range(t):
	s = input()
	if codeforces(s):
		print('Alice')
	else:
		print('Draw')


from functools import lru_cache
t = int(input())
for _ in range(t):
	s = input()
	l = len(s)
	dp = [[True for i in range(l + 1)] for j in range(l + 1)]
	for k in range(2, l + 1, 2):
		for i in range(l + 1 - k):
			j = i + k
			dp[i][j] = s[i] == s[j - 1] and dp[i + 1][j - 1] or (s[i] == s[i + 1] and dp[i + 2][j]) & (s[j - 1] == s[j - 2] and dp[i][j - 2])
	if dp[0][-1]:
		print('Draw')
	else:
		print('Alice')