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 is given from Standard Input in the following format: >$N$ #### Constraints - $1 \leq N \leq 10^{18}$ - All values in input are integers.

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.

***For Sample #1:*** 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`. ***For Sample #2:*** 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$.

AtCoder [ABC216C]