An và Bình chơi với nhau rất thân và cùng có chung niềm đam mê với các dãy số, đặc biệt là dãy số Fibonacci. Một lần An viết ra giấy một dãy số nguyên dương ~a_1, a_2, \dots, a_n~ và muốn Bình hãy đưa ra dãy Fibonacci ~F_{a_1}, F_{a_2}, \dots, F_{a_n}~. Trong đó dãy Fibonacci được định nghĩa như sau: ~F_1 = 1, F_2 = 1, F_3 = F_1 + F_2~ ~F_n = F_{n-2} + F_{n-1}~

Yêu cầu: Hãy viết chương trình giúp Bình tính số Fibonacci theo yêu cầu trên.

Input

• Đọc từ tệp tin.
• Dòng thứ ~i~ chứa số ~a_i~ (~a_i \le 1000~; ~i_{max} = 10^6~).

Output

• Ghi vào tệp tin.
• Dòng thứ ~i~ chứa số ~F_{a_i}~.

Sample Input 1

1
2
7
24

Sample Output 1

1
1
13
46368