자릿수 제곱합 함수

양의 정수 $n$을 밑이 $b$인 진법으로 나타내면 다음과 같다.

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

자릿수 제곱합 함수 $\mathrm{SSD}(b, n)$은 이 표현에 나오는 각 자리 숫자의 제곱을 모두 더한 값이다.

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

입력으로 주어진 양의 정수의 자릿수 제곱합을 구하는 프로그램을 작성하시오.

첫째 줄에 데이터 집합의 개수 $P$가 주어진다. ($1 \le P \le 10000$)

다음 $P$개 줄에 데이터 집합이 한 줄에 하나씩 주어진다. 각 데이터 집합은 서로 독립이며 모두 같은 방식으로 처리한다.

각 줄에는 데이터 집합 번호 $K$, 밑 $b$ ($3 \le b \le 16$), 밑 $b$에서 자릿수 제곱합을 계산할 양의 정수 $n$이 공백으로 구분되어 주어진다. 세 값 모두 십진수이고, $n$은 32비트 부호 없는 정수 범위에 들어간다.

각 데이터 집합마다 한 줄씩 출력한다.

한 줄에는 데이터 집합 번호 $K$, 공백 한 칸, $\mathrm{SSD}(b, n)$의 값을 십진수로 출력한다.