The count-and-say sequence starts with 1. Each following term is produced by reading the previous term as consecutive runs of equal digits and writing, for each run, its length followed by the digit. For example 21 is read as "one 2, one 1" -> 1211.

The first few terms are 1, 11, 21, 1211, 111221.

Given k, output the k-th term (1-indexed).

Input format

One line: an integer k.

Output format

One line: the k-th count-and-say term.

Constraints

• 1 <= k <= 25

4

1211

1

1