E. 安娜与情人节礼物

每次测试的时间限制：2 秒
每次测试的内存限制：256 兆字节

萨沙送给安娜一个包含 $n$ 个整数的列表 $a$ 作为情人节礼物。安娜并不需要这个列表，因此她提议通过一个游戏来销毁它。

玩家轮流进行。萨沙很有绅士风度，所以他让安娜先手。

• 在安娜的回合，她必须从列表中选择一个元素 $a_i$，并将其数字顺序反转。
  例如：如果安娜选择了值为 $42$ 的元素，它会变成 $24$；如果选择了值为 $1580$ 的元素，它会变成 $851$。
  注意：反转后，前导零会被去掉。经过这样的操作，列表中的元素个数不变。
• 在萨沙的回合，他必须从列表中取出两个元素 $a_i$ 和 $a_j$（$i \neq j$），以任意顺序将它们拼接，并将结果插回列表中。
  例如：如果萨沙选择了 $2007$ 和 $19$，他会移除这两个元素，然后加入整数 $200719$ 或 $192007$。
  经过这样的操作，列表中的元素个数减少 $1$。

玩家不能跳过回合。
游戏在萨沙无法行动时结束，也就是说，在安娜的回合结束后，列表中只剩下一个数字。
如果这个整数不小于 $10^m$（即 $\ge 10^m$），萨沙获胜；否则安娜获胜。

可以证明游戏总会结束。
如果双方都采取最优策略，请判断谁会获胜。

输入格式

第一行包含一个整数 $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$）—— 列表中的整数个数以及决定萨沙获胜条件的参数。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 萨沙给安娜的列表。

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

输出格式

对于每个测试用例，输出：

• 如果萨沙在最优玩法下获胜，输出 "Sasha"；
• 如果安娜在最优玩法下获胜，输出 "Anna"。

示例

输入：

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

输出：

Sasha
Anna
Anna
Sasha
Sasha
Anna
Anna
Anna
Sasha

示例解释

考虑第一个测试用例：

安娜可以反转整数 $2$，然后萨沙将 $2$ 和 $14$ 拼接，得到 $214$，大于 $10^2 = 100$。
如果安娜反转了 $14$，萨沙会将 $41$ 和 $2$ 拼接，得到 $412$，同样大于 $100$。
安娜没有其他可能的操作，所以她输了。