题目描述

剪刀石头布（Rock-Paper-Scissors）是一个经典的游戏，我们用三个字符 $\tt{R},\tt{P},\tt{S}$ 依次代表石头、布、剪刀。 给出一个只包含 $\tt{R},\tt{P},\tt{S}$ 三种字符的字符串 $s = s_1s_2\dots s_n$，Alice和Bob在这个字符串上进行游戏，Alice先手，轮流执行以下操作： $\hspace{23pt}\bullet\,$选取一个长度大于等于 $2$ 的子串$^\texttt{[1]}$ $s[l..r]\ (1\le l<r\le|s|^\texttt{[2]})$ ，且 $s_l$ 在剪刀石头布意义上赢过 $s_r$，形式化的，若 $s_l$ 为 $\tt{R}$，则 $s_r$ 为 $\tt{S}$；若 $s_l$ 为 $\tt{P}$，则 $s_r$ 为 $\tt{R}$；若 $s_l$ 为 $\tt{S}$，则 $s_r$ 为 $\tt{P}$； $\hspace{23pt}\bullet\,$删除此子串，将剩余部分按原来的顺序拼接。 不能执行此操作的人将输掉此游戏。请问在双方操作最优的情况下，谁将赢得游戏？ 【名词解释】 子串$^\texttt{[1]}$：从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。我们用 $s[l..r]$ 代表字符串 $s$ 从下标 $l$ 开始、到下标 $r$ 结束的子串（双闭）。 $|s|^\texttt{[2]}$：表示字符串 $s$ 的长度。官方中文

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $t\ (1\le t\le10^4)$ 代表数据组数，每组测试数据描述如下：官方中文

第一行输入一个整数 $n\ (1\le n\le10^6)$，表示字符串的长度。 第二行输入一个仅包含 $\tt{R},\tt{P},\tt{S}$ 三种字符的字符串 $s$，表示初始字符串。官方中文

除此之外，保证单个测试文件的 $n$ 之和不超过 $10^6$ 。官方中文

输出格式

对于每组测试数据，输出一行一个字符串。如果Alice将赢得游戏，输出 $\tt{Alice}$；否则，输出 $\tt{Bob}$。官方中文