Divisor erasing game 1

Time limit2sMemory limit512 MB

Summary

Players alternate erasing a remaining number from 1 to N with its divisors, the player taking the last number loses, so name the winner under optimal play.

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

Problem

A and B play the divisor erasing game. The natural numbers from 1 to $N$ are written on a blackboard, one of each.

On your turn you pick one number that is still on the board and erase it, and you also erase every divisor of that number that is still on the board. For example, if 2, 3, 4, 5, 6 remain and you pick 6, then 6 is erased together with its divisors 2 and 3. You cannot pass your turn without erasing anything. The player who erases the last number loses.

A moves first and both players play optimally. Find the player who wins.

Input

The first line contains $N$ . $N$ is a natural number not greater than 1,000,000.

Output

Print A on the first line if A wins, and B if B wins.

Hint

When $N = 4$ , A picks 4 on the first turn and erases 4 together with its divisors 2 and 1. Only 3 is left on the board, so B has to erase 3 and loses.

Examples2

Example 1
Input
```
4
```
Expected output
```
A
```
Example 2
Input
```
1
```
Expected output
```
B
```