eolymp
bolt
Try our new interface for solving problems
Problems

Tri Tiling

Tri Tiling

Time limit 1 second
Memory limit 128 MiB

In how many ways can you tile a 3 x n rectangle with 2 x 1 dominoes? Here is a sample tiling of a 3 x 12 rectangle.

prb482

Input data

Consists of several test cases followed by a line containing -1. Each test case is a line containing an integer n (0n30).

Output data

For each test case print one integer giving the number of possible tilings.

Examples

Input example #1
2
8
12
-1
Output example #1
3
153
2131