eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

B-Кастинг

B-Кастинг

Ліміт часу 1 секунда
Ліміт використання пам'яті 123 MiB

Поиск хороших задач привел нас к комбинированию модульной арифметики с системами исчисления в разных основаниях. Например, вычисление значений по модулю 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 (1t1000). Каждый тест следует обрабатывать независимо от других.

Каждый тест состоит из одной строки, содержащей три целых числа. Первое число указывает на номер теста. Второе число b (2b10) содержит основание системы исчисления. Третье число содержит неотрицательное целое d в системе исчисления b. Количество цифр в числе d не превышает 10000000.

Вихідні дані

Для каждого теста в отдельной строке вывести его номер, пробел, и остаток от деления числа d на (b - 1).

Приклад

Вхідні дані #1
5
1 10 7829
2 7 123456
3 6 432504023545112
4 8 37777777777777773
5 2 10110100010101010101101110001010001010101010101010111
Вихідні дані #1
1 8
2 3
3 1
4 6
5 0
Джерело Greater New York Region Programming Contest, 2012, October 28