Đề bài

In ra dãy Fibonacci đến số thứ n.

Yêu cầu

Nhập vào một số nguyên n, sử dụng vòng lặp while để in dãy Fibonacci từ số thứ 1 đến số thứ n.

Input

Một số nguyên dương n (1 ≤ n ≤ 30)

Output

In ra n số đầu tiên của dãy Fibonacci, mỗi số trên một dòng.

Ví dụ

Input

7

Output

1
1
2
3
5
8
13

Input

10

Output

1
1
2
3
5
8
13
21
34
55

Gợi ý

• Dãy Fibonacci bắt đầu với F(1) = 1, F(2) = 1
• Từ số thứ 3 trở đi: F(n) = F(n-1) + F(n-2)
• Sử dụng 3 biến: số thứ nhất, số thứ hai, và số tiếp theo
• Sử dụng vòng lặp while với biến đếm