Informatics 1

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

De term Fibonacciwoorden wordt gebruikt voor een rij van woorden die op eenzelfde manier opgebouwd wordt als de getallenrij van Fibonacci:

• het nulde Fibonacciwoord is a
• het eerste Fibonacciwoord is b
• voor $n > 1$ wordt het $n$-de Fibonacciwoord opgebouwd door het $(n-1)$-de en $(n-2)$-de Fibonacciwoord samen te nemen

Invoer

De invoer bestaat uit één regel die een getal $n \in \mathbb{N}$ bevat.

Uitvoer

De uitvoer bestaat uit één regel die het $n$-de Fibonacciwoord bevat.

Voorbeeld

Invoer:

1

Uitvoer:

b

Voorbeeld

Invoer:

5

Uitvoer:

babbabab