Cho dãy số xác định bằng công thức sau :

~ a_0 ~ = 0;~ a_1 ~ = 0;~ a_2 ~ = 1;

~ A_n=A_{n-1}+A_{n-2}+A_{n-3} ~

Viết chương trình in ra số ~ A_x ~ với ~ A_x ~ >= M.

Input

• Gồm nhiều dòng với mỗi dòng là 1 giá trị M khác nhau

Output

• Gồm nhiều dòng, mỗi dòng là giá trị ~ A_x ~ tương ứng của M.

Sample

Input #1

1
2
3
4
5

Output #1

1
2
4
4
7

Problem source: apok