Повторювані десяткові#3767

Повторювані десяткові

2 секунди

64 мегабайти

Легка

Десяткове представлення цілого числа може бути перетворене в інше ціле число шляхом перестановки його цифр. Використовуючи цей принцип, ми можемо побудувати послідовність чисел.

Вам дано невід'ємне ціле число $a_{0}$ a_0 та кількість цифр $L$ . Застосовуючи наведене нижче правило, отримаємо $a_{i + 1}$ a_{i+1} з $a_{i}$ a_i.

Представимо ціле число $a_{i}$ a_i у десятковому вигляді з $L$ цифрами. За необхідності додамо провідні нулі. Наприклад, десяткове представлення числа $2012$ з шістьма цифрами буде $002012$ .
Переставляючи цифри, знайдемо максимальне і мінімальне число. Для наведеного прикладу найбільшим буде $221000$ , а найменшим $000122 = 122$ 000122 = 122.
Нове число $a_{i + 1}$ a_{i+1} отримується шляхом віднімання найменшого числа з найбільшого. Для нашого прикладу це буде $220878$ , отримане відніманням $122$ з $221000$ .

Повторюючи ці обчислення, отримаємо послідовність цілих чисел $a_{0}$ a_0, $a_{1}$ a_1, $a_{2}$ a_2, ... .

Наприклад, починаючи з числа $83268$ і при кількості цифр $6$ , отримаємо таку послідовність $a_{0}$ a_0, $a_{1}$ a_1, $a_{2}$ a_2, ... :

a_{0} = 083268, a_{1} = 886320 - 023688 = 862632, a_{2} = 866322 - 223668 = 642654, a_{3} = 665442 - 244566 = 420876, a_{4} = 876420 - 024678 = 851742, a_{5} = 875421 - 124578 = 750843, a_{6} = 875430 - 034578 = 840852, a_{7} = 885420 - 024588 = 860832, a_{8} = 886320 - 023688 = 862632 \dots

a_0 = 083268, a_1 = 886320 - 023688 = 862632, a_2 = 866322 - 223668 = 642654, a_3 = 665442 - 244566 = 420876, a_4 = 876420 - 024678 = 851742, a_5 = 875421 - 124578 = 750843, a_6 = 875430 - 034578 = 840852, a_7 = 885420 - 024588 = 860832, a_8 = 886320 - 023688 = 862632 \ldots

Оскільки кількість цифр фіксована, то незабаром деяке число повториться в послідовності $a_{0}$ a_0, $a_{1}$ a_1, $a_{2}$ a_2, ... . Тобто завжди знайдеться така пара $i$ і $j$ , для якої $a_{i} = a_{j}$ a_i = a_j ( $i > j$ i > j). Для наведеного прикладу пара ( $i = 8$ i = 8, $j = 1$ j = 1) задовольняє умові, оскільки $a_{8} = a_{1} = 862632$ a_8 = a_1 = 862632.

За заданим цілим числом $a_{0}$ a_0 і кількістю цифр $L$ потрібно знайти найменше $i$ , яке задовольняє умові $a_{i} = a_{j}$ a_i = a_j ( $i > j$ i > j).

Вхідні дані

Вхідні дані складаються з кількох тестів. Кожен тест складається з рядка, що містить два цілі числа $a_{0}$ a_0 і $L$ , розділених пробілом. $a_{0}$ a_0 і $L$ представляють початкове число послідовності і кількість цифр відповідно. Відомо, що $1 \leq L \leq 6$ 1 \le L \le 6 і $0 \leq a_{0} < 1 0^{L}$ 0 \le a_0 < 10^L.

Останній рядок містить два нулі і не обробляється.

Вихідні дані

Для кожного тесту потрібно знайти найменше $i$ , що задовольняє умові $a_{i} = a_{j}$ a_i = a_j ( $i > j$ i > j) і вивести рядок, що містить три цілі числа: $j$ , $a_{i}$ a_i і $i - j$ i - j. Виведені числа слід розділяти пробілом. Провідні нулі не виводити.

Відомо, що шукане значення $i$ не перевищує $20$ .

Приклади

Приклад 1