Optimal String Deletion Strategy

Hùng và Dũng đang chơi một trò chơi với các xâu ký tự. Sẽ có $t$ ván đấu trong trò chơi. Trong mỗi ván đấu, có một xâu ký tự $s$ gồm các chữ cái tiếng Anh thường.

Hùng đi trước và hai người chơi lần lượt thay phiên nhau. Hùng được phép xóa bất kỳ xâu con nào có độ dài chẵn (có thể rỗng) và Dũng được phép xóa bất kỳ xâu con nào có độ dài lẻ từ $s$.

Cụ thể hơn, nếu có một xâu $s = s_1s_2 ... s_k$, người chơi có thể chọn một xâu con $s_ls_{l+1} ... s_{r-1}s_r$ có độ dài đúng tính chẵn lẻ và xóa nó. Sau đó xâu sẽ trở thành $s = s_1 ... s_{l-1}s_{r+1} ... s_k$.

Sau khi xâu trở thành rỗng, ván đấu kết thúc và mỗi người chơi tính điểm số của mình cho ván đấu đó. Điểm số của một người chơi là tổng giá trị của tất cả các ký tự bị xóa bởi người đó. Giá trị của a là $1$, giá trị của b là $2$, giá trị của c là $3$, v.v., và giá trị của z là $26$. Người chơi có điểm số cao hơn sẽ thắng ván đấu. Đối với mỗi ván đấu, hãy xác định người chiến thắng và hiệu số giữa điểm số của người thắng và người thua. Giả sử rằng cả hai người chơi đều chơi tối ưu để tối đa hóa điểm số của mình. Có thể chứng minh rằng kết quả hòa là không thể xảy ra.

Dữ liệu vào

Dòng đầu tiên của đầu vào chứa một số nguyên duy nhất $t$ ($1 ≤ t ≤ 5· 10^4$) biểu diễn số lượng ván đấu.

Mỗi trong $t$ dòng tiếp theo chứa một xâu ký tự $s$ ($1 ≤ |s| ≤ 2· 10^5$) gồm các chữ cái tiếng Anh thường, biểu diễn xâu ký tự được sử dụng cho ván đấu. Ở đây $|s|$ ký hiệu độ dài của xâu ký tự $s$.

Đảm bảo rằng tổng độ dài của $|s|$ qua tất cả các ván đấu không vượt quá $2· 10^5$.

Kết quả

Đối với mỗi ván đấu, in ra một dòng duy nhất chứa một xâu ký tự và một số nguyên. Nếu Alice thắng ván đấu, xâu ký tự phải là Alice. Nếu Bob thắng ván đấu, xâu ký tự phải là Bob. Số nguyên phải là hiệu số giữa điểm số của họ với giả định cả hai người chơi đều chơi tối ưu.

Chấm điểm

Subtask 1 (30 points). $t ≤ 100$; $|s| ≤ 10$

Subtask 2 (70 points). $1 ≤ t ≤ 5· 10^4$

Ví dụ

Input

5
aba
abc
cba
n
codeforces

Output

Alice 2
Alice 4
Alice 4
Bob 14
Alice 93

Ghi chú

Đối với ván đấu đầu tiên, aba được biến đổi như sau. Alice xóa ab đạt điểm $1 + 2 = 3$, để lại a. Sau đó Bob xóa a đạt điểm $1$. Tổng điểm của Alice là $3$, của Bob là $1$. Alice thắng với hiệu số $2$.