OPS

The Odd Prime Space (OPS) is the set of vectors whose every entry is an odd prime. For example $\begin{pmatrix} 3 \\ 5 \end{pmatrix}$ and $\begin{pmatrix} 7 \\ 11 \\ 13 \end{pmatrix}$ belong to OPS, while $\begin{pmatrix} 2 \\ 3 \end{pmatrix}$ and $\begin{pmatrix} 4 \\ 5 \\ 6 \end{pmatrix}$ do not. This problem uses the three dimensional space 3D-OPS.

$\text{3D-OPS} = \left\{ \begin{pmatrix} p_1 \\ p_2 \\ p_3 \end{pmatrix} ; \; p_1, p_2, p_3 \text{ are odd primes} \right\}$

Mac Picc, a computer scientist, works with 3D-OPS. He found that he can map 3D-OPS onto a one dimensional space called the Odd Space (OS), and that OS is much easier to work with.

$\text{OS} = \left\{ x ; \; x \text{ is an odd number greater than 7} \right\}$

The forward map is simple: add the three odd primes and you get an odd number greater than 7. The reverse direction is the hard part. Does every member of OS map back into 3D-OPS? Everything checked so far says yes. That claim is Goldbach's conjecture, open since the 18th century, and nobody has proved or disproved it.

The reverse map is also not unique. For instance $15 = 5 + 5 + 5 = 3 + 5 + 7$ and $17 = 3 + 3 + 11 = 5 + 5 + 7$. Mac Picc does not ask you to print every solution. He wants the solution that maximizes the infinity norm, and only the value of that norm.

In linear algebra a norm assigns a strictly positive length to a vector. Here are norms you may already know, with $n = 3$ in this problem.

Manhattan norm:

$\|x\|_1 = \sum_{i=1}^{n} |x_i|$

Euclidean norm:

$\|x\|_2 = \sqrt{x_1^2 + x_2^2 + \cdots + x_n^2}$

$p$-norm:

$\|x\|_p = \left( \sum_{i=1}^{n} |x_i|^p \right)^{1/p}$

The infinity norm is the special case $p \to \infty$ of the $p$-norm, so computing it needs a limit.

$\|x\|_\infty = \lim_{p \to \infty} \left( \sum_{i=1}^{n} |x_i|^p \right)^{1/p}$

The first line contains an integer $T$, the number of test cases ($1 \le T \le 5\,000$).

Each of the next $T$ lines contains one odd integer $M$ ($7 < M < 1\,000\,000$).

For each test case, print one line with the largest value of $\left\| \begin{pmatrix} p_1 \\ p_2 \\ p_3 \end{pmatrix} \right\|_\infty$ over all vectors of 3D-OPS with $p_1 + p_2 + p_3 = M$.

At least one such vector exists for every $M$ in the input range, so an answer always exists.