SP23881 DCEPC14G - God of Nim

Amit is a big fan of Nim Game. Literally! He doesn’t just play the game, he fantasizes it. He follows the simple mantra – Eat, Sleep, Nim. His fantasy is overgrown over time that he has starting thinking of himself as God of Nim. Legend has that if you meet him, more often than not he is imagining a game played between you both and how he beats you with comfort. Frustrated with his never ending Nim fantasy, Mishra decides to give him a taste of his own medicine. Mishra devises a game which looks similar to Nim but is not in reality. Here’s how the game looks: 1. Game is played between 2 players, taking turns alternatively. Both play optimally. 2. There are N plies of coins, each containing exactly Pi coins. 3. There are N integers given. Let’s denote each of them by Ki. 4. In a single turn, a player can choose a pile Pi and can discard “x” coins from the pile Pi where 1

First line contains T, the number of test cases. Each test cases starts with an integer N in first line. Next line consists of N integers, P1 to PN. Next line consists of N integers, K1 to KN. 1

Output exactly one string per test case, “Mishra” if Mishra wins the game or “Amit” if Amit wins the game.

Explanation:For second test case, one possible way of winning for Amit is – Amit and Mishra discard 1 coin alternatively from first pile, starting from Amit. Then Amit picks up 3 from second pile, Mishra picks up 1 from second pile and Amit finishes the game by picking up 3 coins left in the second pile.