cho.sh

Divisor erasing game 1

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.

Medium7Game theoryNumber theoryNo attempts yetTime limit2sMemory limit512 MB

Problem

A and B play the divisor erasing game. The natural numbers from 1 to NN 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 NN. NN 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=4N = 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.