|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||18||9||9||50.000%|
Alice and Bob are in their class doing drills on multiplication and division. They quickly get bored and instead decide to play a game they invented.
The game starts with a target integer N ≥ 2, and an integer M = 1. Alice and Bob take alternate turns. At each turn, the player chooses a prime divisor p of N, and multiply M by p. If the player’s move makes the value of M equal to the target N, the player wins. If M > N, the game is a tie.
Assuming that both players play optimally, who (if any) is going to win?
The first line of input contains T (1 ≤ T ≤ 10000), the number of cases to follow. Each of the next T lines describe a case. Each case is specified by N (2 ≤ N ≤ 231 − 1) followed by the name of the player making the first turn. The name is either Alice or Bob.
For each case, print the name of the winner (Alice or Bob) assuming optimal play, or tie if there is no winner.
10 10 Alice 20 Bob 30 Alice 40 Bob 50 Alice 60 Bob 70 Alice 80 Bob 90 Alice 100 Bob
Bob Bob tie tie Alice tie tie tie tie Alice