给 Alice 和 Bob 一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 和一个整数 $$$k$$$ ($$$1\leq k \lt n$$$)。
如果 Alice 能够将 $$$s$$$ 的所有字符转换为零,她就获胜。如果爱丽丝无法在有限的步数内获胜,那么鲍勃就获胜。
Alice 和 Bob 轮流,Alice 先走。
- 轮到爱丽丝时,她可以选择任何 子序列 字符串 $$$y$$$ 的$$$^{\text{*}}$$$ 的长度为 $$$k$$$ 中的 $$$s$$$,然后将该子序列中的所有字符设置为零。
- 轮到鲍勃时,他可以选择任何 子字符串$$$^{\text{†}}$$$,$$$s$$$ 中的长度为 $$$k$$$,然后将该子字符串中的所有字符设置为 1。
请注意,如果在游戏过程中的任何时刻(包括在 Alice 和 Bob 的回合之间)该字符串全部由零组成,则 Alice 获胜。
确定谁以最佳发挥获胜。 字符串 $$$s$$$ 的
$$$^{\text{*}}$$$A 子序列 字符串 $$$y$$$ 的 是 $$$s$$$ 中的一组字符。请注意,这些字符不必相邻。
$$$^{\text{†}}$$$A 字符串 $$$s$$$ 的 子字符串 是 $$$s$$$ 中的一组连续字符。请注意,这些字符必须相邻。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2\leq n \leq 2\cdot 10^5$$$, $$$1\leq k \lt n$$$)。
每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,在单行上输出“爱丽丝“如果爱丽丝以最佳发挥获胜,并且”鲍勃“如果鲍勃以最佳发挥获胜。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“爱丽丝", "爱丽丝", "爱丽丝“,和”爱丽丝“将被识别为”爱丽丝".
示例
输入复制
65 2110117 410110116 10100004 111118 3101101106 4111111
输出复制
Bob Alice Alice Bob Bob Alice
注意
在第三个样本中,Alice可以选择由$$$s_2$$$组成的子序列,将$$$s$$$变成$$$000000$$$。然后她立刻就赢了。
在第四个样本中,可以证明Alice无法保证她可以在有限的移动次数内将$$$s$$$变成$$$0000$$$。