Sasha 给了 Anna 一份情人节礼物 $$$a$$$ 的 $$$n$$$ 整数列表。安娜不需要这个列表,所以她建议通过玩游戏来销毁它。
玩家轮流进行。萨沙是一位绅士,所以他给了安娜先出手的权利。
- 轮到安娜时,她必须从列表中选择一个元素 $$$a_i$$$ 并反转其数字的顺序。例如,如果 Anna 选择值为 $$$42$$$ 的元素,则它将变为 $$$24$$$;如果 Anna 选择值为 $$$1580$$$ 的元素,则它将变为 $$$851$$$。请注意,前导零已被删除。这样一转之后,列表中的元素数量并没有改变。
- 轮到 Sasha 必须从列表中提取两个元素 $$$a_i$$$ 和 $$$a_j$$$ ($$$i \ne j$$$),以任意顺序连接它们并将结果插入回列表中。例如,如果 Sasha 选择等于 $$$2007$$$ 和 $$$19$$$ 的元素,他将从列表中删除这两个元素并添加整数 $$$200719$$$ 或 $$$192007$$$。这样一转之后,列表中的元素数量减少了$$$1$$$。
玩家不能跳过回合。当莎莎无法移动时,游戏结束,即安娜移动后,列表中只剩下一个数字。如果这个整数不小于 $$$10^m$$$ (即 $$$\ge 10^m$$$),Sasha 获胜。否则,安娜获胜。
可以证明,游戏总会结束。如果两名玩家都发挥最佳,确定谁会获胜。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
然后是测试用例的描述。
每个测试用例的第一行包含整数 $$$n$$$, $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^6$$$) - 列表中整数的数量以及确定 Sasha 何时获胜的参数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - Sasha 给 Anna 的列表。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出:
- “Sasha”,如果 Sasha 以最佳发挥获胜;
- “安娜”,如果安娜以最佳发挥获胜。
示例
输入 #1
9 2 2 14 2 3 5 9 56 1 4 10 1 2007 800 1580 4 5 5000 123 30 4 10 10 6 4 6 2 3 1 10 9 10 7 1 1 6 1 1 10 8 9 1 2 9 10 10 2 10 2 4 5 10 10 10 10
输出 #1
Sasha Anna Anna Sasha Sasha Anna Anna Anna Sasha
注意
考虑第一个测试用例。
Anna可以将整数$$$2$$$反转,然后Sasha可以将整数$$$2$$$和$$$14$$$连接起来,得到整数$$$214$$$,它大于$$$10^2 = 100$$$。如果 Anna 颠倒了整数 $$$14$$$,Sasha 就会将整数 $$$41$$$ 和 $$$2$$$ 连接起来,得到整数 $$$412$$$,它大于 $$$10^2 = 100$$$。安娜没有其他可能的行动,所以她输了。