Sequences without Stammers

Memory limit: 32 MB

We consider sequences of letters. We say a sequence contains a stammer, if we can find in it two occurrences of the same subsequence, one directly following the other, i.e. if for some and () we have .

We are interested in -element sequences having no stammers, built of the minimal number of different letters.

Example

For it is enough to use two letters, say and . We have exactly two -element sequences without stammers build of those letters: and . For we need three different letters. For example is a three-letter sequence without stammers. In the sequence we have two stammers: and .

Task

Write a program which:

• reads the length of the sequence ,
• computes an -element sequence with no stammers built of the minimal number of different letters,
• writes the result.

Input

In the first line of the standard input there is one positive integer , .

Output

Your program should write to the standard output. In the first line there should be one positive integer equal to the minimal number of different letters that must appear in an -element sequence having no stammers.

In the second line one should write the computed sequence without stammers as a word that comprises lower case letters of English alphabet and is built only of the letters from up to the -th letter of the alphabet. If there are many such sequences, your program should write one of them.

Example

For the input data:

5

the correct result is:

3
abcab

Task author: Krzysztof Sikora.