"Educational"

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>  
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
double eps = 1e-12;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define umap unordered_map
#define uset unordered_set
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define INF 2e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend
#define sz(x) ((ll)(x).size())
#define max3(a,b,c) max(max((a),(b)),(c))
#define max4(a,b,c,d) max(max((a),(b)),max((c),(d)))
#define min3(a,b,c) min(min((a),(b)),(c))
#define min4(a,b,c,d) min(min((a),(b)),min((c),(d)))

template<class T>
void swp(T&a,T&b)
{
    T temp=a;
a=b;
b=temp;
}


// Useful Funcs

// smallest prime divisor
// int smp[100001]={0};
// void calcPrimes(){
//     forn(i,100001){
//         smp[i]=i;
//     }
//     ll ct=2;
//     while(ct*ct<100001){
//         if(smp[ct]==ct){
//             for(ll j=ct*ct;j<100001;j+=ct){smp[j]=ct;}}
//         ct+=1;
//     }
// }


ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;}

// Recursive function to calculate gcd
long long gcd(long long a, long long b){
    if(b==0)
        return a;
    return gcd(b,a%b);
}

/* Iterative Function to calculate (x^y)%p in O(log y) */
long long modex(long long x, unsigned int y, long long p)
{
    long long res = 1;     // Initialize result
    x = x % p; // Update x if it is more than or
                // equal to p
    if (x == 0) return 0; // In case x is divisible by p;
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;
        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}

int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;

        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;

        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);

        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }

    // We reach here when element is not
    // present in array
    return -1;
}

// STL binary search functions
// binary_search(start_ptr, end_ptr, num)
    // returns true if element present,
    // otherwise returns false.

// upper_bound(start_ptr, end_ptr, num)
    // returns the first index having value
    // greater than num.
    // If there is no such index, then returns
    // length of array.

// lower_bound(start_ptr, end_ptr, num)
    // returns the fiirst index having value
    // not less than num

// Subtract v.begin() or a(in case of array) to get index.

// Pointers
// for array->  a, a+x
// for vector-> v.begin(), v.begin()+x, v.end()
 


const ll MOD = 998244353;
const ll mod = 1e9+7;

void solve(){
    string s;
    cin>>s;
    ll n = sz(s);

    vv64 dp(n,v64(n));

    for(ll l=2;l<=n;l+=2){
        for(ll i=0;i<=n-l;++i){
            ll j = i+l-1;
            if(l==2){
                if(s[i]==s[j]) dp[i][j]=3;
                else dp[i][j]=1;
            }
            else{
                ll res1=0,res2=0;
                //a[i]
                ll r1=0,r2=0;
                //a[i+1]
                if(dp[i+2][j]!=3) r1=dp[i+2][j];
                else if(s[i+1]<s[i]) r1=2;
                else if(s[i+1]==s[i]) r1=3;
                else r1=1;
                //a[j]
                if(dp[i+1][j-1]!=3) r2=dp[i+1][j-1];
                else if(s[j]<s[i]) r2=2;
                else if(s[j]==s[i]) r2=3;
                else r2=1;
                if(r1==2 || r2==2) res1=2;
                else if(r1==3 || r2==3) res1=3;
                else res1=1;  

                //a[j]
                r1=0;
                r2=0;
                //a[i]
                if(dp[i+1][j-1]!=3) r1=dp[i+1][j-1];
                else if(s[i]<s[j]) r1=2;
                else if(s[j]<s[i]) r1=1;
                else r1 = 3;
                //a[j-1]
                if(dp[i][j-2]!=3) r2=dp[i][j-2];
                else if(s[j-1]<s[j]) r2=2;
                else if(s[j-1]>s[j]) r2=1;
                else r2=3;
                if(r1==2 || r2==2) res2=2;
                else if(r1==3 || r2==3) res2=3;
                else res2=1;  

                if(res1==1 || res2==1) dp[i][j]=1;
                else if(res1==3 || res2==3) dp[i][j]=3;
                else dp[i][j]=2;                
            }
        }
    }
    if(dp[0][n-1]==1){
        cout<<"Alice\n";
    }
    else if(dp[0][n-1]==2){
        cout<<"Bob\n";
    }
    else{
        cout<<"Draw\n";
    }
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
    fast_cin();
    ll t;
    cin >> t;
    for(int it=1;it<=t;it++) {
        solve();
    }
    return 0;
}

Did you see the constraints?

Try DP!