설명

피보나치 수열은 수열의 첫 번째와 두 번째 수가 모두 1이고, 그 다음 각 수는 앞의 두 수의 합과 같다.양의 정수 a를 주고 피보나치 수열의 a번째 수가 1000 다이얼에 대한 결과가 얼마인지 요구한다.

형식 입력

첫 번째 행은 테스트 데이터의 그룹 수 n이고 그 뒤에 n 행에 따라 입력합니다.각 테스트 데이터는 양의 정수 a (1 ≤ a ≤ 1000000) 를 포함하여 1 행을 차지합니다.

출력 형식

n행, 각 행의 출력에 해당하는 입력.출력은 피보나치 수열의 a 번째 수 대 1000 모델링에 대한 양의 정수여야 합니다.

샘플

4
5
2
19
1

5
1
181
1