Problem Statement

You are given a string $S$ consisting of lowercase English letters.

Alice and Bob play the following game using this string.

• Prepare an empty string $T$.
• Starting with Alice, they take turns playing.
• On each turn, the player chooses one lowercase English letter and concatenates the chosen letter to the end of $T$. Here, the player cannot take an action such that $T$ after concatenation is not a substring of $S$.

The player who cannot make a move first loses.

Determine which player will win when both players play optimally.

You are given $T$ test cases; solve each of them.

Constraints

• $1\le T\le 10^5$
• $T$ is an integer.
• $S$ is a string consisting of lowercase English letters with length between $1$ and $2\times 10^5$, inclusive.
• The sum of the lengths of $S$ over all test cases is at most $4\times 10^5$.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format.

S

Output

Output the answers for the test cases in order, separated by newlines.

For each test case, output Alice if Alice wins when both players play optimally, and Bob if Bob wins.