У нас порожня коробка. Степан може читати наступні два заклинання будь-яку кількість разів у будь-якому порядку.

• Заклинання A: кладе одну нову кульку в коробку.

• Заклинання B: подвоює кількість куль у коробці.

Як отримати в коробці рівно \(N\) кульок здійснивши щонайбільше \(\mathbf{120}\) заклинань.

Можна довести, що такий шлях завжди існує за заданих обмежень. Немає іншого способу, крім заклинань, щоб змінити кількість кульок у коробці.

Формат вхідних даних

Вхідний потік містить ціле число \(N\) (\(1 \le N \le 10^{18}\))

Формат вихідних даних

У вихідний потік виведіть рядок \(S\), що складається з 'A' та 'B'. \(i\)-й символ \(S\) має представляти заклинання для \(i\)-го застосування. \(S\) має містити щонайбільше \(\mathbf{120}\) символів.

Примітка

До прикладу 1:

При цьому кількість кульок змінюється наступним чином: \(0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A}5\) .

Є також інші прийнятні виходи, наприклад AAAAA.

Приклад вхідних даних

5

Приклад вихідних даних

AABA

Приклад вхідних даних

14

Приклад вихідних даних

BBABBAAAB