좀비 침공

헬리콥터를 타고 온 생존자 무리가 외딴 섬에 도착했다. 섬은 좁고 긴 띠 모양이고, 마을 20개가 서쪽 해안부터 동쪽 해안까지 한 줄로 늘어서 있다. 감염된 생존자가 가장 동쪽 마을에 내리는 바람에 그곳 주민까지 감염됐고, 좀비는 동쪽 해안에서 서쪽으로 밀고 들어온다. 섬 주민은 서쪽으로 달아나기 시작한다.

주민의 이동 풍습은 독특하다. 마을과 마을 사이는 두 명이 짝을 지어서만 건널 수 있고, 짝을 지어 건넌 두 명 중 한 명만 살아서 도착한다.

좀비가 동쪽 끝 마을부터 한 마을씩 서쪽으로 밀려오므로, 이동도 동쪽 끝 마을에서 시작해 서쪽 방향으로 한 마을씩 차례대로 일어난다. 차례가 된 마을에 사람이 $k$명 있으면 그중 $\lfloor k/2 \rfloor$명이 바로 서쪽 마을에 도착하고, $k$가 홀수이면 남은 한 명이 그 마을에 남는다. 사람이 한 명뿐인 마을에서는 짝을 지을 수 없어서 아무도 움직이지 못한다. 서쪽 해안 마을에 닿은 사람은 더 이동하지 않고 그 마을에 모인다.

각 마을에 몇 명이 남는지, 그리고 서쪽 해안 마을에 최종적으로 몇 명이 있는지 구하라.

첫 줄에 데이터 집합의 개수 $N$이 주어진다. ($1 \le N \le 50$)

이어지는 $N$개의 줄에는 각각 음이 아닌 정수 20개가 주어진다. 각 정수는 한 마을에 사는 주민 수이고 1000 이하다. 가장 왼쪽 수가 서쪽 해안 마을, 가장 오른쪽 수가 동쪽 해안 마을에 해당한다.

데이터 집합마다 음이 아닌 정수 20개를 공백으로 구분해 한 줄에 출력한다.

첫 번째 수는 이동이 모두 끝난 뒤 서쪽 해안 마을에 있는 사람 수이고, 원래 그 마을에 살던 주민도 포함한다. 두 번째 수부터는 서쪽에서 두 번째 마을부터 동쪽 해안 마을까지 각 마을에 남은 사람 수를 순서대로 출력한다.