Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

• Spell A: puts one new ball into the box.
• Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most $\mathbf{120}$ casts of spells.
It can be proved that there always exists such a way under the Constraints given.
There is no way other than spells to alter the number of balls in the box.

Input

Input is given from Standard Input in the following format:
N

Output

Print a string S consisting of A and B.
The i-th character of S should represent the spell for the i-th cast.
S must have at most $\mathbf{120}$ characters.

Constraints

• $1 \leq N \leq 10^{18}$
• All values in input are integers.

Sample Input 1

5

Sample Output 1

AABA

This changes the number of balls as follows: $0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5$.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

14

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: $0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14$.
It is not required to minimize the length of S.

见题面 Input 部分

见题面 Output 部分