Alice and Bob are playing a game of picking coins. They are given a large pile of \(N\) coins and an integer \(k\). In the \(i^{th}\) move of any player, \(k^i\) coins are picked from the pile. A player who is not able to make the move during his turn loses. You are required to predict the winner of the game.
Note: In every turn, Alice plays first followed by Bob.
Input format
- First line: \(T\) that represents the total number of test cases
- Each line of the test case: Two space-separated integers \(N\) and \(k\)
Output format
For each test case, you are required to print the name of the winner of the game. You have to print either Alice or Bob depending upon who is the winner of the game.
Constraints
\(1 \le T \le 100\)
\(1 \le N , k \le 10^{18}\)
4 10 3 14 2 18 10 37 5
Bob Bob Alice Alice
Test Case 1
In the first move: Alice first removes 3 coins, then Bob also removes 3 coins.
In the second move: Alice has to remove 9 coins but since only 4 are available, Alice loses and Bob wins.
Test Case 2
In the first move: Alice first removes 2 coins, then Bob also removes 2 coins
In the second move: Alice removes 4 coins, then Bob also removes 4 coins and only 2 coins remain.
In the third move: Alice has to remove 8 coins but it is not possible so Bob wins.
Similarly, the other two test cases can be followed.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor