Bob vs ATM

All submissions for this problem are available.
Due to shortage of ATMs, a bank decided to convert some arcade gaming machines into ATMs. Unfortunately, due to a bug, the converted machine will only dispense cash if the withdrawer can win the game. The game is played over a valid bracket sequence. Formally a valid bracket sequence is defined as:
 An empty string is valid
 If A is a valid bracket sequence, then (A) is also valid
 If A and B are valid, AB is also valid
In each move a player can erase such a nonempty valid substring of the remaining brackets such that they cannot be formed by concatenating 2 valid sequences. E.g. a player can erase (()) or (()()) but not ()() or (())(). The ATM always plays first. The player that is not able to make a move will lose the game. Assume that both the players play optimally.
Bob is trying to withdraw money and is frustrated as he keeps losing against the machine. He suspects the machine is rigged and always wins the game. So, he has asked you to help him out. Given a valid bracket sequence, can you determine who wins the game?
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each of the test case consists of a single line containing the string S  the initial bracket sequence.
Output
For each test case, output a single line containing the winner  either "ATM" or "Bob" without quotes.
Constraints
 1 ≤ T ≤ 10^{5}
 2 ≤ length of S ≤ 10^{5}
 The sum of all lengths of S will be not more than 10^{6}
 S will be a valid bracket sequence
Example
Input: 5 () (()()(())) ()() (())() (()()(()))((())) Output: ATM ATM Bob ATM Bob
Explanation
Example case 1. The ATM will erase the entire sequence and win the game
Example case 2. The ATM will again erase the entire sequence and win the game
Example case 3. The ATM can erase either the first or the second (), Bob will erase the other one and win
Author:  admin3 
Editorial  https://discuss.codechef.com/problems/AMR16J 
Tags  admin3, amr16, icpc2016 
Date Added:  20122016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3 
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. 