Lemon Game

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

Alice and Bob are playing a game. There are two piles of lemons, one pile consisting of N lemons and the other pile consisting of M lemons (M \le N). The two players perform the following operation alternately, starting from Alice:

  • Take x lemons from the pile with more lemons, and x must be a positive multiple of the smaller pile.
  • If any pile is empty, the current player cannot perform any operation and then (s)he is the loser, while the other player is the winner.

If both players play optimally, can you write a program to determine if Alice or Bob will win the game? Your program needs to determine the winner for Q rounds.

Input Specification

The first line contains one integer, Q (1 \le Q \le 10), the number of games.

Each of the next Q lines contains two space-separated integers N and M (0 \le M \le N < 2^{31}).

Output Specification

For each query, if Alice wins, print Alice Win; otherwise, print Bob Win.

Sample Input

4
2 1
5 4
37 15
82 76

Sample Output

Alice Win
Bob Win
Alice Win
Bob Win

Explanation

For the 1st game, Alice can take 2 lemons from the first pile, and Bob will lose the game.

For the 2nd game, Alice must take 4 lemons from the first pile. The two piles will have [1, 4] lemons. Bob can take 4 lemons from the 2nd pile and win the game.


Comments

There are no comments at the moment.