Description

所谓斐波那契数列是指，第1个数为1，第2个数为1，从第3个数开始，每个数为前两个数之和，比如第3个数为1+1=2，第4个数为1+2=3……现在我有n次询问，每次问fbnq数列中第k项是多少，请你编写程序实现这一功能。

Format

Input

第一行，一个整数N(N<=1000,000),表示询问次数；

第二行，N个整数，表示每次询问的是第几项。

Output

一行一个整数，表示查询的结果。

Samples

1
5

5

Limitation

1s, 1024KiB for each test case.