168. Count and Say

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

- countAndSay(1) = '1'
- countAndSay(n) = run-length encoding of countAndSay(n-1)

Run-length encoding (RLE) of a string: count consecutive groups of characters and say the count followed by the character.

Given a positive integer n, return the nth element of the count-and-say sequence.

Input: A single integer n.

Output: A string — the nth element of the count-and-say sequence.

Examples

Example 1

Input: 1
Output: 1
Explanation: Base case.

Example 2

Input: 4
Output: 1211
Explanation: 1→11→21→1211.

Example 3

Input: 6
Output: 312211
Explanation: 1→11→21→1211→111221→312211.