$\ \ \ \ \ \ \$注意到斐波那契数列，本题完成一半。

$\ \ \ \ \ \ \$注意到$\text{Fibonacci}[44]=701408733<10^9,\text{Fibonacci}[45]=1134903170>10^9$，本题结束。

#include <cstdio>
#define ll long long int

const int MAXN = 44;

ll fibo[MAXN];

int fillFibo(){
    fibo[1] = 1;
    fibo[2] = 1;
    for(int i = 3; i <= MAXN; i++){
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }
    return 0;
}

int main(){
    ll t, n;
    fillFibo();
    scanf("%lld", &t);
    for(ll i = 1; i <= t; i++){
        scanf("%lld", &n);
        if(n > 44){
            printf("shenmegouba\n");
            continue;
        }
        printf("%lld\n", fibo[n]);
    }
    return 0;
}