D. Четно-нечётная игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время своих новогодних каникул Алиса и Боб играют в следующую игру, используя массив a из n целых чисел:

  • Игроки ходят по очереди, первой ходит Алиса.
  • Каждый ход игрок выбирает любой элемент и удаляет его из массива.
  • Если Алиса выбрала четное число, то она прибавляет его в свой результат. Если же число было нечетным, результат Алисы не меняется.
  • Аналогично, если Боб выбрал нечетное число, то он прибавляет его в свой результат. Если же число было четным, то результат Боба не меняется.

Если в массиве не осталось чисел, то игра заканчивается. Побеждает тот игрок, результат которого больше. Если результаты игроков равны, то объявляется ничья.

Например, если n=4 и a=[5,2,7,3], то игра могла пройти следующим образом (существуют и другие варианты):

  • Первым ходом Алиса выбрала число 2 и получила два очка. Ее результат теперь равен 2. Массив a становится равным [5,7,3].
  • Вторым ходом Боб выбрал число 5 и получил пять очков. Его результат теперь равен 5. Массив a становится равным [7,3].
  • Третьим ходом Алиса выбрала число 7 и не получила очков. Ее результат теперь равен 2. Массив a становится равным [3].
  • Последним ходом Боб выбрал число 3 и получил три очка. Его результат теперь равен 8. Массив a становится пустым.
  • Так как у Боба на конец игры больше очков, он объявлется победителем.

Вам интересно, кто победит если оба игрока будут играть оптимально. Обратите внимание, что в массиве могут быть повторяющиеся числа.

Входные данные

В первой строке находится целое число t (1t104) — количество наборов входных данных. Далее следуют t наборов входных данных.

В первой строке каждого набора содержится целое число n (1n2105) — количество элементов в массиве a.

В следующей строке находится n целых чисел a1,a2,,an (1ai109) — массив a, с помощью которого проводится игра.

Гарантируется, что сумма n по всем наборам входных данных не превосходит 2105.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите:

  • «Alice», если при оптимальной игре выиграет Алиса;
  • «Bob», если при оптимальной игре выиграет Боб;
  • «Tie», если при оптимальной игре будет объявлена ничья.
Пример
Входные данные
4
4
5 2 7 3
3
3 2 1
4
2 2 2 2
2
7 8
Выходные данные
Bob
Tie
Alice
Alice