시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB40232156.757%

문제

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.

입력

Each test case 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 consists of only lowercase letters. The total input length will be less than 500000 characters.

출력

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

예제 입력 1

5
aba b
bab b
aaab aab
xyz mnk
xyz xyz

예제 출력 1

Alice
Alice
Bob
Bob
Alice