#include <bits/stdc++.h>
using namespace std;
long long q, n, ans;
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  exgcd(b, a % b, x, y);
  long long z = x;
  x = y;
  y = z - (a / b) * y;
}
signed main() {
  scanf("%lld", &q);
  while (q--) {
    scanf("%lld", &n);
    if (n < 4) {
      printf("-1\n");
      continue;
    }
    if (n % 4 == 0 || n % 4 == 2)
      printf("%lld\n", n / 4);
    else {
      long long x, y, a, b;
      ans = -0x3f3f3f3f;
      exgcd(4, 9, x, y);
      x *= n;
      y *= n;
      a = x;
      b = y;
      y = (y % 4 + 4) % 4;
      x = n - 9 * y;
      x /= 4;
      if (x >= 0 && y >= 0) ans = max(ans, x + y);
      x = a;
      y = b;
      x = (x % 9 + 9) % 9;
      y = n - 4 * x;
      y /= 9;
      if (x >= 0 && y >= 0) ans = max(ans, x + y);
      long long m = n;
      if (n % 3 == 0) {
        n /= 3;
        exgcd(2, 3, x, y);
        x *= n;
        y *= n;
        a = x;
        b = y;
        y = (y % 2 + 2) % 2;
        x = n - 3 * y;
        x /= 2;
        if (x >= 0 && y >= 0) ans = max(ans, x + y);
        x = a;
        y = b;
        x = (x % 3 + 3) % 3;
        y = n - 2 * x;
        y /= 3;
        if (x >= 0 && y >= 0) ans = max(ans, x + y);
      }
      n = m;
      if (n > 6) {
        n -= 6;
        exgcd(4, 9, x, y);
        x *= n;
        y *= n;
        a = x;
        b = y;
        y = (y % 4 + 4) % 4;
        x = n - 9 * y;
        x /= 4;
        if (x >= 0 && y >= 0) ans = max(ans, x + y + 1);
        x = a;
        y = b;
        x = (x % 9 + 9) % 9;
        y = n - 4 * x;
        y /= 9;
        if (x >= 0 && y >= 0) ans = max(ans, x + y + 1);
      }
      if (ans == -0x3f3f3f3f)
        printf("-1\n");
      else
        printf("%lld\n", ans);
    }
  }
}

### 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;
long long q, n, ans;
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  exgcd(b, a % b, x, y);
  long long z = x;
  x = y;
  y = z - (a / b) * y;
}
signed main() {
  scanf("%lld", &q);
  while (q--) {
    scanf("%lld", &n);
    if (n < 4) {
      printf("-1\n");
      continue;
    }
    if (n % 4 == 0 || n % 4 == 2)
      printf("%lld\n", n / 4);
    else {
      long long x, y, a, b;
      ans = -0x3f3f3f3f;
      exgcd(4, 9, x, y);
      x *= n;
      y *= n;
      a = x;
      b = y;
      y = (y % 4 + 4) % 4;
      x = n - 9 * y;
      x /= 4;
      if (x >= 0 && y >= 0) ans = max(ans, x + y);
      x = a;
      y = b;
      x = (x % 9 + 9) % 9;
      y = n - 4 * x;
      y /= 9;
      if (x >= 0 && y >= 0) ans = max(ans, x + y);
      long long m = n;
      if (n % 3 == 0) {
        n /= 3;
        exgcd(2, 3, x, y);
        x *= n;
        y *= n;
        a = x;
        b = y;
        y = (y % 2 + 2) % 2;
        x = n - 3 * y;
        x /= 2;
        if (x >= 0 && y >= 0) ans = max(ans, x + y);
        x = a;
        y = b;
        x = (x % 3 + 3) % 3;
        y = n - 2 * x;
        y /= 3;
        if (x >= 0 && y >= 0) ans = max(ans, x + y);
      }
      n = m;
      if (n > 6) {
        n -= 6;
        exgcd(4, 9, x, y);
        x *= n;
        y *= n;
        a = x;
        b = y;
        y = (y % 4 + 4) % 4;
        x = n - 9 * y;
        x /= 4;
        if (x >= 0 && y >= 0) ans = max(ans, x + y + 1);
        x = a;
        y = b;
        x = (x % 9 + 9) % 9;
        y = n - 4 * x;
        y /= 9;
        if (x >= 0 && y >= 0) ans = max(ans, x + y + 1);
      }
      if (ans == -0x3f3f3f3f)
        printf("-1\n");
      else
        printf("%lld\n", ans);
    }
  }
}

```