OPS

홀수 소수 공간(Odd Prime Space, OPS)은 모든 성분이 홀수 소수인 벡터의 집합이다. 예를 들어 $\begin{pmatrix} 3 \\ 5 \end{pmatrix}$와 $\begin{pmatrix} 7 \\ 11 \\ 13 \end{pmatrix}$은 OPS에 속하지만, $\begin{pmatrix} 2 \\ 3 \end{pmatrix}$과 $\begin{pmatrix} 4 \\ 5 \\ 6 \end{pmatrix}$은 속하지 않는다. 이 문제에서는 3차원 공간인 3D-OPS를 다룬다.

$\text{3D-OPS} = \left\{ \begin{pmatrix} p_1 \\ p_2 \\ p_3 \end{pmatrix} ; \; p_1, p_2, p_3 \text{ \text{는 홀수 소수}} \right\}$

전산학자 맥 픽은 3D-OPS를 연구하다가, 3D-OPS를 홀수 공간(Odd Space, OS)이라는 1차원 공간으로 대응시킬 수 있다는 사실을 발견했다. OS를 다루는 쪽이 3D-OPS를 직접 다루는 쪽보다 훨씬 쉽다.

$\text{OS} = \left\{ x ; \; x \text{ \text{는 7보다 큰 홀수}} \right\}$

정방향 대응은 간단하다. 홀수 소수 세 개를 더하면 7보다 큰 홀수가 나온다. 어려운 쪽은 반대 방향이다. OS의 모든 원소가 3D-OPS로 되돌아갈까? 지금까지 확인한 범위에서는 모두 그렇다. 이 주장이 18세기부터 아무도 증명하지도 반증하지도 못한 골드바흐 추측이다.

반대 방향의 대응은 하나로 정해지지 않는다. 예를 들어 $15 = 5 + 5 + 5 = 3 + 5 + 7$이고 $17 = 3 + 3 + 11 = 5 + 5 + 7$이다. 맥 픽은 모든 해를 출력하라고 요구하지 않는다. 무한대 노름을 최대로 만드는 해 하나를 골라, 그 노름의 값만 알고 싶어 한다.

선형대수학에서 노름은 벡터에 항상 양수인 길이를 대응시키는 함수다. 이미 알고 있을 만한 노름을 아래에 적는다. 이 문제에서는 $n = 3$이다.

맨해튼 노름:

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

유클리드 노름:

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

$p$-노름:

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

무한대 노름은 $p$-노름에서 $p \to \infty$인 특수한 경우라서, 값을 구하려면 극한을 계산해야 한다.

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

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 5\,000$).

다음 $T$개의 줄에 각각 홀수 $M$이 하나씩 주어진다 ($7 < M < 1\,000\,000$).

각 테스트 케이스마다 $p_1 + p_2 + p_3 = M$을 만족하는 3D-OPS의 벡터 가운데 $\left\| \begin{pmatrix} p_1 \\ p_2 \\ p_3 \end{pmatrix} \right\|_\infty$의 최댓값을 한 줄에 하나씩 출력한다.

입력 범위의 모든 $M$에 대해 그런 벡터가 적어도 하나 있으므로, 답은 항상 존재한다.