Đếm số cách lát hình chữ nhật 3*n bằng các domino 2*1.

Input

Dữ liệu vào gồm nhiều testcase kết thúc là số ~-1~. Mỗi testcase là một số nguyên ~n~, ~0 \leq~ ~n \leq~ ~30~.

Output

Với mỗi test case, in ra số nguyên là đáp số trên một dòng.

Sample Input

2
8
12
-1

Sample Output

3
153
2131