Dãy số tribonacci được định nghĩa như sau:

• ~a_0=0, a_1=0, a_2=1;~
• ~a_n = a_{n-1} + a_{n-2} + a_{n-3}, n ≥ 3.~

Các phần tử ban đầu của dãy là:

~0~, ~0~, ~1~, ~1~, ~2~, ~4~, ~7~, ~13~, ~24~, ~44~, ~81~, ~149~, ~274~, ~504~, ~927~, ~1705~, ~3136~, ~5768~,~10609~, ~19513~, ~35890~, ~66012~, ~121415~, ~223317~, ~410744~, ~755476~,~1389537~, ~2555757~, ~4700770~, ~8646064~, ...

Yêu cầu:Cho số ~n~, tìm số tribonacci đầu tiên lớn hơn hoặc bằng ~n~.

Input

• Input gồm nhiều test, số lượng test không quá ~100~.
• Mỗi test gồm một dòng chứa số nguyên ~n~ (~0 ≤ n ≤ 109~).

Output

• Với mỗi test, in ra số tribonacci tìm được.

Sample

Input #1

1
2
3
4
5

Output #1

1
2
4
4
7

Problem source: Kc97ble - Free Contest