The term Fibonacci words is used to stipulate a row of words that are constructed in the same manner as the Fibonacci sequence¹:

• the zeroth Fibonacci word is a

• the first Fibonacci word is b

• for $$n > 1$$, the $$n$$th Fibonacci word is built by merging the $$(n-1)$$th and $$(n-2)$$th Fibonacci word

Input

The input consists of a single line containing the number $$n \in \mathbb{N}$$.

Output

The output consists of a single line containing the $$n$$th Fibonacci word.

Example

Input:

1

Output:

b

Example

Input:

5

Output:

babbabab