Поиск хороших задач привел нас к комбинированию модульной арифметики с системами исчисления в разных основаниях. Например, вычисление значений по модулю b - 1, где b - основание системы исчисления, в которой задано число. Например

782910 mod 9 = 8

377777777777777738 mod 7 = 6

1234567 mod 6 = 3

(Отметим, что 377777777777777738 = 112589990684261910 и 1234567 = 2287510)

Напишите программу, которая читает числа в различных системах исчисления и находит остаток от их деления на число, на единицу меньшее от основания системы исчисления.

Входные данные

Первая строка содержит количество тестов t (1 ≤ t ≤ 1000). Каждый тест следует обрабатывать независимо от других.

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

Выходные данные

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