大炮打蚊子，用了个矩阵快速幂 WA 了。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using vi = vector <i64>;
using M = vector <vi>;
const int MOD = 1e4;

M multi(M a, M b) {
	int n = a.size(), t = a[0].size(), m = b[0].size();
	M ret(n, vi(m, 0));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < t; k++)
				ret[i][j] = (ret[i][j] % MOD + ((a[i][k] + MOD) % MOD * (b[k][j] + MOD) % MOD + MOD)) % MOD;
	return ret;
}

M fpow(M a, long long k) {
	int n = a.size();
	M ret(n, vi(n, 0));
	for (int i = 0; i < n; i++)
		ret[i][i] = 1;
	for (; k; a = multi(a, a), k >>= 1)
		if (k & 1)
			ret = multi(ret, a);
	return ret;
} 

int main() {
	long long n = 2, k;
	M A(n, vi(n, 0));
	A[0][0] = A[0][1] = A[1][0] = 1;
	int T;
	cin >> T;
	while (T--) {
	    cin >> k;
        if (k <= 2) {
            cout << 1 << '\n';
            continue;
        }
        M ret = fpow(A, k);
	    cout << ret[0][1] << '\n';
    }
	return 0;
}