The Sum Squared Digits function, SSD(b, n) of a positive integer n, in base b is defined by representing n in base b as in:</p>

n = a₀ + a₁b + a₂b² + …

then:

SSD(b, n) = a₀² + a₁² + a₂² + …

is the sum of squares of the digits of the representation.

Write a program to compute the Sum Squared Digits function of an input positive number.

입력 형식

The first line of input contains a single decimal integer P, (1 ≤ P ≤ 10000), which is the number of data sets that follow. Each data set should be processed identically and independently.</p>

Each data set consists of a single line of input. It contains the data set number, K, followed by the base, b (3 ≤ b ≤ 16) as a decimal integer, followed by the positive integer, n (as a decimal integer) for which the Sum Squared Digits function is to be computed with respect to the base b. n will fit in a 32 bit unsigned integer. 

출력 형식

For each data set there is a single line of output.</p>

The single line of output consists of the data set number, K, followed by a single space followed by the value of SSD(b, n) as a decimal integer.

예제 입력

3
1 10 1234
2 3 98765
3 16 987654321

예제 출력

1 30
2 19
3 696