Problem Description

Casting around for problems leads us to combine modular arithmetic with different integer bases, particularly the problem of computing values modulo b-1, where b is the base in which the value is represented. For example,

7829₁₀ mod 9 = 8,
37777777777777773₈ mod 7 = 6
123456₇ mod 6 = 3

(Note that 37777777777777773₈ = 1125899906842619₁₀ and 123456₇ = 22875₁₀.)

Your job is to write a program that reads integer values in various bases and computes the remainder after dividing these values by one less than the input base.

Input

The first line of input contains a single integer P, (1 <= P <= 1000) , which is the number o data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input containing three space-separated values. The first is an integer which is the data set number. The second is an integer which is the number, B (2 <= B <= 10), denoting a numeric base. The third is an unsigned number, D, in base B representation. For this problem, the number of numeric characters in D will be limited to 10,000,000.

Output

For each data set there is a single line of output. It contains the data set number followed by a single space which is then followed by the remainder resulting from dividing D by (B-1).

4
1 10 7829
2 7 123456
3 6 432504023545112
4 8 37777777777777773 

1 8
2 3
3 1
4 6