피보나치수열

문제 정의

피보나치 수열은 첫째 항과 둘째 항이 1이고, 셋째 항 부터는 아래의 공식에 따라 만들어지는 수열입니다.

Fn=Fn−1+Fn−2

n
이 주어졌을 때, 피보나치 수열의 n

번째 항을 출력하는 프로그램을 작성하세요.

입력 형식

입력의 첫 줄에 테스트 케이스의 숫자 t가 주어진다.
그 후, t줄에 걸쳐 테스트 케이스마다 n 이 주어진다. n은 30 이하의 자연수이다.

출력 형식

각 테스트 케이스에서 입력 받은 n에 대해 피보나치 수열의 n번째 항을 한 줄에 출력한다.

입력 예시

6
1
2
3
4
5
6

출력 예시

1
1
2
3
5
8

t = int(input())

def fib1(k):
    f = [0] * (k+1)
    if k == 0:
        return 0
    f[0] = 0; f[1] = 1
    for i in range(2, k+1):
        f[i] = f[i-1] + f[i - 2]
    return f

for _ in range(t):
    index = int(input())
    list = fib1(t)
    print(list[index])