Задача Kingdoms. В одному далекому казковому королівстві жив Вчений. Багато років він працював над можливістю подорожувати іншими казковими королівствами, що знаходяться в паралельних світах. Внаслідок проведених багаточисельних експериментів і завдяки щасливому випадку Вчений раптом виявив, що здійснити свою давню мрію можна за допомогою портального пристрою, зібраного з чарівних кристалів. Існує всього дев'ять різновидів таких кристалів, причому кристали кожного з дев'яти видів є в королівстві в достатній кількості. Для того, щоб потрапити в казкове королівство, яке знаходиться в паралельному світі номер N, треба послідовно (щільно один до одного вряд) з'єднати рівно N чарівних кристалів таким чином, щоб оптичне збільшення отриманого портального пристрою чисельно дорівнювало його електричному опору. Допоможіть Вченому визначити, скільки існує різних способів потрапити в паралельний світ номер N і яка мінімальна кількість чарівних кристалів кожного виду для цього знадобиться.

Величини оптичного збільшення та електричного опору кожного з дев'яти видів кристалів чисельно рівні їх номерам- від одного до дев'яти. Наприклад, оптичне збільшення всіх чарівних кристалів "номер шість" дорівнює шести й електричний опір їх також дорівнює шести. Подорожі відбуваються по черзі, кристали можна використовувати багато разів.

Технічні умови. Програма Kingdoms читає з пристрою стандартного введення натуральне число N(1<=N<=500). Програма виводить у одному рядку через пропуски спочатку шукане число - кількість різних способів потрапляння в паралельний світ із заданим номером, а далі дев'ять чисел - мінімальну кількість кристалів (у порядку збільшення номерів) для здійснення всіх почергових подорожей у паралельний світ номерN.