URI Online Judge | 1538

Alien Sequence

By Mauricio Amaral, UFU BR Brazil

Timelimit: 1

Recently it was discovered a planet called Gliese 581g. He only has three times the mass of Earth, and is the 20 light years away, orbiting a star in the constellation Libra known as Gliese 581, a red dwarf. Astronomers at the University of California and the Carnegie Institution of Washington claim that the planet is the first to present real potential to support life. They said that this discovery was only possible through the analysis of ancient Egyptian scriptures remnants of the Library of Alexandria. Notes with a strange sequence that supposedly indicate the positions of planets with life in the universe were found. Each element is translated into three-dimensional coordinates using a very complex algorithm described in the notes, however the algorithm for calculating the sequence was lost because of the fire burned pages of the library.

The book contains only the first eight values ​​of this sequence, detected in legible pages of the scriptures, and to be able to find other coordinates the University of California released a global challenge for students of mathematics, engineering and computing. Given the first elements of this sequence you must write an algorithm able to calculate any element in the series. The known elements are {B, BA, CB, BAA, BCB, CBA, DAB, BAAA} .

It is believed that it is possible to find any element of the series, whose elements seem to be written in an alien number base.

Input

Each line of input contains an integer N (1 ≤ N ≤ 100000), which describes the position in the sequence of the alien element to be calculated. The input is terminated when N = 0.

Output

For each value read should be printed on the screen the element in the nth position of the alien sequence, always with a line feed.

Sample Input Sample Output

1

2

3

4

5

6

7

8

0

B

BA

CB

BAA

BCB

CBA

DAB

BAAA