String Game

• 번갈아가면서 시퀀스의 양쪽 끝중 한쪽을 골라서 원소를 제거하는 게임이다. 가끔 문제로 등장한다. 예) 19504
• 마지막 1개가 남을때까지 원소를 제거해야 하는 규칙이라면, 마지막으로 돌을 제거하는 플레이어는 원할 경우 가장 가운데에 있는 원소가 마지막에 남도록 강제할수 있다. 상대가 맨 앞에서 제거하면 나는 맨 뒤에서 제거하고, 상대가 맨 뒤에서 제거하면 나는 맨 앞에서 제거하는 식으로, 앞에서 제거된 돌 수와 뒤에서 제거된 돌 수를 동일하게 맞춰줄수가 있기 때문이다
• 이 게임도 똑같이 접근한다. 시작 문자열 길이에서 타겟 문자열 길이를 뺀 값이, 제거해야 할 글자의 갯수이다.
• 제거해야 할 글자가 2N개라면, 앨리스가 마지막에 제거하게 된다. 앞에서 말한 전략을 이용해서 앨리스는 마지막에 남는 문자열이 앞에서 N개, 뒤에서 N개가 제거된 init[N:-N]이 되도록 만들수 있다. 그 문자열이 타겟문자열과 동일하다면, 앨리스는 항상 승리할수 있다는 말과도 동일하다. 그렇지 않고도 앨리스가 항상 이길수 있는 방법이 있을까? 마지막 직전턴까지 앞에서 N-1, 뒤에서 N-1개의 글자가 제거된 상황을 생각해보자. 여기서 마지막 턴에 밥이 앞에서 글자를 제거한다면 앨리스도 앞에서 제거를 하고, 밥이 뒤에서 제거한다면 앨리스도 뒤에서 제거할수 있다. 이렇게 해서 만들어질수 있는 문자열은 init[N-1:-(N+1)] 또는 init[N+1:-(N-1)] 가 된다. 이 두가지중 어느것이 될지는 밥의 선택에 따라서 달라지지만, 이 두가지가 모두 타겟문자열과 동일하다면, init[N:-N]이 타겟이 아니더라도 앨리스는 승리할수 있다
• 그러면 그 외에 다른 승리 방법은 없을까. 구체적으로는 init[N:-N]와 init[N-1:-(N+1)] 둘다 타겟이 아닌경우, 또는 init[N:-N]와 init[N+1:-(N-1)]가 둘다 타겟이 아닌경우에도 이길수 있는 방법이 있냐는 것인데, 대답은 불가능하다는 것이다. 밥 또한 동일한 전략을 사용해서, 최종 결과를 init[N:-N]와 init[N-1:-(N+1)] 중 하나가 되도록 강제할수 있다. 따라서 모두 타겟이 아닌경우에는 앨리스가 이길수가 없다. 이렇게 강제하는 밥의 전략은, 첫턴에 먼저 뒤에서 제거한 다음, 이어지는 턴에서 앨리스가 앞에서 제거하면 밥은 뒤에서, 앨리스가 뒤에서 제거하면 밥은 앞에서 제거하는 것을 반복한다. 그러면 마지막에 앨리스의 차례를 남기고는 앞에서 N-1개, 뒤에서 N개가 제거된 상태가 되고 앨리스가 어떤 선택을 하든 저 둘중 하나의 상태로 끝나게 된다.
• 정리하면, 제거해야할 글자가 2N개일때의 앨리스가 승리할수 있는 조건은 (init[N:-N]==target || (init[N-1:-(N+1)]==target && init[N+1:-(N-1)]== target) 이 된다
• 제거해야할 글자가 2N+1 개일때에는 마지막 턴이 밥에게 돌아오므로 승리하기가 좀더 힘들다. 비슷한 논리로 풀어보면 승리 조건은 (init[N:-(N+1)]==target && init[N+1:-N)]== target) 이 된다

"""Solution code for "BOJ 11307. String Game".

- Problem link: https://www.acmicpc.net/problem/11307
- Solution link: http://www.teferi.net/ps/problems/boj/11307

Tags: [game theory]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    for _ in range(N):
        initial, target = sys.stdin.readline().split()

        remove_count = len(initial) - len(target)
        if remove_count % 2 == 0:
            is_win_pos = initial[remove_count // 2 :].startswith(target) or (
                initial[remove_count // 2 - 1 :].startswith(target)
                and initial[remove_count // 2 + 1 :].startswith(target)
            )
        else:
            is_win_pos = initial[remove_count // 2 :].startswith(target) and (
                initial[remove_count // 2 + 1 :].startswith(target)
            )

        print('Alice' if is_win_pos else 'Bob')


if __name__ == '__main__':
    main()