E. Аня и подарок на День святого Валентина
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Саша подарил Ане на День святого Валентина массив $$$a$$$ из $$$n$$$ целых чисел. Ане не нужен этот массив, поэтому она предлагает его уничтожить, сыграв в игру.

Игроки ходят по очереди. Саша джентльмен, поэтому уступает право первого хода Ане.

  • Аня в свой ход должна выбрать элемент $$$a_i$$$ из массива и развернуть последовательность цифр его значения. Например, если Аня выбрала элемент со значением $$$42$$$, он превратится в $$$24$$$; если Аня выбрала элемент со значением $$$1580$$$, он превратится в $$$851$$$. Обратите внимание, что ведущие нули удаляются. После этого хода количество элементов в массиве не изменится.
  • Саша в свой ход должен извлечь два элемента $$$a_i$$$ и $$$a_j$$$ ($$$i \ne 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, \ldots, 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$$$, что больше $$$10^2 = 100$$$. Других возможных ходов у Ани нет, поэтому она проигрывает.