Alice 和 Bob 在一个单行棋盘上玩游戏，棋盘上有若干个格子。一些格子（可能没有）中写有玩家的名字，即 “Alice” 或 “Bob”。其他格子初始为空。

游戏从 Alice 开始，两位玩家轮流行动。在每一轮中，当前玩家选择一个空白格子，要求该格子的相邻格子中没有写有该玩家自己的名字，然后在该空白格子中写上自己的名字。注意，相邻格子中是否有对手的名字并不影响选择。

无法进行移动的玩家输掉游戏。给定棋盘的初始状态，确定在双方最优策略下，Alice 和 Bob 谁会获胜。

输入格式

输入包含一个或多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 2 \times 10^5$)，表示测试用例的数量。接下来是 $t$ 个测试用例的描述，每个测试用例格式如下：

$n$ $s$

整数 $n$ 表示棋盘上的格子数 ($1 \le n \le 2 \times 10^5$)。棋盘的初始状态由长度为 $n$ 的字符串 $s$ 给出。

对于每个 $i$ ($1 \le i \le n$)，字符串 $s$ 的第 $i$ 个字符 $s_i$ 为 ‘a’、‘b’ 或 ‘.’，表示从左往右第 $i$ 个格子的初始状态。其中，若 $s_i$ 为 ‘a’，则表示第 $i$ 个格子包含 Alice 的名字；若为 ‘b’，则表示包含 Bob 的名字；若为 ‘.’，则表示该格子为空。

保证初始棋盘中不存在两个相邻的格子写有相同的名字。

所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，如果 Alice 获胜，输出 alice；如果 Bob 获胜，输出 bob，每行输出一个结果。

样例

输入 1

3
2
..
3
.a.
4
ab..

输出 1

bob
bob
alice