递推斐波那契

这个思路就比较简单了~

/*int fibo(int a){
	int q1,q2;
	if(a == 1 || a == 2){
		return 1;
	}
	else{
		q1 = fibo(a - 1);
		q2 = fibo(a - 2);
		return q1 + q2;
	}
}
int main(){
	int n,a;
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++){
		scanf("%d",&a);
		printf("%ld\n",fibo(a) % 1000);
	}
	return 0;
}*/
//上面On超时！！！递归不行事。。。

long long fi = 1,fb = 1;
long long fn;
int h,a[1000005],n;
int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++){
		scanf("%d",&a[i]);
	}
	for(int i = 1;i <= n;i ++){
		h = a[i];
		if(h == 1 || h == 2){
			printf("%lld\n",fi);
		}
		else{
			for(int j = 3;j <= h;j ++){
				fn = fb + fi;
				fi = fb % 1000;//取模取模取模！！！！
				fb = fn % 1000;
			}
		printf("%lld\n",fn % 1000);
		fn = 0;
		fi = 1;
		fb = 1;
		}
	}
	return 0;
}