A number series 1, 2, 3, 4, 6, 9, 13... is generated using the formula t[n] = t[n - 1] + t[n - 3].

Print the first 100 terms in the series.

Input

None

Output

Print the first 100 terms in the series one per line

Example

Output:
1
2
3
4
6
...
(100 terms)