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

• countAndSay(1) = "1"
• countAndSay(n) is the run-length encoding of countAndSay(n - 1)

To generate the next term, read off the digits of the previous term and say how many times each digit is repeated.

Example:

countAndSay(1) = "1"
countAndSay(2) = "11"       (one 1)
countAndSay(3) = "21"       (two 1s)
countAndSay(4) = "1211"     (one 2, one 1)
countAndSay(5) = "111221"   (one 1, one 2, two 1s)

Example 1:

Input: 1
Output: 1

Example 2:

Input: 4
Output: 1211

Constraints:

• 1 ≤ n ≤ 30

Input format: A single integer n.

Output format: The nth term of the count-and-say sequence.