OpenKattis
Increasing CP5 Lower Bound (Day 3)

#### Start

2020-12-08 18:00 AKST

## Increasing CP5 Lower Bound (Day 3)

#### End

2020-12-08 23:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -408 days 4:46:10

5:00:00

0:00:00

# Problem EMultiplication Game

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 \geq 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?

## Input

The first line of input contains $T$ ($1 \leq T \leq 10\, 000$), the number of cases to follow. Each of the next $T$ lines describe a case. Each case is specified by $N$ ($2 \leq N \leq 2^{31}-1$) followed by the name of the player making the first turn. The name is either Alice or Bob.

## Output

For each case, print the name of the winner (Alice or Bob) assuming optimal play, or tie if there is no winner.

Sample Input 1 Sample Output 1
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