Back

C. Sum Squared Digits

Worth 4 point(s) - Runtime Limit: 3 seconds

Summary

To form the Sum Squared Digits function, \(SSD(b, n)\) of a positive integer \(n\), in base \(b\), we first state that the digits of \(n, a_0, a_1, . . . , a_{k−1}\), are in the set {0, 1, . . . , b − 1}. Then the Value of \(n\) is given by
$$ Value(n) = a_{k−1}b^{k−1} + a_{k−2}b^{k−2} + . . . + a_1b^1 + a_0 $$

Then

$$ SSD(b, n) = a^{2}_0 + a^{2}_1 + a^{2}_2 + . . . + a^{2}_{k-1} $$
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.

Input

The first line of input contains a single decimal integer P, (1 ≤ P ≤ 10000), which is the number of datasets that follow. Each dataset should be processed identically and independently.
Each dataset consists of a single line of input. It contains the dataset 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\). The value of \(n\) will fit in a 32 bit unsigned integer.

3
1 10 1234
2 3 98765
3 16 987654321

Output

For each dataset there is a single line of output
The single line of output consists of the dataset number, K, followed by a single space followed by the value of \(SSD(b, n)\) as a decimal integer.

1 30
2 19
3 696