CF1931E.Anna and the Valentine's Day Gift

Sasha gave Anna a list $a$ of $n$ integers for Valentine's Day. Anna doesn't need this list, so she suggests destroying it by playing a game.

Players take turns. Sasha is a gentleman, so he gives Anna the right to make the first move.

• On her turn, Anna must choose an element $a_i$ from the list and reverse the sequence of its digits. For example, if Anna chose the element with a value of $42$, it would become $24$; if Anna chose the element with a value of $1580$, it would become $851$. Note that leading zeros are removed. After such a turn, the number of elements in the list does not change.
• On his turn, Sasha must extract two elements $a_i$ and $a_j$ ($i \ne j$) from the list, concatenate them in any order and insert the result back into the list. For example, if Sasha chose the elements equal to $2007$ and $19$, he would remove these two elements from the list and add the integer $200719$ or $192007$. After such a turn, the number of elements in the list decreases by $1$.

Players can't skip turns. The game ends when Sasha can't make a move, i.e. after Anna's move there is exactly one number left in the list. If this integer is not less than $10^m$ (i.e., $\ge 10^m$), Sasha wins. Otherwise, Anna wins.

It can be shown that the game will always end. Determine who will win if both players play optimally.

萨沙在情人节送给安娜一个包含 $n$ 个整数的列表 $a$。安娜并不需要这个列表，于是她提议通过玩游戏来销毁它。

双方轮流进行操作，萨沙是一位绅士，因此他让安娜先手。

• 在安娜的回合中，她必须从列表中选择一个元素 $a_i$，并将其各位数字反转。例如，若安娜选中值为 $42$ 的元素，则它变为 $24$；若她选中值为 $1580$ 的元素，则它变为 $851$（注意：前导零会被去除）。经过此操作后，列表中元素的总数不变。
• 在萨沙的回合中，他必须从列表中选出两个不同位置的元素 $a_i$ 和 $a_j$（$i \ne j$），以任意顺序将它们拼接（即连接其十进制表示），并将拼接所得的新整数重新插入列表。例如，若萨沙选中值分别为 $2007$ 和 $19$ 的两个元素，则他将这两个元素从列表中移除，并加入整数 $200719$ 或 $192007$。经过此操作后，列表中元素的总数减少 $1$。

双方均不可跳过自己的回合。当萨沙无法进行操作时，游戏结束，即在安娜操作之后列表中恰好只剩下一个数。若该整数不小于 $10^m$（即 $\ge 10^m$），则萨沙获胜；否则安娜获胜。

可以证明，该游戏必定会结束。假设双方均采取最优策略，请判断最终谁将获胜。

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Then follows the description of the test cases.

The first line of each test case contains integers $n$, $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^6$) — the number of integers in the list and the parameter determining when Sasha wins.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the list that Sasha gave to Anna.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, output:

• "Sasha", if Sasha wins with optimal play;
• "Anna", if Anna wins with optimal play.

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

• “Sasha”，如果 Sasha 在双方都采取最优策略时获胜；
• “Anna”，如果 Anna 在双方都采取最优策略时获胜。

Consider the first test case.

Anna can reverse the integer $2$, then Sasha can concatenate the integers $2$ and $14$, obtaining the integer $214$, which is greater than $10^2 = 100$. If Anna had reversed the integer $14$, Sasha would have concatenated the integers $41$ and $2$, obtaining the integer $412$, which is greater than $10^2 = 100$. Anna has no other possible moves, so she loses.

考虑第一个测试用例。

安娜可以将整数 $2$ 反转，然后萨沙可以将整数 $2$ 和 $14$ 拼接，得到整数 $214$，其大于 $10^2 = 100$。如果安娜改为反转整数 $14$，则萨沙将拼接整数 $41$ 和 $2$，得到整数 $412$，其同样大于 $10^2 = 100$。安娜没有其他可行的操作，因此她输掉游戏。