题目背景

斐波那契数列的第 $1$、第 $2$ 项都是 $1$，从第 $3$ 项开始，每项的值是前面两项的和。

小鱼想快速知道著名的斐波那契数列的某些项的值，你编写一个程序来帮助她吧。

题目描述

给定一系列的整数，表示要计算的斐波那契数列的项数，输出这些项数对应的斐波那契数列的值。

输入格式

第 $1$ 行是一个正整数 $N$，表示要计算的项数的数量；然后有 $N$ 行数据，每行是一个正整数 $n$ ，表示要计算斐波那契数列第 $n$ 项的值。

输出格式

$N$ 行，每行是与输入对应的斐波那契数列指定项的值。

输入输出样例

10
1
2
3
4
5
6
7
8
9
10

1
1
2
3
5
8
13
21
34
55

3
10
5
1

55
5
1

说明/提示

👀️ 对于$100\%$的数据，$1 \leq N \leq 10^5,1 \leq n \leq 90$。