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;
uint64_t gcd(uint64_t a, uint64_t b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
uint64_t lcm(uint64_t a, uint64_t b) { return (a * b) / gcd(a, b); }
uint64_t modpow(uint64_t x, uint64_t n, uint64_t m) {
  if (n == 0) return 1 % m;
  uint64_t u = modpow(x, n / 2, m);
  u = (u * u) % m;
  if (n % 2 == 1) u = (u * x) % m;
  return u;
}
template <class C>
vector<C> factorize(C n) {
  vector<C> factors;
  for (C i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      factors.push_back(i);
      n /= i;
    }
  }
  if (n > 1) {
    factors.push_back(n);
  }
  return factors;
}
template <class C>
bool is_prime(C n) {
  if (n < 2) return false;
  for (C x = 2; x * x <= n; ++x) {
    if (n % x == 0) return false;
  }
  return true;
}
template <class C>
void line_to_vec_n(C& v, const int32_t count) {
  copy_n(istream_iterator<typename C::value_type>(cin), count,
         back_inserter(v));
}
template <class C>
void print_container(const C& v, const char* delim = " ") {
  copy(v.begin(), v.end(),
       ostream_iterator<typename C::value_type>(cout, delim));
  cout << endl;
}
template <class C>
vector<C> sieve(const C n) {
  vector<C> s(n + 1, 0);
  for (int x = 2; x <= n; x++) {
    if (s[x]) continue;
    for (int u = 2 * x; u <= n; u += x) {
      s[u] = x;
    }
  }
  s[0] = s[1] = 1;
  return s;
}
int main(int argc, char* argv[]) {
  uint64_t n;
  cin >> n;
  for (uint64_t i = 0; i < n; ++i) {
    int64_t qi;
    cin >> qi;
    int64_t q = qi;
    int64_t r = q / 4;
    if (q == r * 4) {
      cout << r << endl;
      continue;
    }
    q = qi - 6;
    r = q / 4;
    if (q >= 0)
      if (q == r * 4) {
        cout << r + 1 << endl;
        continue;
      }
    q = qi - 9;
    r = q / 4;
    if (q >= 0)
      if (q == r * 4) {
        cout << r + 1 << endl;
        continue;
      }
    q = qi - 15;
    r = q / 4;
    if (q >= 0)
      if (q == r * 4) {
        cout << r + 2 << endl;
        continue;
      }
    cout << -1 << endl;
  }
  return 0;
}
