A game of digits P69088


Statement
 

pdf   zip

thehtml

Consider the following game: given two positive integers n and b, players A and B take turns to write digits in base b (from 0 to b−1), starting with player A. The digits are written from left to right. For instance, if A writes a 5, B may write a 1 to form a 51, but not a 15. (And then A would write another digit, and then B, and so on.) If at any point during the game a multiple of n (including 0) is written (in base b), then B wins and the game finishes.

If A can indefinitely prevent B from winning, both players will eventually get bored and player A will be declared the winner. Otherwise, they will keep playing until B wins. Can you determine who will be the winner? Assume that A and B play perfectly.

Input

Input consists of several cases, each with n and b. Assume 1 ≤ n ≤ 1018 and 2 ≤ b ≤ 1018.

Output

For every case, print the name of the winner.

Public test cases
  • Input

    10 5
    5 10
    2 2
    1000000000000000000 123456789012345
    

    Output

    A
    B
    B
    A
    
  • Information
    Author
    Martí Oller
    Language
    English
    Official solutions
    C++
    User solutions
    C++