다이아몬드 암호

어느 유명 보석 회사가 금고 보안 소프트웨어를 의뢰했습니다. 이 회사는 다이아몬드를 보관하는 두 종류의 금고를 만듭니다. 하나는 스위치가 $20$개이고, 다른 하나는 스위치가 $200$개입니다. 금고를 열려면 숫자로 이루어진 비밀번호가 필요합니다. 비밀번호가 주어지면 스위치를 어떻게 맞춰야 하는지 알려 주는 프로그램을 작성하세요.

스위치는 $0$번부터 차례로 번호가 매겨져 있고, $i$번 스위치에는 값 $3^i$이 배정됩니다. 각 스위치는 세 가지 상태(위, 가운데, 아래)를 가집니다. 위로 올린 스위치들의 값의 합에서 아래로 내린 스위치들의 값의 합을 뺀 값이 비밀번호와 같으면 금고가 열립니다.

다음을 수행하는 프로그램을 작성하세요.

• 표준 입력에서 금고 비밀번호들을 읽고,
• 각 비밀번호에 대해 스위치 배치를 구한 뒤,
• 결과를 표준 출력에 씁니다.

첫째 줄에 비밀번호의 개수 $N$이 주어집니다 ($1 \le N \le 250$). 이어지는 $N$개의 줄에는 각각 금고 비밀번호가 하나씩 주어지며, 앞자리에 불필요한 $0$이 없는 음이 아닌 정수입니다. 절반의 테스트에서는 모든 비밀번호가 스위치 $20$개짜리 금고에 해당하고, 나머지 절반에서는 스위치 $200$개짜리 금고가 필요할 수 있습니다.

각 비밀번호에 대해 금고를 여는 스위치 상태를 두 줄에 걸쳐 출력합니다. 첫째 줄에는 위로 올린 스위치의 개수를 먼저 쓰고, 이어서 그 스위치들의 번호를 오름차순으로 씁니다. 둘째 줄에는 아래로 내린 스위치의 개수를 먼저 쓰고, 이어서 그 스위치들의 번호를 오름차순으로 씁니다. 한 줄 안의 모든 수는 공백 하나로 구분합니다. 위(또는 아래)로 놓인 스위치가 하나도 없으면 그 줄에는 $0$만 출력합니다.