AT_abc433_g [ABC433G] Substring Game

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.

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

### Sample Explanation 1 Consider the first test case. For example, the game proceeds as follows. - Alice chooses `x`. $ T= $ `x`. - Bob chooses `o`. $ T= $ `xo`. - No matter which lowercase English letter Alice chooses and concatenates to the end of $ T $ , $ T $ will not be a substring of $ S $ , so Alice cannot make a move. At this point, Bob wins. In this test case, Bob can win no matter how Alice plays. Therefore, output `Bob`. ### 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 $ .