В стране Патагонии живет сто благородных семей, и каждый год некоторые из них получают несколько ритуальных кубов от Всевидящего Ока. Он имеет несколько правил распределения кубов: если семья получает хотя бы один куб, то каждый простой делитель их количества должен быть либо 2 либо 3, к тому же, если одна семья получит a > 0 кубов а другая семья в том же году получит b > 0 кубов, то a не должно быть кратно b и наоборот.

Вы - Всевидящее Око. Вам известно, сколько кубов будет доступно для распределения в следующие t лет. Вы ходите найти корректное распределение кубов в каждом году. Каждый год Вы должны распределить все доступные кубы на этот год.

Входные данные

Первая строка содержит количество годов t (1 ≤ t ≤ 1000). Каждая из следующих t строк содержит количество кубов ni (1 ≤ ni ≤ 1018), которое следует распределить в i-ом году.

Выходные данные

Для каждого года i выведите две строки. В первой строке вывести количество семей mi (1 ≤ mi ≤ 100), которое получит хотя бы один куб в i-ый год. Во второй строке вывести mi чисел - количество кубов, которое получила каждая семья. Сумма этих чисел должна равняться ni.