Problems
Happy figures (RU)
Happy figures (RU)
Школьнику Васе нравятся числа, которые заканчиваются счастливыми для него цифрами \textbf{k}. Поэтому каждый раз, когда он видит какое-нибудь натуральное число \textbf{n}, он сразу пытается подобрать такое \textbf{d} (\textbf{d} ≥ \textbf{2}), что число \textbf{n} в системе счисления с основанием \textbf{d} заканчивается как можно большим количеством цифр \textbf{k}.
Требуется написать программу, которая по заданным числам \textbf{n} и \textbf{k} найдет такое \textbf{d}, чтобы число \textbf{n} в системе счисления с основанием \textbf{d} заканчивалось как можно большим количеством цифр \textbf{k}.
\textbf{Формат входных данных}
Входной файл содержит два целых десятичных числа \textbf{n} и \textbf{k} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^11}; \textbf{0} ≤ \textbf{k} ≤ \textbf{9}).
\textbf{Формат выходных данных}
В выходной файл выведите два числа: \textbf{d} --- искомое основание системы счисления и \textbf{s} --- количество цифр \textbf{k}, которым заканчивается запись числа \textbf{n} в этой системе счисления. Если искомых \textbf{d} несколько, выведите наименьшее.
Input example #1
49 1
Output example #1
3 2