Count and Say Sequence

The Count and Say Sequence is a sequence of strings defined recursively. The first term is "1". Each subsequent term is generated by describing the previous term in terms of the frequency and value of groups of consecutive digits.

For example, the second term is "11" because the first term "1" is read off as "one 1". The third term is "21" because "11" is read as "two 1s". In general, the nth term is generated by reading the (n-1)th term and recording the counts of consecutive identical digits.

Mathematically, if the sequence is represented by \( a(n) \), then \( a(1) = "1" \) and for \( n > 1 \), \( a(n) \) is the result of describing \( a(n-1) \) formed by concatenating the counts and the corresponding digits.

inputFormat

Input is given on a single line containing one integer \( n \) representing the term of the sequence to generate. For example:

4

This means you need to output the 4th term of the Count and Say sequence.

outputFormat

Output the nth term of the Count and Say sequence as a string. For example, if \( n = 4 \), the output is:

1211

1

1