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.

Example 1

Input:
1
3

Output:
3
21