斐波那契数列进阶
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
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.