Fibonacci sayı

Fibonacci ədədlərini aşağıdakı kimi təyin edək:

F(1) = F(2) = 1

F(n) = F(n - 1) + F(n - 2) burada n ≥ 3.

n-ci Fibonacci ədədini hesablayın.

Giriş məlumatları

Birinci sətirdə testlərin sayı t (1 ≤ t ≤ 10^3) verilir. Sonrakı t sətirdə hər biri bir ədəd n (1 ≤ n ≤ 10^4) olan bir ədəd var.

Çıxış məlumatları

Hər test üçün müvafiq Fibonacci ədədini ayrı bir sətirdə çıxarın.

Nümunələr