Sum Squared Digits Function

Write a positive integer $n$ in base $b$:

$n = a_0 + a_1 b + a_2 b^2 + \cdots$

The sum squared digits function $\mathrm{SSD}(b, n)$ is the sum of the squares of the digits of that representation.

$\mathrm{SSD}(b, n) = a_0^2 + a_1^2 + a_2^2 + \cdots$

Write a program that computes the sum squared digits function of a given positive integer.

The first line contains one decimal integer $P$, the number of data sets that follow. ($1 \le P \le 10000$)

Each of the next $P$ lines holds one data set. The data sets are independent and are all processed the same way.

A line contains the data set number $K$, the base $b$ ($3 \le b \le 16$), and the positive integer $n$ whose sum squared digits value in base $b$ is to be computed, separated by spaces. All three values are decimal integers, and $n$ fits in a 32 bit unsigned integer.

Print one line for each data set.

The line contains the data set number $K$, a single space, and the value of $\mathrm{SSD}(b, n)$ as a decimal integer.