A. Subtle Substring Subtraction

Alice and Bob are playing a game with strings. There will be tt rounds in the game. In each round, there will be a string ss consisting of lowercase English letters.

Alice moves first and both the players take alternate turns. Alice is allowed to remove any substring of even length (possibly empty) and Bob is allowed to remove any substring of odd length from ss.

More formally, if there was a string s=s1s2…sk the player can choose a substring slsl+1…sr−1sr with length of corresponding parity and remove it. After that the string will become s=s1…sl−1sr+1…sk.

After the string becomes empty, the round ends and each player calculates his/her score for this round. The score of a player is the sum of values of all characters removed by him/her. The value of a is 1, the value of b is 2, the value of c is 3, ……, and the value of z is 26. The player with higher score wins the round. For each round, determine the winner and the difference between winner's and loser's scores. Assume that both players play optimally to maximize their score. It can be proved that a draw is impossible.

Input

The first line of input contains a single integer tt (1≤t≤5⋅10^4) denoting the number of rounds.

Each of the next tt lines contain a single string ss (1≤|s|≤2⋅10^5) consisting of lowercase English letters, denoting the string used for the round. Here |s||s| denotes the length of the string ss.

It is guaranteed that the sum of |s||s| over all rounds does not exceed 2⋅10^5

Output

For each round, print a single line containing a string and an integer. If Alice wins the round, the string must be "Alice". If Bob wins the round, the string must be "Bob". The integer must be the difference between their scores assuming both players play optimally.

Example

input

Copy

5
aba
abc
cba
n
codeforces

output

Copy

Alice 2
Alice 4
Alice 4
Bob 14
Alice 93

Note

For the first round, "aba"−→−−Alice"aba"→"a"−→−Bob"a"→""". Alice's total score is 1+2=3. Bob's total score is 1.

For the second round, "abc"−→−−Alice"abc"→"a"−→−Bob"a"→""". Alice's total score is 2+3=5. Bob's total score is 1.

For the third round, "cba"−→−−Alice"cba"→"a"−→−Bob"a"→""". Alice's total score is 3+2=5. Bob's total score is 1.

For the fourth round, "n"−→−−Alice"n"→"n"−→−Bob"n"→"". Alice's total score is 00. Bob's total score is 14.

For the fifth round, "codeforces"−→−−Alice"codeforces"→"". Alice's total score is 3+15+4+5+6+15+18+3+5+19=93. Bob's total score is 0.

（注意子串是连续的）

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int data1[1000000];
int sum=0;
int main()
{
    long long t;
    cin>>t;
    while (t>0)
    {
        string s;
        cin>>s;
        sum=0;
        int length=s.size();
        for(int i=0;i<length;i++)
        {
            data1[i]=0;
        }
        for(int i=0;i<s.size();i++)
        {
            data1[i]=(int)(s[i]-'a'+1);
        }
        for(int i=0;i<length;i++)
        {
            sum=sum+data1[i];
        }
        if(s.size()%2==0)                                    //如果字符串长度是偶数，则Alice必赢
        {
            cout<<"Alice"<<" "<<sum<<endl;
        }
        else
        {
            if(s.size()==1)                                  //字符串长度为1的情况
            {
                cout<<"Bob"<<" "<<data1[0]<<endl;
            }
            else if(s.size()!=1)                             //字符串长度为奇数且不为1
            {
                cout<<"Alice"<<" "<<max((sum-2*data1[0]),(sum-2*data1[length-1]))<<endl;
            }
        }
        t--;
    }
    return 0;
}