URI Online Judge | 2041

Gödelito's Sequence

By Daniele Oliveira, Universidade Federal de Uberlândia BR Brazil

Timelimit: 1

Gödelito is fascinated by mathematical and logical issues and spends a lot of time playing in trying to figure out the semantics behind the mathematical sequences. The most fun to Gödelito is not so much to find the next number in the sequence, but understand the axioms which determine the shape of the sequences.
Many sequences are dictated by mathematical rules, for example the Fibonacci sequence whose axiom is that each number is the sum of the previous two. Other sequences involve more semantic axioms, for example the following: 2, 10, 12, 16, 17, 18, 19, 200 ... in which axiom is: numbers whose name starts with the letter D (in portuguese).
Gödelito is currently faced with an interesting sequence. After some time he found that the axiom of the sequence is semantic (he tried first several mathematical accounts, which only made him happier when he discovered the meaning of the sequence). The sequence is shown below:

3
13
1113
3113
132113
1113122113
311311222113
...

Gödelito was impressed with how this sequence grows quickly. And how do not want to spend sheets of his notebook to calculate all the numbers he wants he asked for your help to create an algorithm to find the other numbers in the sequence. But he explained to you the meaning of the sequence to make your life easier:

Each sequence number is generated by reading (describing) the above, for example, the second number is 13 because the top row contains one (1) number three (3). The third number is 1113, because the top line contains one (1) number (1) and one (1) number three (3). The fourth number of the sequence is 3113, because the top row contains three (3) numbers one (1) and one (1) number three (3). I think you get the idea, right?

Input

The input consists of several test cases. Each test case is composed of a line having an integer N, which is the nth number of the sequence to be calculated, with 0 <N <= 40.

Output

The output of each test case is a line containing only the nth number of the sequence.

Input Samples Output Samples

5

2

1

4

132113

13

3

3113