Problem E
String Game

Alice and Bob are playing the following game with strings of letters.

Before the game begins, an initial string and a target string are decided. The initial string is at least as long as the target string. Then, Alice and Bob take turns, starting with the initial string. Bob goes first. In each turn, the current player removes either the first or the last letter of the current string. Once the length of the current string becomes equal to the length of the target string, the game stops. If the string at the end of the game is equal to the target string, Alice wins the game; otherwise Bob wins.

Determine who will win the game if both players are playing optimally.

Input

The input starts with $N$, the number of inputs to process. Each input consists of one line, which contains the initial string, followed by a space, followed by the target string. Each string is non-empty and consists of only lowercase letters ‘a’-‘z’.

The total length of the $2n$ strings will be at most $500\, 000$ characters.

Output

For each input, output the winner, which will either be Alice or Bob.

5
aba b
bab b
aaab aab
xyz mnk
xyz xyz

Alice
Alice
Bob
Bob
Alice