Счастливые цифры
Счастливые цифры
Школьнику Васе нравятся числа, которые заканчиваются счастливыми для него цифрами k
. Поэтому каждый раз, когда он видит какое-нибудь натуральное число n
, он сразу пытается подобрать такое d
(d ≥ 2
), что число n
в системе счисления с основанием d
заканчивается как можно большим количеством цифр k
.
Требуется написать программу, которая по заданным числам n
и k
найдет такое d
, чтобы число n
в системе счисления с основанием d
заканчивалось как можно большим количеством цифр k
.
Формат входных данных
Входной файл содержит два целых десятичных числа n
и k
(1 ≤ n ≤ 1011
; 0 ≤ k ≤ 9
).
Формат выходных данных
В выходной файл выведите два числа: d
— искомое основание системы счисления и s
— количество цифр k
, которым заканчивается запись числа n
в этой системе счисления. Если искомых d
несколько, выведите наименьшее.
49 1
3 2