B-Кастинг
B-Кастинг
Поиск хороших задач привел нас к комбинированию модульной арифметики с системами исчисления в разных основаниях. Например, вычисление значений по модулю b - 1, где b - основание системы исчисления, в которой задано число. Например
7829[10]
mod 9 = 8
37777777777777773[8]
mod 7 = 6
123456[7]
mod 6 = 3
(Отметим, что 37777777777777773[8]
= 1125899906842619[10]
и 123456[7]
= 22875[10]
)
Напишите программу, которая читает числа в различных системах исчисления и находит остаток от их деления на число, на единицу меньшее от основания системы исчисления.
Вхідні дані
Первая строка содержит количество тестов t (1 ≤ t ≤ 1000). Каждый тест следует обрабатывать независимо от других.
Каждый тест состоит из одной строки, содержащей три целых числа. Первое число указывает на номер теста. Второе число b (2 ≤ b ≤ 10) содержит основание системы исчисления. Третье число содержит неотрицательное целое d в системе исчисления b. Количество цифр в числе d не превышает 10000000.
Вихідні дані
Для каждого теста в отдельной строке вывести его номер, пробел, и остаток от деления числа d на (b - 1).
Приклад
5 1 10 7829 2 7 123456 3 6 432504023545112 4 8 37777777777777773 5 2 10110100010101010101101110001010001010101010101010111
1 8 2 3 3 1 4 6 5 0