文字列 \(S\) に対し、\(d[S]\) を \(S\) から始めたとき先手必勝かを表す bool 値とします。

遷移は \(S\) から \(1\) 手で到達可能な文字列 \(S'\) であって \(d[S']\) が false であるようなものが存在する場合は true、そのような \(S'\) が存在しない場合は false であるという遷移で計算することができます。

引数としてあり得るものは一見 \(N!!\) 通りあるように見えますが、実はこの遷移で必要な引数の個数は \(F_{N+1}\) 個以下（\(F_n\) はフィボナッチ数）であることが証明できます。

証明：

元の \(N\) 個の石のうち、現在どの石が残っているかを表した 01 文字列 \(T\) を用意します。\(T\) の中の 0 の個数は偶数である必要があり、さらに \(T\) に現れる \(0\) の連続区間の長さは必ず偶数になります。

ここで、そのような条件を満たす \(T\) の個数 \(a_N\) とします。\(T_1\) が 1 である場合は残り \(N-1\) 文字が同じ条件を満たす必要があるため \(a_{N-1}\) 通り、0 である場合は \(2\) 文字目も 0 である必要があるため \(a_{N-2}\) 通りであるため \(a_N=a_{N-1}+a_{N-2}\) が成り立ちます。\(a_0=a_1=1\) であるため、\(a_N=F_{N+1}\) が成り立ちます。したがって、遷移で用いられる文字列の個数は \(F_{N+1}\) 個以下であることが分かります。

以上より、\(S\) から遷移を全て計算することでこの問題を解くことができます。無駄な遷移を行わず、同じ文字列に対しては計算を何回も行わないように注意してください。

実装例(Python3)

from functools import cache


@cache
def f(now: int):
    n = (now.bit_length() + 1) >> 1
    for i in range(n - 1):
        if ((now >> (2 * i)) & 3) == ((now >> (2 * (i + 1))) & 3):
            continue
        if not f(((now >> (2 * (i + 2))) << (2 * i)) | (now & ((1 << (2 * i)) - 1))):
            return True
    return False


for _ in range(int(input())):
    n = int(input())
    s = input()
    now = 0
    for c in s:
        now <<= 2
        now += ord(c) - ord("A") + 1
    print("Alice" if f(now) else "Bob")