Multiplication Game

Time limit5sMemory limit512 MB

Summary

Given N, players alternate multiplying a running product by a prime factor of N; making it equal N wins, overshooting ties.

Level: Medium7 of 10
Topics: Game theory, Number theory, Math, Brute force
Solved: No attempts yet

Problem

Alice and Bob are working through multiplication and division drills in class. They get bored fast, so they invent a game instead.

The game starts with a target integer $N$ ( $N \ge 2$ ) and an integer $M = 1$ . Alice and Bob take alternate turns. On a turn the player picks a prime divisor $p$ of $N$ and multiplies $M$ by $p$ . If the move makes $M$ equal to the target $N$ , the player who made it wins. If the move makes $M$ greater than $N$ , the game ends in a tie right there.

Both players play optimally. Work out who wins, if anyone.

Input

The first line contains $T$ ( $1 \le T \le 10000$ ), the number of cases. Each of the next $T$ lines holds one case: the target integer $N$ ( $2 \le N \le 2^{31} - 1$ ) followed by the name of the player taking the first turn, separated by a space. The name is either Alice or Bob.

Output

For each case print the name of the winner under optimal play, Alice or Bob, on its own line. Print tie if neither player wins.

Examples1

Example 1

Input

10
10 Alice
20 Bob
30 Alice
40 Bob
50 Alice
60 Bob
70 Alice
80 Bob
90 Alice
100 Bob

Expected output

Bob
Bob
tie
tie
Alice
tie
tie
tie
tie
Alice