#include <stdio.h>
#include <math.h>
void main()
{
	int i,temp;
	long n,xinxi[12],sum,ferret[12],t;
	xinxi[1]=1,ferret[1]=5;
	for (i=2;i<12;i++)
	{
		xinxi[i]=xinxi[i-1]*5+1;
		ferret[i]=5*ferret[i-1];
	}
	scanf("%ld",&t);
	while (t-->0)
	{
		scanf("%ld",&n);
		if (n==5)
		{
			printf("1\n");
			continue;
		}
		sum=0;
		for (i=11;i>0&&n>5;i--)
		{
			if (ferret[i]>n)
				continue;
			else
			{
				temp=(int)n/ferret[i];
				sum+=temp*xinxi[i];
				n-=temp*ferret[i];
			}
		}
		printf("%ld\n",sum);
	}
}