Some people who love strings have decided to call a special group of strings as the “unique strings.”

Let’s define a(S) as the number of characters “a” the string S contains, and b(S) as the number of characters “b” the string S contains.

S is a unique string if:

1. S only contains the characters “a” and “b”
2. For every substring S’ of S, | a(S’) – b(S’) | <= 3

For example, “abbab” is a unique string. However, “abbbba” is not because it includes the substring “bbbb” for which | a(“bbbb”) – b(“bbbb”) | = 4 > 3.

Let’s say we sort the unique strings – first by length and then lexicographically. The N^th unique string is the string that appears in the position N in the sorted list. The first unique string is assigned the number 1.

The first 12 unique strings in the sorted list are: a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab

Input

A single number N (1 <= N <= 10¹⁴). Your task is to find the N^th unique string in the sorted list.

Output

A single line: the N^th unique string in the sorted list.

Example

Input:
10

Output:
abb

Input:
19

Output:
abab