H. Hello Hello Hyasat
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hyasat is a dedicated software engineer who just inherited a legacy codebase. Upon running the linter, he discovers exactly $$$N$$$ warnings.To help clear the backlog, he has built two automated code-refactoring tools:

  • Quick Patch: Clears exactly $$$5$$$ warnings per run;
  • Deep Clean: Clears exactly $$$7$$$ warnings per run.

Because these tools are highly specialized, they will crash the entire system if they attempt to clear more warnings than are actually remaining.

Hyasat wants to completely eliminate all $$$N$$$ warnings using the minimum total number of tool runs.

Help him find the minimum number of times he needs to run his tools, or determine if it is impossible to clear exactly $$$N$$$ warnings without crashing the system.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

Each test case consists of a single line containing one integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the number of warnings in the codebase.

Output

For each test case, output a single integer: the minimum total number of tool runs required to clear exactly $$$n$$$ warnings. If it is impossible to clear the warnings exactly, output -1.

Example
Input
5
10
14
17
3
24
Output
2
2
3
-1
4