Как известно, Петька очень любит арифметику. Он много раз загадывал положительное целое число и сообщал Чапаеву сумму его цифр, а также сумму квадратов его цифр. Чапаев всегда без особых раздумий называл наименьшее число, удовлетворяющее этим требованиям. Но Петька всегда получал в ответ не то число, которое загадывал. Что же с этим делать? Как бы загадать такое число, чтобы Чапаев назвал именно его?

Петька обратился за помощью к Фурманову. Он попросил научить его определять, является ли число наименьшим с заданными суммами цифр и квадратов цифр. Фурманов был не прочь порешать на досуге математические ребусы и отнёсся к этой задачке с большим интересом. Немного поразмыслив, он понял, что от порядка цифр эти суммы не зависят, а значит, в «наименьших» числах цифры всегда идут по возрастанию. И ещё из этого следует, что нулей в таких числах не бывает. Уже всерьёз занявшись задачей, он обнаружил и такое свойство: если из «наименьшего» числа вычеркнуть несколько цифр, то снова получится «наименьшее» число.

И тут Фурманов понял, что может выписать несколько шаблонов, которые будут определять все числа, интересующие Петьку. Для этого ему будет достаточно таких шаблонов, в которых кроме цифр встречаются звёздочки, означающие, что предыдущая цифра может повторяться произвольное количество раз (в т. ч. вообще отсутствовать).

Фурманов взял вчерашний номер «Правды» и на полях выписал шаблоны. Список был таким, что любое «наименьшее» число обязательно подходит хотя бы под один из шаблонов, и в то же время любое число, подходящее под шаблоны, является «наименьшим». При этом список оказался ещё и самым коротким из возможных. А вы смогли бы повторить столь героический поступок Фурманова?

Входные данные содержат единственное целое число — основание системы счисления, для которой нужно составить такой список (от 2 до 36).

Выведите список шаблонов, отсортированный по возрастанию по обычным правилам. Каждый шаблон может содержать только цифры данной системы счисления (1, 2, …, 9, A, B, …) и звёздочку. Шаблоны не должны содержать лишние элементы: вместо шаблона «12*2*3» следует выводить «12*3». Допускается, что пустая строка может подходить под некоторые шаблоны.

Числа 222 и 1113 имеют одинаковые сумму цифр и сумму квадратов цифр. Поэтому любое число, содержащее три единицы и одну тройку, можно «уменьшить», сохранив при этом суммы цифр и квадратов цифр.