Consider some positive integer x. Its prime factorization will be of form x = 2^{k_1} ⋅ 3^{k_2} ⋅ 5^{k_3} ⋅ ...

Let's call x elegant if the greatest common divisor of the sequence k_1, k_2, ... is equal to 1. For example, numbers 5 = 5^1, 12 = 2^2 ⋅ 3, 72 = 2^3 ⋅ 3^2 are elegant and numbers 8 = 2^3 (GCD = 3), 2500 = 2^2 ⋅ 5^4 (GCD = 2) are not.

Count the number of elegant integers from 2 to n.

Each testcase contains several values of n, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer T (1 ≤ T ≤ 10^5) — the number of values of n in the testcase.

Each of the next T lines contains a single integer n_i (2 ≤ n_i ≤ 10^{18}).

Output

Print T lines — the i-th line should contain the number of elegant numbers from 2 to n_i.

Example

Input

4
4
2
72
10


Output

2
1
61
6

Note

Here is the list of non-elegant numbers up to 10:

  * 4 = 2^2, GCD = 2; 
  * 8 = 2^3, GCD = 3; 
  * 9 = 3^2, GCD = 2. 



The rest have GCD = 1.
#include <bits/stdc++.h>
using namespace std;
namespace zdw {
void readint(int &x) {
  char s = getchar(), c = 0;
  while (~s && s < '0' || s > '9') c = s, s = getchar();
  x = s - '0';
  while (~(s = getchar()) && s >= '0' && s <= '9')
    x = (x << 3) + (x << 1) + s - '0';
  if (c == '-') x = -x;
}
void readll(long long &x) {
  char s = getchar(), c = 0;
  while (~s && s < '0' || s > '9') c = s, s = getchar();
  x = s - '0';
  while (~(s = getchar()) && s >= '0' && s <= '9')
    x = (x << 3) + (x << 1) + s - '0';
  if (c == '-') x = -x;
}
void _readint(char *&s, int &x) {
  char w = *s, c;
  while (w && w < '0' || w > '9') w = *++s;
  if (!w) {
    x = -1;
    return;
  }
  c = *(s - 1);
  x = w - '0';
  while ((w = *++s) && w >= '0' && w <= '9') x = (x << 3) + (x << 1) + w - '0';
  if (c == '-') x = -x;
}
void _readll(char *&s, long long &x) {
  char w = *s, c;
  while (w && w < '0' || w > '9') w = *++s;
  if (!w) {
    x = -1;
    return;
  }
  c = *(s - 1);
  x = w - '0';
  while ((w = *++s) && w >= '0' && w <= '9') x = (x << 3) + (x << 1) + w - '0';
  if (c == '-') x = -x;
}
char __num_table[500001];
void init_num_table() {
  for (int i = 0; i < 100000; ++i) {
    char *t = __num_table + i * 5;
    t[0] = i / 10000 + '0';
    t[1] = (i / 1000) % 10 + '0';
    t[2] = (i / 100) % 10 + '0';
    t[3] = (i / 10) % 10 + '0';
    t[4] = i % 10 + '0';
  }
}
void putint(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x <= 9) {
    putchar(x + '0');
    return;
  }
  char w[11], *p = w, *t;
  *p = 0;
  int z;
  while (x > 9999) {
    z = x / 100000;
    t = __num_table + (x - z * 100000) * 5;
    p[1] = t[4];
    p[2] = t[3];
    p[3] = t[2];
    p[4] = t[1];
    p[5] = t[0];
    x = z;
    p += 5;
  }
  t = __num_table + x * 5;
  t[1] > '0'     ? p[1] = t[4], p[2] = t[3], p[3] = t[2], p[4] = t[1], p += 4,
               0 : t[2] > '0' ? p[1] = t[4], p[2] = t[3], p[3] = t[2], p += 3,
               0 : t[3] > '0' ? p[1] = t[4], p[2] = t[3], p += 2,
               0 : t[4] > '0' ? *++p = t[4], 0 : 0;
  while (*p) putchar(*p--);
}
void putll(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x <= 9) {
    putchar(x + '0');
    return;
  }
  char w[20], *p = w, *t;
  *p = 0;
  long long z;
  while (x > 9999) {
    z = x / 100000;
    t = __num_table + (x - z * 100000) * 5;
    p[1] = t[4];
    p[2] = t[3];
    p[3] = t[2];
    p[4] = t[1];
    p[5] = t[0];
    x = z;
    p += 5;
  }
  t = __num_table + x * 5;
  t[1] > '0'     ? p[1] = t[4], p[2] = t[3], p[3] = t[2], p[4] = t[1], p += 4,
               0 : t[2] > '0' ? p[1] = t[4], p[2] = t[3], p[3] = t[2], p += 3,
               0 : t[3] > '0' ? p[1] = t[4], p[2] = t[3], p += 2,
               0 : t[4] > '0' ? *++p = t[4], 0 : 0;
  while (*p) putchar(*p--);
}
void _putint(char *&s, int x) {
  if (x < 0) *s++ = '-', x = -x;
  if (x <= 9) {
    *s++ = x + '0';
    return;
  }
  char w[11], *p = w, *t;
  *p = 0;
  int z;
  while (x > 9999) {
    z = x / 100000;
    t = __num_table + (x - z * 100000) * 5;
    p[1] = t[4];
    p[2] = t[3];
    p[3] = t[2];
    p[4] = t[1];
    p[5] = t[0];
    x = z;
    p += 5;
  }
  t = __num_table + x * 5;
  t[1] > '0'     ? p[1] = t[4], p[2] = t[3], p[3] = t[2], p[4] = t[1], p += 4,
               0 : t[2] > '0' ? p[1] = t[4], p[2] = t[3], p[3] = t[2], p += 3,
               0 : t[3] > '0' ? p[1] = t[4], p[2] = t[3], p += 2,
               0 : t[4] > '0' ? *++p = t[4], 0 : 0;
  while (*s++ = *p--)
    ;
  --s;
}
void _putll(char *&s, long long x) {
  if (x < 0) *s++ = '-', x = -x;
  if (x <= 9) {
    *s++ = x + '0';
    return;
  }
  char w[20], *p = w, *t;
  *p = 0;
  long long z;
  while (x > 9999) {
    z = x / 100000;
    t = __num_table + (x - z * 100000) * 5;
    p[1] = t[4];
    p[2] = t[3];
    p[3] = t[2];
    p[4] = t[1];
    p[5] = t[0];
    x = z;
    p += 5;
  }
  t = __num_table + x * 5;
  t[1] > '0'     ? p[1] = t[4], p[2] = t[3], p[3] = t[2], p[4] = t[1], p += 4,
               0 : t[2] > '0' ? p[1] = t[4], p[2] = t[3], p[3] = t[2], p += 3,
               0 : t[3] > '0' ? p[1] = t[4], p[2] = t[3], p += 2,
               0 : t[4] > '0' ? *++p = t[4], 0 : 0;
  while (*s++ = *p--)
    ;
  --s;
}
class FastInput {
 public:
  static const int MXL = 83886080;
  char *buf, *tt;
  int sz;
  FastInput(int SZ = MXL) {
    buf = (char *)malloc((sz = SZ) + 1);
    tt = buf + 1;
    *buf = *tt = 0;
  }
  ~FastInput() { free(buf); }
  void file_init(FILE *F) {
    buf[fread(buf + 1, 1, sz, F)] = 0;
    tt = buf + 1;
  }
  void readint(int &x) { _readint(tt, x); }
  void readll(long long &x) { _readll(tt, x); }
  char getchar() { return *tt ? *tt++ : -1; }
  void getchar(char &c) { c = (*tt ? *tt++ : -1); }
  void getstr(char *s) {
    char w;
    while ((w = *tt) && w == '\r' || w == '\n' || w == ' ') ++tt;
    while ((w = *tt) && w != '\r' && w != '\n' && w != ' ') *s++ = w, ++tt;
    *s = 0;
  }
  void getline(char *s) {
    char w;
    while ((w = *tt) && w != '\r' && w != '\n') *s++ = w, ++tt;
    tt += *tt == '\r' ? 1 : 0;
    tt += *tt == '\n' ? 1 : 0;
    *s = 0;
  }
};
class FastOutput {
 public:
  static const int MXL = 83886080;
  char *buf, *tt;
  int sz;
  FastOutput(int SZ = MXL) {
    buf = (char *)malloc(sz = SZ);
    tt = buf;
  }
  ~FastOutput() { free(buf); }
  void flush(FILE *F) {
    if (tt == buf) return;
    fwrite(buf, 1, tt - buf, F);
    tt = buf;
  }
  void putint(const int &x) { _putint(tt, x); }
  void putll(const long long &x) { _putll(tt, x); }
  void putchar(const char &c) { *tt++ = c; }
  void putstr(char *s) {
    while (*tt++ = *s++)
      ;
    --tt;
  }
};
}  // namespace zdw
zdw::FastInput FIN;
zdw::FastOutput FOUT;
const long long N = 1e18;
std::map<long long, long long> M;
std::map<long long, long long>::iterator it;
long long x, ans;
int q;
int main() {
  zdw::init_num_table();
  FIN.file_init(stdin);
  M[N + 7] = 1;
  for (long long i = 2, j; (j = i * i * i) <= N; ++i)
    while (!M[j]) {
      M[j] = 1;
      if (N / i < j) break;
      j *= i;
    }
  for (it = M.begin(), q = 0; it != M.end();) {
    long long t = sqrt((long double)it->first);
    if (t * t == it->first)
      M.erase(it++);
    else
      q = (it++->second += q);
  }
  FIN.readint(q);
  while (q--) {
    FIN.readll(x);
    ans = sqrt((long double)x);
    ans += M.upper_bound(x)->second;
    FOUT.putll(x + 1 - ans);
    FOUT.putchar('\n');
  }
  FOUT.flush(stdout);
  return 0;
}
