#include <bits/stdc++.h>
using namespace std;
template <typename T, typename S>
inline bool REMIN(T& a, const S& b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
inline bool REMAX(T& a, const S& b) {
  return a < b ? a = b, 1 : 0;
}
int bit(long long x, int pos) { return (x >> pos) & 1; }
long long power(long long base, long long exp, long long c = 1e9 + 7) {
  if (!exp) return 1;
  long long r = power(base, exp >> 1, c);
  r = (r * r) % c;
  if (exp & 1) r = (r * base) % c;
  return r;
}
long long T, N, M, K;
int a, b, c;
string s1, s2;
const long double PI = 2 * acos(0);
const long long INF = 1e9 + 4;
const long long MOD = 1000000007;
const int NMAX = 3e5 + 5;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> T;
  while (T--) {
    cin >> a;
    if (a < 4) {
      cout << -1;
    } else {
      int ma = 1e9;
      for (int(i) = int(0); (i) <= int(1); ++(i)) {
        for (int(j) = int(0); (j) <= int(1); ++(j)) {
          b = a, c = 0;
          if (i) b -= 6, c++;
          if (j) b -= 9, c++;
          if (b >= 0 and b % 4 == 0) {
            c += b / 4;
            REMIN(ma, c);
          }
        }
      }
      if (ma == 1e9)
        cout << -1;
      else
        cout << ma;
    }
    cout << '\n';
  }
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename S>
inline bool REMIN(T& a, const S& b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
inline bool REMAX(T& a, const S& b) {
  return a < b ? a = b, 1 : 0;
}
int bit(long long x, int pos) { return (x >> pos) & 1; }
long long power(long long base, long long exp, long long c = 1e9 + 7) {
  if (!exp) return 1;
  long long r = power(base, exp >> 1, c);
  r = (r * r) % c;
  if (exp & 1) r = (r * base) % c;
  return r;
}
long long T, N, M, K;
int a, b, c;
string s1, s2;
const long double PI = 2 * acos(0);
const long long INF = 1e9 + 4;
const long long MOD = 1000000007;
const int NMAX = 3e5 + 5;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> T;
  while (T--) {
    cin >> a;
    if (a < 4) {
      cout << -1;
    } else {
      int ma = 1e9;
      for (int(i) = int(0); (i) <= int(1); ++(i)) {
        for (int(j) = int(0); (j) <= int(1); ++(j)) {
          b = a, c = 0;
          if (i) b -= 6, c++;
          if (j) b -= 9, c++;
          if (b >= 0 and b % 4 == 0) {
            c += b / 4;
            REMIN(ma, c);
          }
        }
      }
      if (ma == 1e9)
        cout << -1;
      else
        cout << ma;
    }
    cout << '\n';
  }
  return 0;
}

```