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