#include <stdio.h>

#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)

int func(int a, int x, int d, int sc)
{
  int n = 0; 
  int t = 0;
  while ( sc >= 1 ) {
     n = a / x - a / (d * x);
     t += sc * n;
     sc--;
     x = x / d;
  }
  return t;
}

int main()
{
   //
   int n;
   scanf("%d", &n);
   for ( int i = 0; i < n; i++ ) {
      int a;
      scanf("%d", &a);
      int m1 = func(a, 244140625, 5, 12);
      int m2 = func(a, 536870912, 2, 29);
      printf("%d\n", min(m1, m2));
   }
   return 0;
}