https://www.acmicpc.net/problem/13075
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;
using matrix = vector<vector<int>>;
const int mod = 1e9;
matrix operator * (const matrix &a, const matrix &b) {
int size = a.size();
matrix res(size, vector<int>(size));
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
for (int k = 0; k < size; k++) {
res[i][j] += a[i][k] * b[k][j];
}
res[i][j] %= mod;
}
}
return res;
}
matrix power(matrix a, int n) {
int size = a.size();
matrix res(size, vector<int>(size));
for (int i = 0; i < size; i++) { // 단위 행렬
res[i][i] = 1;
}
while (n > 0) {
if (n % 2 == 1) {
res = res * a;
}
n /= 2;
a = a * a;
}
return res;
}
int32_t main() {
fastio;
int tc; cin >> tc;
while(tc--){
matrix baseFibo = {{1,1},{1,0}};
int n; cin >> n;
auto ans = power(baseFibo, n);
cout << ans[0][1] << "\n";
}
}