#include <algorithm>
#include <iostream>
using namespace std;

const int special[] = {1, 64, 729, 4096, 15625, 46656, 117649, 262144, 531441, 1000000, 1771561, 2985984, 4826809, 7529536, 11390625, 16777216, 24137569, 34012224, 47045881, 64000000, 85766121, 113379904, 148035889, 191102976, 244140625, 308915776, 387420489, 481890304, 594823321, 729000000, 887503681};

int main() {
   int m, n;
   scanf("%d", &m);
   while (m--) {
      scanf("%d", &n);
      printf("%d\n", count_if(special, special + 31, [n](int val) { return val <= n; }));
   }
   return 0;
}