테르나리아의 저울추

헬레니즘 시대의 지중해에는 테르나리아라는 작은 섬나라가 있었다. 스파르타와 가까웠지만 산이 험해서 스파르타가 정복하기 어려웠고, 기원전 729년 대지진으로 바다에 가라앉기 전까지 독립국으로 남았다. 문명 수준이 높아서 일부 현대 역사학자는 이 섬을 신화 속 도시 아틀란티스의 원형으로 본다. 테르나리아가 과학과 수학에 남긴 성과는 그리스가, 나중에는 로마가 상당 부분 받아들였다. 오늘날에도 쓰는 파운드 단위를 처음 표준으로 삼은 것도 테르나리아 사람이다. 테르나리아 수학은 모든 계산을 3진법으로 했다. (역사학자들은 스파르타와 싸우다 양손에서 손가락을 두 개씩 잃은 테르나리 왕을 기린 결과라고 추측한다.)

테르나리아의 양팔저울은 여러 세기 동안 표준이었다. 정확하고 쓰기 쉬웠기 때문이다. 양쪽에 접시를 두고 가운데에 받침점을 둔 저울을 처음 만든 것도 테르나리아 사람이다. 무게를 잴 물건은 왼쪽 접시에 올리고, 평형이 될 때까지 양쪽 접시에 추를 올린다. 요즘 저울은 보통 오른쪽 접시에만 추를 올리니 이 방식이 낯설어 보인다. 그러나 요즘 방식은 추가 더 많이 필요하다. 테르나리아 방식은 3의 거듭제곱 파운드마다 추를 하나씩만 갖추면 된다. 즉 1파운드 추 하나, 3파운드 추 하나, 9파운드 추 하나, 이런 식이다.

2파운드짜리 테르나리아 닭의 무게를 잰다고 하자. 닭을 왼쪽 접시에 올리고 3파운드 추를 오른쪽에 올리면 오른쪽이 더 무겁다. 그래서 1파운드 추를 닭과 함께 왼쪽에 올려 평형을 맞춘다. 오른쪽 추의 합에서 왼쪽 추의 합을 뺀 값이 물건의 무게와 같다.

21파운드짜리 테르나리아 호박이라면 27파운드 추와 3파운드 추를 오른쪽에 올리고 9파운드 추를 물건과 함께 왼쪽에 올려 평형을 맞춘다.

10진수로 주어진 물건의 무게를 읽어 양쪽 접시에 올릴 추를 출력하는 프로그램을 작성하시오.

첫 줄에 풀어야 할 테스트 케이스의 개수 $n$이 주어진다. ($1 \le n \le 100$)

다음 $n$개 줄에는 각각 왼쪽 접시에 올릴 물건의 무게 $x$가 파운드 단위로 주어진다. ($0 \le x \le 10^9$)

각 테스트 케이스마다 두 줄을 출력한다.

첫 줄에는 left pan:을 출력한 뒤, 왼쪽 접시에 올릴 추를 내림차순으로 출력한다. 둘째 줄에는 right pan:을 출력한 뒤, 오른쪽 접시에 올릴 추를 내림차순으로 출력한다. 추는 공백 하나로 구분하고, 첫 추 앞에도 공백을 하나 둔다. 한쪽 접시에 올릴 추가 없으면 그 줄에는 이름만 출력한다.

3의 거듭제곱 파운드마다 추가 하나씩만 있으므로 평형을 이루는 방법은 하나뿐이다.

테스트 케이스 사이에는 빈 줄을 하나 출력한다.