CHGROOM  Room Change
Problem Statement
It's the end of the semester and best friends Anne and Marian have finally gotten permission from the hostel supervisor to swap rooms and become room mates. Both of them are extremely happy to hear this, but one problem still remains. Although Anne and Marian definitely want to be room mates, both of them are also very attached to their current rooms and neither of them wants to move out.
After a lot of discussion regarding who should be the one to shift rooms, they decide to settle the matter in the following manner :
Both Anne and Marian write down, independently, 2 positive integers k1 and k2. Then, the value q = ( k1 + k2  1 ) is written down on a piece of a paper. Anne is the first person to make a move. During each move, the current player writes down any integer number that is a nontrivial divisor of the last written number. The first person who can't make a move wins, and the other person is the one who needs to shift into the winner's room.
Given that both players play optimally, output the name of the person who wins the game for a given value of q.
NOTE : A number's divisor is said to be nontrivial if it is different from one and from the divided number itself.
Input
The input contains a single integer q ( 1 <= q <= 10^{13} ).
Output
On a single line output "ANNE" if Anne wins. Else output "MARIAN". Note that the quotes are just for clarity, and that the output is casesensitive.
Example
Input #1:
6
Output #1:
MARIAN
Input #2:
30
Output #2:
ANNE
Input #3:
1
Output #3:
ANNEExplanation :
Input #1 : 6 has exactly 2 nontrivial divisors  { 2, 3 }. But neither of these numbers have any nontrivial divisors. So no matter which one Anne writes down, Marian will win since she cannot make any move
Input #2 : Since 6 is a nontrivial divisor of 30, Anne writes down 6. Now, as can be seen from input #1, no matter what move Marian makes, Anne will win.
Input #3 : Since 1 has no nontrivial divisors, Anne wins.
hide comments
nadstratosfer:
20200205 00:23:35
With 60+ 1integer testfiles, measured runtime mostly covers server instability or interpreter startup lag. My Py2 solution comes at 1.67s total, probably less than half of it being actual computation. Poor setup giving no room for any magic, possible with this concept, to work. 

geeta:
20160708 20:47:20
wrong ans @58!! pls provide some more test cases!! 

akshayvenkat:
20160708 20:06:27
O(sqrt(n)*sqrt(n)) giving TLE :( Last edit: 20160708 20:25:47 

hodobox:
20151212 02:51:45
Good question about game theory :) 

785227:
20140624 18:33:40
Good question formation :)


Satyam Kumar Shivam:
20131216 20:12:04
getting WA in 63rd test case.. any help ??? 

joud zouzou:
20130328 08:41:54
My code is giving WA after running(60) :(


Ehor Nechiporenko:
20130327 20:21:39
Yahoo!! The good one task! 1st one! 

rafiki93:
20130326 12:10:54
can you please see why my code is is giving tle?any suggestion would be helpful 
Added by:  Gowri Sundaram 
Date:  20130128 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 