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).