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;
int Abs(int t) {
  if (t < 0) return -t;
  return t;
}
int NOD(int a, int b) {
  while (a > 0 && b > 0)
    if (a > b)
      a %= b;
    else
      b %= a;
  return a + b;
}
bool Check(unsigned a) {
  char* i = new char[4];
  i[0] = a / 1000;
  i[1] = a / 100 % 10;
  i[2] = a / 10 % 10;
  i[3] = a % 10;
  if (i[0] == i[1] || i[0] == i[2] || i[0] == i[3] || i[1] == i[2] ||
      i[1] == i[3] || i[2] == i[3])
    return false;
  else
    return true;
}
bool IsSimple(int now) {
  for (int i = 2; i < now; i++)
    if (now % i == 0) return false;
  return true;
}
class Tog {
 public:
  int first;
  int second;
  int d;
  Tog(int o, int t, int h) {
    first = o;
    second = t;
    d = h;
  }
};
void solve() {
  int n;
  cin >> n;
  int h;
  for (int i = 0; i < n; i++) {
    cin >> h;
    if (h % 4 == 0) {
      cout << h / 4 << "\n";
      continue;
    }
    if (h % 4 == 1 && h >= 9 && (h - 9) % 4 == 0) {
      cout << (h - 9) / 4 + 1 << "\n";
      continue;
    }
    if (h % 4 == 2 && h > 5) {
      cout << (h - 6) / 4 + 1 << "\n";
      continue;
    }
    if (h % 4 == 3 && h > 14 && (h - 15) % 4 == 0) {
      cout << (h - 15) / 4 + 2 << "\n";
      continue;
    }
    cout << -1 << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false);
  solve();
  return 0;
}
