화물 우주선 적재

줄리엣이 읽는 공상과학 소설에는 화물 우주선의 적재량을 최대로 쓰는 문제가 나온다. 우주선이 나르는 화물은 각 차원의 크기가 3인 $D$차원 격자 모양이다. 격자의 각 절점에는 무게가 같은 공이 하나씩 놓이고, 공을 잇는 연결선의 무게는 공에 비해 무시할 수 있을 만큼 작다. 그래서 화물 하나의 무게는 절점의 개수로만 정해진다. 반면 화물의 가치는 절점의 개수와 연결선의 개수를 더한 값이다.

$D$차원 화물에는 절점이 $3^D$개 있고, 한 축의 방향으로 이웃한 두 절점마다 연결선이 하나씩 있다.

우주선에는 실을 수 있는 무게의 한도가 있다. 한도를 넘기지 않으면서 실은 화물의 가치 합을 최대로 만들어야 한다. 어느 차원의 화물이든 원하는 만큼 쓸 수 있다. 가치 합을 최대로 만드는 적재 방법은 하나뿐이다.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다. $N$은 양의 정수이다.

다음 $N$개의 줄에 우주선의 적재 한도를 나타내는 정수 $K$가 한 줄에 하나씩 주어진다. ($1 \le K < 10^7$)

각 테스트 케이스마다 $X_m\ X_{m-1}\ \dots\ X_1\ X_0$을 공백으로 구분해 한 줄에 출력한다. $X_i$는 가치 합을 최대로 만들기 위해 실어야 하는 $i$차원 화물의 개수이고, 가장 높은 차원의 개수 $X_m$은 0보다 크다.