#include<stdio.h>
long a[100000];
main()
{
	long t;
	long i,j,k;
	long n;
	long a1=1;
	long max=2;
	a[0]=1;
	a[1]=1;
	a[2]=2;
	for(i=3;i<75000;i++)
	{
		a1=(a1+a[i-1])%100000;
		max=(max+a1)%100000;
		a[i]=max;
	}
	scanf("%ld",&t);
	while(t--)
	{
		scanf("%ld",&n);
		k=n%75000;
		printf("%ld\n",a[k]);
	}
	return 0;
}