Count and Say Sequence

Given a positive integer \( n \), compute the \( n \)th term of the count and say sequence. The sequence is defined as follows:

For \( n = 1 \), the term is "1". For \( n \ge 2 \), the \( n \)th term is obtained by reading the previous term and stating the counts of consecutive identical digits.

More formally, if the \( i \)th term is denoted by \( a_i \), then \( a_{i+1} = say(a_i) \) where the function say converts a string into a new string by concatenating the count and the digit for each group of identical digits.

For example:

• \( a_1 = "1" \)
• \( a_2 = "11" \) (one 1)
• \( a_3 = "21" \) (two 1s)
• \( a_4 = "1211" \) (one 2 followed by one 1)
• \( a_5 = "111221" \) (one 1, one 2, and two 1s)

You can assume that \( 1 \leq n \leq 30 \).

inputFormat

The input consists of a single integer \( n \) provided via standard input (stdin). This integer represents the index of the term in the count and say sequence that you need to compute.

outputFormat

Output the \( n \)th term of the count and say sequence to standard output (stdout).

1

1