Malvika and Animesh play RedBlue cards Game

All submissions for this problem are available.
After 2 hours of Mathematics and chill, Malvika and Animesh got bored of solving problems and decided to play a game. They have n cards with them, each of which is red on one side and blue on the other. They initially put them in a row, from left to right. They then takes turns, with Malvika going first.
In a single turn, the player should choose a card which has its red face up. The player also chooses zero or more consecutive blue faced cards, with the sequence starting immediately on the right of the chosen red card. All the chosen cards are then flipped. That is, the red faced card will now be blue. The zero or more blue faced cards will now be red. Then the turn ends, and it's the other player's turn.
You will be given the initial arrangement of the n cards as a string of R's and B's, which imply red facingup and blue facingup, respectively. They will be given in order, from left to right.
The player who is not able to make any move in his/her turn loses. Find out the winner, assuming that both Malvika and Animesh play optimally.
Input
 The first line of input contains a single integer T denoting the number of test cases.
 The only line of each test case contains a string of 'R's and 'B's.
Output
 For each test case, output a single line. It should be "Malvika" (without quotes) if Malvika is the winner, and "Animesh" (without quotes) if Animesh is the winner.
Constraints
 1 ≤ T ≤ 100
 1 ≤ n ≤ 500, where n refers to the length of each string.
Example
Input: 2 R BB Output: Malvika Animesh
Explanation
In the first example, Malvika will flip the red faced card in the first move, so it will now be blue faced. Now Animesh can't make any move, so he will lose. Hence Malvika is the winner.
In the second example, Malvika can not make any move in the first turn itself, and therefore she loses. Hence Animesh is the winner.
Author:  admin2 
Editorial  http://discuss.codechef.com/problems/CHN07 
Tags  acm15chn, admin2, gametheory 
Date Added:  15012016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 