Số Fibonacci được định nghĩa như sau:

F₁ = 1, F₂ = 1, F₃ = F₁ + F₂  

…

F_n = F_n-2 + F_n-1

Hãy viết chương trình tính số Fibonacci theo yêu cầu sau:

INPUT: Đọc từ tệp FIBO.INP

Dòng thứ i chứa số a[ i ] ( a[ i ] ≤ 1000 ; i_max = 10⁶ )

OUTPUT: Ghi vào tệp FIBO.OUT

Dòng thứ i chứa số F_{a[ i ]} 

GIỚI HẠN

• 25% số test có 5 dòng và a[ i ] ≤ 75
• 25% số test có a[ i ] ≤ 75
• 50% số test không có giới hạn gì thêm

Ví dụ: