You are given several queries. In the i-th query you are given a single positive integer ni. You are to represent ni as a sum of maximum possible number of composite summands and print this maximum number, or print -1, if there are no such splittings.

An integer greater than 1 is composite, if it is not prime, i.e. if it has positive divisors not equal to 1 and the integer itself.

Input

The first line contains single integer q (1 ≤ q ≤ 105) — the number of queries.

q lines follow. The (i + 1)-th line contains single integer ni (1 ≤ ni ≤ 109) — the i-th query.

Output

For each query print the maximum possible number of summands in a valid splitting to composite summands, or -1, if there are no such splittings.

Examples

Input

1
12


Output

3


Input

2
6
8


Output

1
2


Input

3
1
2
3


Output

-1
-1
-1

Note

12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12, but the first splitting has the maximum possible number of summands.

8 = 4 + 4, 6 can't be split into several composite summands.

1, 2, 3 are less than any composite number, so they do not have valid splittings.
#include <bits/stdc++.h>
using namespace std;
class mstream {
 private:
  int res = 0;
  bool right = 0, sign = 0, space = 0, zero = 0;
  int width = 0, precision = 0, maxwidth = 1e6;
  string interval = "";
  const char* formstr(bool ri, bool si, bool sp, bool ze, bool wi, bool pr,
                      string ty) {
    string f = "%";
    if (ri && right) f += "-";
    if (si && sign) f += "+";
    if (sp && space) f += " ";
    if (ze && zero) f += "0";
    if (wi) f += "*";
    if (pr) f += ".*";
    f += ty;
    f += "%s";
    return f.c_str();
  }

 public:
  operator int() { return res; }
  mstream() {}
  mstream operator()() {
    res = 0;
    return *this;
  }
  mstream setright(bool n = 1) {
    right = n;
    return *this;
  }
  mstream setleft(bool n = 1) {
    right = !n;
    return *this;
  }
  mstream setsign(bool n = 1) {
    sign = n;
    return *this;
  }
  mstream notsign(bool n = 1) {
    sign = !n;
    return *this;
  }
  mstream setspace(bool n = 1) {
    space = n;
    return *this;
  }
  mstream notspace(bool n = 1) {
    space = !n;
    return *this;
  }
  mstream setzero(bool n = 1) {
    zero = n;
    return *this;
  }
  mstream notzero(bool n = 1) {
    zero = !n;
    return *this;
  }
  mstream setwidth(int n = 0) {
    width = n;
    return *this;
  }
  mstream setprecision(int n = 6) {
    precision = n;
    return *this;
  }
  mstream setmaxwidth(int n = 1e6) {
    maxwidth = n;
    return *this;
  }
  mstream setinterval(string n = " ") {
    interval = n;
    return *this;
  }
  mstream notinterval(string n = "") {
    interval = n;
    return *this;
  }
  mstream operator>>(int& x) {
    int r = scanf("%d", &x);
    if (r != EOF) res += r;
    return *this;
  }
  mstream operator>>(long long& x) {
    int r = scanf("%I64d", &x);
    if (r != EOF) res += r;
    return *this;
  }
  mstream operator>>(float& x) {
    int r = scanf("%f", &x);
    if (r != EOF) res += r;
    return *this;
  }
  mstream operator>>(double& x) {
    int r = scanf("%lf", &x);
    if (r != EOF) res += r;
    return *this;
  }
  mstream operator>>(char& x) {
    int r = scanf("%c", &x);
    if (r != EOF) res += r;
    return *this;
  }
  mstream operator>>(string& x) {
    char s[maxwidth + 1];
    int r = scanf("%s", s);
    if (r != EOF) x = s, res += r;
    return *this;
  }
  mstream operator<<(int x) {
    int r = printf(formstr(1, 1, 1, 1, 1, 0, "d"), width, x, interval.c_str());
    if (r > 0) res += r;
    return *this;
  }
  mstream operator<<(long long x) {
    int r =
        printf(formstr(1, 1, 1, 1, 1, 0, "I64d"), width, x, interval.c_str());
    if (r > 0) res += r;
    return *this;
  }
  mstream operator<<(float x) {
    int r = printf(formstr(1, 1, 1, 1, 1, 1, "f"), width, precision, x,
                   interval.c_str());
    if (r > 0) res += r;
    return *this;
  }
  mstream operator<<(double x) {
    int r = printf(formstr(1, 1, 1, 1, 1, 1, "lf"), width, precision, x,
                   interval.c_str());
    if (r > 0) res += r;
    return *this;
  }
  mstream operator<<(char x) {
    int r = printf(formstr(1, 0, 0, 1, 1, 0, "c"), width, x, interval.c_str());
    if (r > 0) res += r;
    return *this;
  }
  mstream operator<<(string x) {
    int r = printf(formstr(1, 0, 0, 1, 1, 1, "s"), width, maxwidth, x.c_str(),
                   interval.c_str());
    if (r > 0) res += r;
    return *this;
  }
};
mstream mstr = mstream();
int main() {
  int q;
  mstr >> q;
  for (long long i = 0, i_TO = q; i < i_TO; i++) {
    int n;
    mstr >> n;
    int d = n / 4, m = n % 4;
    if (m == 0)
      mstr << d << '\n';
    else if (m == 1) {
      if (d >= 2)
        mstr << d - 1 << '\n';
      else
        mstr << -1 << '\n';
    } else if (m == 2) {
      if (d >= 1)
        mstr << d << '\n';
      else
        mstr << -1 << '\n';
    } else {
      if (d >= 3)
        mstr << d - 1 << '\n';
      else
        mstr << -1 << '\n';
    }
  }
}
