D. Double it
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Alex has two magic machines A and B. Machine A will give you 2x + 1 coins if you insert x coins in it, machine B will give you 2x + 2. Alex has no coins and wants to get exactly n coins in order to buy a new unicorn, but he can't figure out how to do it. Your task is to find a way to use the machines to get exactly n coins.

Input

The input consists of a single line containing n (1 ≤ n ≤ 109).

Output

For each one output a string of A's and B's giving the order in which the machines are used.

Examples
Input
7
Output
AAA
Input
10
Output
ABB