#include<bits/stdc++.h> using namespace std; int main(){ int n,k,a[100000]; cin>>n; a[0]=1; a[1]=1; for(int i=2;i<100000;i++){ a[i]=a[i-1]+a[i-2]; a[i]%=10000; } for(int i=0;i<n;i++){ cin>>k; cout<<a[k-1]<<endl; } return 0; }

#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; while(n--){ int k; cin >> k; long long a[1000005] = {}; a[1] = 1, a[2] = 1; for(int i = 3; i <= k; i++) { a[i] = (a[i - 1] + a[i - 2]) % 1000; } cout << a[k] << endl; } return 0; }

#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; while(n--){ int k; cin >> k; long long a[1000005] = {}; a[1] = 1, a[2] = 1; for(int i = 3; i <= k; i++) { a[i] = (a[i - 1] + a[i - 2]) % 1000; } cout << a[k] << endl; } return 0; }