FIBONACI

Dãy Fibonaci là dãy vô hạn các số tự nhiên. Số Fibonaci thứ n, ký hiệu F(n), được định nghĩa như sau:

• F(n) = 0, nếu n = 0
• F(n) = 1, nếu n = 1

• F(n) = F(n-1) + F(n-2), nếu n > 1

  Day F: 0 1 1 2 3 5 8 13 21 34 55 89 144

Yêu cầu:

Tính số fibonaci thứ n với n cho trước. VD n = 6  Ket qua: 8

Input

Gồm có nhiều test (tối đa 10 test), mỗi test trên 1 dòng (chứa số nguyên n<=35)

Output

Mỗi dòng ghi kết quả tương ứng

Sample Input

6
8
12

Sample Output

8
21
144

Subtask

Note

Gợi ý: