Euclid's Game

Interview

Time limit1sMemory limit128 MB

Summary

Given two starting numbers, decide who wins the subtraction game Euclid's Game under optimal play, for each pair until the terminating 0 0 line.

Level: Medium6 of 10
Topics: Game theory, Math, Number theory, Recursion
Solved: No attempts yet

Problem

Euclid's Game is a two-player game that begins with two natural numbers. Dong-hyeok and Dong-gyu play it, and Dong-hyeok always moves first.

On each turn, the player to move subtracts a positive multiple of the smaller number from the larger number. The result must be a non-negative integer and must be strictly smaller than the larger number was before the subtraction. The two players keep shrinking the numbers this way, alternating turns. The player who makes the larger number exactly $0$ wins the game.

For example, a game starting from $(25, 7)$ may proceed as follows. (On each line, the two values are the larger and the smaller number at that moment.)

25 7
11 7
4 7
4 3
1 3
1 0

In this case Dong-hyeok wins.

Given the two starting natural numbers, write a program that determines who wins when both players play optimally.

Input

The input consists of several lines. Each line contains the two natural numbers that start a game, and Dong-hyeok always moves first. Both natural numbers are at most $2^{31}-1$ . The last line contains two zeros and must not be processed.

Output

For each game, print A wins if Dong-hyeok wins, or B wins if Dong-gyu wins, one result per line.

Examples2

Example 1
Input
```
34 12
15 24
0 0
```
Expected output
```
A wins
B wins
```
Example 2
Input
```
25 7
0 0
```
Expected output
```
A wins
```