题目描述

Renako 陷入了两难的境地……当然，我指的是 Ajisai 和 Mai ！她们两个都想和她一起玩，她实在无法决定！于是 Ajisai 和 Mai 决定进行一场异或游戏。

Ajisai 和 Mai 被给予长度为 $n$ 的数组 $a$ 和 $b$。她们将进行一个持续 $n$ 回合的游戏，其中 Ajisai 在奇数回合行动，Mai 在偶数回合行动。在第 $i$ 回合，行动者可以选择交换 $a_i$ 和 $b_i$，或者选择不操作。

请注意，如果发生交换，被交换的索引必须与回合号匹配。例如，在第一回合，Ajisai 可以选择交换 $a_1$和 $b_1$，或者不操作。在第二回合，Mai 可以选择交换 $a_2$ 和 $b_2$，或者不操作。如此进行 $n$ 个回合。因此，只有 Ajisai 可以交换奇数索引的元素，只有 Mai 可以交换偶数索引的元素。

游戏结束时，Ajisai 的得分为 $a_1⊕a_2⊕⋯⊕a_n$，Mai 的得分为 $b_1⊕b_2⊕⋯⊕b_n$。得分更高的玩家获胜。如果双方得分相同，则游戏以平局结束。

请确定在双方都采取最优策略的情况下游戏的结果。更正式地说，如果存在某位玩家的一个策略，使得无论对手如何选择，该玩家总能获胜，则认为该玩家在最优策略下获胜。如果双方都不存在这样的策略，则认为在最优策略下游戏是平局。

$⊕$ 表示按位异或操作。

输入格式

第一行包含一个整数 $t$ — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$。

每个测试用例的第二行包含 $n$ 个整数，$a_1,\ a_2,\ …,\ a_n$。

每个测试用例的第三行包含 $n$ 个整数，$b_1,\ b_2,\ ...,\ b_n$。

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

输出格式

对于每个测试用例，在一行上输出 Ajisai（如果 Ajisai 在最优策略下获胜）、Mai（如果 Mai 在最优策略下获胜）或 Tie（如果游戏在最优策略下以平局结束）。

样例

6
4
1 4 6 1
3 2 3 7
6
20 11 1 7 7 0
14 8 3 6 17 6
4
2 6 3 6
3 4 7 1
5
1 4 5 5 3
6 7 1 2 13
6
9 5 9 17 17 6
1 13 6 13 1 15
5
2 3 8 1 5
3 1 6 14 7

Mai
Ajisai
Tie
Ajisai
Mai
Tie

样例1解释

第一回合，Ajisai 选择交换 $a_1$ 和 $b_1$。此时数组变为 $a=[3,\ 4,\ 6,\ 1]$ 和 $b=[1,\ 2,\ 3,\ 7]$。

第二回合，Mai 选择交换 $a_2$ 和 $b_2$。此时数组变为 $a=[3,\ 2,\ 6,\ 1]$ 和 $b=[1,\ 4,\ 3,\ 7]$。

第三回合，Ajisai 选择不操作。

第四回合，Mai 选择交换 $a_4$ 和 $b_4$。此时数组变为 $a=[3,\ 2,\ 6,\ 7]$ 和 $b=[1,\ 4,\ 3,\ 1]$。

最终，Ajisai 的得分为 $3⊕2⊕6⊕7=0$，Mai 的得分为 $1⊕4⊕3⊕1=7$。因此，Mai 获胜。

请注意，以上描述不一定代表最优策略。

数据范围

对于 $30\%$ 的数据，$0\le a_i,\ b_i\le1$。

对于 $100\%$ 的数据，$1\le t\le 10^4$，$1\le n\le2\times10^5$，$0\le a_i,\ b_i\le10^6$。