Ternarian Weights

У вас есть обычные весы с двумя чашами и набор гирь с весами 1, 3, 9, 27, .... Каждая гиря имеется только в одном экземпляре.

Для взвешивания груз кладется на левую чашу весов, к нему добавляются некоторые гири и затем весы приводятся в равновесие некоторыми другими гирями на правой чаше.

Вам нужно определить, какие гири на какую чашу следует положить.

Input

Ввод состоит из нескольких тестов. Первая строка содержит количество тестов n, 1≤n≤100. Каждый тест находится на отдельной строке и представляет из себя вес груза x, 0≤x≤10⁹.

Output

Для каждого теста выведите 3 строки. В первую из них выведите описание левой чаши: фразу "left pan: " и веса гирь на левой чаше в порядке убывания через пробел. Во вторую выведите описание правой чаши: фразу "right pan: " и веса гирь на правой чаше в порядке убывания через пробел. Выведите третью пустую строку.

4
2
3
21
250

left pan: 1
right pan: 3

left pan:
right pan: 3

left pan: 9
right pan: 27 3

left pan: 3
right pan: 243 9 1