URI Online Judge | 1739

Threebonacci Sequence

By Victor Marcilio Peixoto, UNIVASF BR Brazil

Timelimit: 1

A number belongs to Threebonacci sequence if it belongs to Fibonacci (consider 1 as being the first number in this sequence) sequence and satisfy at least one criteria below:

1 – The number representation contains at least one digit 3.

2 – The number is a multiple of 3.

Input

Each test case contains an integer N (1 ≤ N ≤ 60 ). Input ends with EOF.

Output

For each test case print a single line containing the Nth term in Threebonacci sequence.

Input Sample Output Sample

1

3

3

21